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

Если писать недумавши, то и асм станет медленным.

patricia trie

От перебора в общем случае не уйти. Но сам по себе поиск по регулярке можно и нужно соптимизировать, - парсить регулярку один раз, а затем использовать её прекомпилированную миллион раз.

Подстрока, которую ты ищешь произвольной длины?

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

если по немеренному фиксированному массиву многократно идёт поиск разными регулярками, то в теории: во первых заранее сократить диапазон символов (по 8-ми битным кодам поиск существенно быстрее чем по 16-ти и сильно-сильно быстрее чем по utf8), далее тестить разные либы на производительность :-) в комплекте perl`pcre, posix`regexp + в сети есть либы от yandex и google (нестандартные).

Для ограниченного набора фич можно теребить студентов в Job - построение различных FA по регулярке входит в обязательную программу CS.

кстати можно и параллелить на треды-ядра и хосты-ноды

Спасибо.

Ага.

Да.

На правах студента разберусь сам =-) Скажи, что такое FA?

FA - finite automat, он же КА - конечный автомат. Для posix re строится обычно классический автомат с таблицей переходов и состояний, для perl - стековый автомат.

Понятно, спасибо.

обычно его называют FSM

Царя еще не привозили с палаты? Он как-то про регулярки спрашивал и рассказывал как все круто можно без их сделать.

Тут многое зависит то того, как часто это нужно делать и как часто меняются поисковое условие и список.

Можно ссылку?

Список фиксирован. Условие меняется неуправляемо при каждом запросе.