соответствие подстроки быстрее с регулярным выражением?
Читая на RE/NFA и DFA, кажется, что нахождение подстроки в строке могло бы на самом деле асимптотически быстрее использовать РЕ, а не грубая сила O (млн) находят. Мое обоснование состоит в том, что DFA на самом деле поддержал бы состояние и постарался бы не обрабатывать каждый символ в "стоге сена" несколько раз. Следовательно, поиски в длинных строках могут на самом деле быть намного быстрее, если сделано с регулярными выражениями.
Конечно, это допустимо только для РЕ matchers, которые преобразовывают от NFA до DFA.
Кто-либо испытал лучшую строковую производительность соответствия в реальной жизни при использовании РЕ, а не грубой силы matcher?
3 ответа
Прежде всего, я бы рекомендовал вам прочитать статью о внутреннем устройстве регулярных выражений в нескольких языках: Regular Expression Matching Can Be Simple And Fast.
Поскольку регулярные выражения во многих языках предназначены не только для сопоставления, но и предоставляют возможность группового захвата и обратной ссылки, почти все реализации используют так называемый "обратный путь" при выполнении NFA, построенного на основе заданного регулярного выражения. И эта реализация имеет экспоненциальную временную сложность (в худшем случае).
Возможна реализация RE через DFA (с захватом группы), но она имеет накладные расходы (см. статью Лаурикари NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions).
Для простого поиска подстроки можно использовать алгоритм Knuth-Morris-Pratt, который строит DFA для поиска подстроки и имеет оптимальную сложность O(len(s)). Но он также имеет накладные расходы, и если вы протестируете наивный подход (O(nm)) против этого оптимального алгоритма на реальных словах и фразах (которые не так часто повторяются), вы можете обнаружить, что наивный подход в среднем лучше.
Для точного поиска подстроки вы также можете попробовать алгоритм Boyer-Moore, который имеет сложность O(mn) в худшем случае, но в среднем работает лучше, чем KMP на реальных данных.
Большинство регулярных выражений, используемых на практике, являются PCRE (Perl-совместимые регулярные выражения), которые шире регулярного языка и поэтому не могут быть выражены с помощью регулярной грамматики. В PCRE есть такие вещи, как положительные/отрицательные утверждения lookahead/lookbehind и даже рекурсия, поэтому при разборе может потребоваться обработка некоторых символов более одного раза. Конечно, все сводится к конкретной реализации RE: оптимизирована ли она, если выражения остаются в пределах регулярной грамматики, или нет.
Лично я не проводил никаких сравнений производительности между этими двумя системами. Однако, по моему опыту, у меня никогда не было проблем с производительностью при поиске и замене грубой силой, в то время как с узкими местами в производительности RE мне приходилось сталкиваться неоднократно.
Если вы посмотрите документацию по большинству языков, в ней будет упоминаться, что если вам не нужно использовать регулярное выражение, вы должны использовать версию без регулярного выражения из соображений производительности ... Пример: http: //www.php. net / manual / en / function.preg-split.php утверждает: «Если вам не нужна мощь регулярных выражений, вы можете выбрать более быстрые (хотя и более простые) альтернативы, такие как explode () или str_split ()».
Это компромисс, который существует повсюду. Чем более гибким и многофункциональным является решение, тем хуже его производительность.