Является ли регулярное выражение в perl быстрее, чем на Java или других языках?

Ответ 1

Почему вы считаете скорость двух движков, когда одна из них (Java) заметно глючит? (Ищите записи Тома "tchrist" Christiansen по этому вопросу.) Например, \s не соответствует многим пробелам.

Кроме того, некоторые онлайн-документы также говорят, что Perl имеет преимущества, когда дело доходит до обработки регулярных выражений.

Вот некоторые из них:

• Есть много функций, которые вы не можете найти в других механизмах, потому что другие двигатели еще не скопировали их или потому, что их дизайн не позволяет им поддерживать эти функции.
• Высокая оптимизация. Многие из этих оптимизаций помогают сообщать о неудачных совпадениях раньше, что не покрывается многими критериями.
• Лидер в поддержке Unicode. Эта поддержка настолько продвинута, что наши разработчики находят проблемы со стандартом Unicode и работают над их устранением.
• Замечательная ошибка.

Ответ 2

Вы можете взглянуть на этот тест. В таблице столбец patmch:1t указывает время сопоставления URL с /([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/?[^ ]*)/, а столбец patmch:2t - на соответствие URL-адресу или электронной почте с помощью /([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/?[^ ]*)|([^ @]+)@([^ @]+)/ (обратите внимание на оператор |). Для первого шаблона Perl примерно на 10 раз быстрее, чем Java; для второго они примерно одинаковы.

В общем, Perl использует механизм регулярного выражения backtrack. Такой движок является гибким, простым в использовании и очень быстрым в подмножестве регулярных выражений. Однако для других типов регулярных выражений, например, когда есть оператор |, он может стать очень медленным. В крайнем случае скорость его совпадения экспоненциальна по длине рисунка. Другой тип регулярного выражения основан на NFA. Это сложнее реализовать, но имеет стабильную производительность (квадратичную в худшем случае IIRC) для всех типов ввода. Russ Cox несколько статей об этих темах, которые мне очень нравятся.

Я не знаю, какие типы ядро ​​regex использует Java, но из эталона его производительность не кажется впечатляющей. Вы также можете быть заинтересованы в этом тесте, который оценивает несколько библиотек C/С++ в regex.

EDIT: в обоих тестах шаблоны тестируются на старой версии Linux Howto. Подавляющее большинство линий не имеют соответствия.

О DFA vs. NFA: если я прав, чистый DFA не может захватить группы, по крайней мере, не так просто. Только NFA может захватывать группы. Я слышал, что RE2 преобразует локальную NFA в DFA для части регулярного выражения без захвата группы. Я не знаю, верно ли это.

В PCRE: PCRE имеет ту же проблему, что и Perl, - неэффективные заданные сложные чередования. Вы можете взглянуть на тест regex-dna из игры Benchmarks Computer Language. Версии с использованием PCRE намного медленнее, чем самая быстрая версия, использующая TCL (возможно, PCRE не использует trie?). V8, безусловно, является победителем в этом тесте, потому что не использует откат. IMO, для программистов на С++ лучшая библиотека регулярных выражений - RE2.

Ответ 3

Дело не в том, что Perl является или не быстрее Java (тесты тестов скажут вам), но эти регулярные выражения - это действительно (глубоко) часть самого языка. Просто пример, в Perl, не нужно загружать какой-либо модуль для использования регулярного выражения. См. соответствующий ответ

Ex. однострочный Perl в псевдотерминале (который печатает корневую оболочку):

perl -nE '/^root.*:([\/\w]+)$/ and say $1' /etc/passwd

Сколько строк вам нужно сделать на Java?

Perl является фактическим эталонным языком для регулярных выражений. Вот почему так много языков используют PCRE engine (что означает Perl Compatible Regular Expression)