Поиск по регулярному выражению в массиве небольших строк

С регулярками ты будешь парсить несколько часов.

y not awk?

Можт, слепить в одну строку, прогнать, ну а потом как-нибудь отколупать точное место вхождения, если оно там вообще есть?

Нет, не подойдёт.

Считай хеш, сортируй, ищи бинарным поиском.

Если длина строки 10 символов нахер не нужны никакие выкрутасы. тут основная просадка будет приходится не на регекспы, а на перебор массива. Глупость какая-то. Это имело бы смысл, если бы строки были длинными.

А не, говно советую, ты же регекспы хочешь.

А ты их точно хочешь?

То есть вместо перебора \Theta (n), делать \Theta(n log n).

Толково.

А regexp у тебя О(1) ?

Поиск по регулярному выражению в массиве небольших строк (комментарий)

Тож задумался. Вообще, в приложении могло бы сильно пригодиться.

может отсортировать, если это поможет сузить границы, где матчить регулярное выражение, то получите выигрыш

Конечно.

Это почему? Бинарный поиск — O(log(n)).

Считай хеш, сортируй, ищи бинарным поиском.

\Theta(n) + \Theta(n log n) + \Theta(log n)

Ну тут несколько вариантов.
1. Бинарное дерево поиска - если будешь искать не один раз
2. Сравнение результата fgets - если будешь искать один раз
3. Дерево, у которого в каждом узле содержится массив указателей на символы слова. Забыл как оно называется.
К примеру: есть слово «привет» В первом узле по индексу 'п' указатель на второй узел. Во втором узле по индексу 'р' указатель на третий узел и тд.

Вставка в отсортированный массив — это по сложности тот же бинарный поиск.

Какого вида регулярки?

Вставка в отсортированный массив

n раз по

это по сложности тот же бинарный поиск.

\Theta(log n)

А ты в ядрах так же хорошо разбираешься, как в алгоритмах?

Может, ему нужно данные постепенно накапливать, а искать быстро.

А ты в ядрах так же хорошо разбираешься, как в алгоритмах?

Если тебя интересует этот вопрос, можешь создать отдельный топик и резвиться там.

Может, ему нужно данные постепенно накапливать, а искать быстро.

А почему ты не спросил это у него?

А ты?

Общего вида.

Ну, так сортировку и бинарный поиск не я же предлагал. А то, что надо, я у него спросил, а именно вид регулярок. Бинарный поиск над специально подготовленным массивом имеет смысл только для достаточно ограниченного множества.

Накапливание промежуточных резулататов не подойдёт, всё же насколько быстро будет расти объём накапливаемых данных?

Насколько быстро будет расти объём накапливаемых данных?

Можешь покурить сырцы грепа или какой-нибудь другой быстрой реализации именно регулярок на предмет разнообразных ускорений в частных случаях, но так или иначе ответ тебе будет - нет, только молодость, только перебор.

Лучше конкретнее опиши задачу, которую ты решаешь.

Ну да, это может дать прирост, че то не подумал. По сути, единственно верный вариант, в данном случае. Так и делай.

Полистаю. Со сваливанием в одну большую строку не заморачиваться?

В grep'е и sed'е такие оптимизации есть (месим не разбивая по \n, потом разберёмся), это ускоряет с точки зрения чтения большими кусками.

При определённых обстоятельствах это может и замедлить, так как разрешает больше строк, которые потом будут выброшены, при учёте границ.

Дано:

Список строк, длинной порядка миллионов элементов; строки, длинной порядка десятков символов; произвольное регулярное выражение.

Найти:

1) строки, в которых встречается данное регулярное выражение,

2) указать точные места вхождений.

Спасибо!

Как и где эти строки хранятся?

Односвязный список, в каждой вершине хранится указатель на строку.

Т.е., ты эти строки скопом откуда-то подгружаешь в память?

Совершенно верно.

Неужели си такой медленный? Я щас попробовал на JS массив из миллиона строк, при худшем для регулярок случае (совпадение в конце строки) с наполнением другого массива выполняется за 424 ms на слабой машине. Че там оптимизировать, спрашивается?

Интересно.

Можете выложить ваш бенчмарк?

И да, регуляркой по целой строке быстрей — 260ms

Это anonimous наверняка опять пустые циклы считает.

Предлагаю считать хэши и сортировать при вставке прямо во время загрузки.

Не думаю, что в конце строки — это худший случай, наверное, облом в середине регулярного выражения при обработке похожей подстроки, стоящей в середине проверяемой строки...

Хотя нафига тебе хеш? Строки ровно по 10 символов? Рассматривай эти 10 символов как 80-битное значение и сортируй по нему.

Дерево, у которого в каждом узле содержится массив указателей на символы слова. Забыл как оно называется.

Таких деревьев есть несколько видов. Trie ( https://en.wikipedia.org/wiki/Trie ), radix tree и т.п.

Для поиска подстрок за O(m), где m - длина ключа, используют (редко) еще и суффиксные деревья/суффиксные массивы. У них есть фича - размер индекса получается больше размера данных.

Ну и делать на них «поиск по регулярному выражению» будет скорее всего непросто.

На десятках мегабайт можно вообще не особо париться, даже перебор должен работать достаточно быстро

Здесь уже тонкости. Об этом подумал (и ещё раз подумал, когда предлагали, построение дополнительных структур для поиска). Косяк в том, что загрузка «не совсем тривиальный процесс», и привинчивать такую «предобработку налету» теперь целый квест.

Теоретики вашу мать. Цифр нет, кода нет, тестов нет - но надо оптимизировать.

KISS matherfakers

Кто ж знал что у него задача с помощью регуляро найти строки? ОП сам не сознавался, пока не спросили. Я то думал кто то опять задумал решить проблему поиска подстроки через регулярки.