Быстрее ли использовать чередование, чем последующие замены в регулярных выражениях

У меня вполне прямой вопрос. Там, где я работаю, я вижу много регулярных выражений. Они используются в Perl для замены и/или удаления некоторых строк в тексте, например:

$string=~s/^.+\///;
$string=~s/\.shtml//;
$string=~s/^ph//;

Я понимаю, что вы не можете объединить первую и последнюю замену, потому что вы можете заменить ph только в начале строки после того, как вы сделали первую замену. Однако я бы объединил первое и второе регулярное выражение с чередованием: $string=~s/(^.+\/|\.shtml)//; Поскольку мы обрабатываем тысячи файлов (+500 000), мне было интересно, какой метод наиболее эффективен.

regex perl alternation

Bram Vanroy 05.04.2016 источник

comment

Нет, не опускайте тег языка, это важно. - Wiktor Stribiżew 05.04.2016

comment

@WiktorStribiżew Почему так, если этот вопрос касается всех типов регулярных выражений? - Bram Vanroy 05.04.2016

comment

Реализации регулярных выражений на разных языках ОЧЕНЬ разные. Использование ленивого сопоставления точек в .NET и PCRE приведет к различному падению производительности. Lookbehind с ограничительными квантификаторами в Java и .NET различаются способом анализа строки и шаблона. Итак, вам нужен совет экспертов по Perl. - Wiktor Stribiżew 05.04.2016

comment

Спасибо за объяснение. - Bram Vanroy 05.04.2016

comment

На самом деле это много зависит от данных. Я думаю, будет справедливо сказать, что в общем случае вы не можете позвонить. Крайние примеры. Если шаблон имеет много фиксированных строк, он может соответствовать чередованию за один проход или, по крайней мере, за несколько проходов. Если у вас есть фиксированные шаблоны в начале и в конце, лучше использовать отдельные. Если шаблон сложный, когда вы его разбиваете, вы можете переписать (под)шаблоны, чтобы свести к минимуму откат (снижение производительности). Если бы вы могли сузить спецификацию данных, это было бы иначе. Но эти микрооптимизации, конечно, дорого обходятся. - zdim 05.04.2016

comment

Ваше комбинированное регулярное выражение не эквивалентно: исходный код превращает foo/bar.shtml в bar; ваша версия превращает его в bar.shtml - ThisSuitIsBlackNot 14.04.2016

comment

В общем, я хочу сказать, что быстрее расставить приоритеты выражений в чередовании. За кулисами всех замен заключается в том, что при каждом запуске регулярного выражения создается новая строка. Быстрее ли создать только одну новую строку или создать три новые строки? Наверное, быстрее создать один новый. Также есть соображение, что сделав это один раз, одна и та же территория не проверяется повторно. - 15.04.2016

Ответы (6)

arrow_upward
10
arrow_downward

Ваши выражения не эквивалентны

Этот:

$string=~s/^.+\///;
$string=~s/\.shtml//;

заменяет текст .shtml и все до последней косой черты включительно.

Этот:

$string=~s/(^.+\/|\.shtml)//;

заменяет либо текст .shtml или все до последней косой черты включительно.

Это одна из проблем объединения регулярных выражений: одно сложное регулярное выражение сложнее написать, сложнее понять и сложнее отладить, чем несколько простых.

Наверное, неважно, что быстрее

Даже если ваши выражения были эквивалентны, использование одного или другого, вероятно, не оказало бы существенного влияния на скорость вашей программы. Операции в памяти, такие как s///, выполняются значительно быстрее, чем файловый ввод-вывод, и вы указали, что выполняете много файлового ввода-вывода.

Вы должны профилировать свое приложение с помощью чего-то вроде Devel::NYTProf, чтобы увидеть, действительно ли эти конкретные замены узкое место (я сомневаюсь, что они есть). Не тратьте время на оптимизацию того, что уже работает быстро.

Чередования мешают оптимизатору

Имейте в виду, что вы сравниваете яблоки и апельсины, но если вас все еще интересует производительность, вы можете посмотреть, как perl оценивает конкретное регулярное выражение, используя тег re прагма:

$ perl -Mre=debug -e'$_ = "foobar"; s/^.+\///; s/\.shtml//;'
...
Guessing start of match in sv for REx "^.+/" against "foobar"
Did not find floating substr "/"...
Match rejected by optimizer
Guessing start of match in sv for REx "\.shtml" against "foobar"
Did not find anchored substr ".shtml"...
Match rejected by optimizer
Freeing REx: "^.+/"
Freeing REx: "\.shtml"

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

С /^.+\// оптимизатор знает, что $string должен содержать хотя бы одну косую черту для соответствия; когда он не находит косых черт, он немедленно отклоняет совпадение, не вызывая полный механизм регулярных выражений. Аналогичная оптимизация происходит с /\.shtml/.

Вот что делает Perl с комбинированным регулярным выражением:

$ perl -Mre=debug -e'$_ = "foobar"; s/(?:^.+\/|\.shtml)//;'
...
Matching REx "(?:^.+/|\.shtml)" against "foobar"
   0 <> <foobar>             |  1:BRANCH(7)
   0 <> <foobar>             |  2:  BOL(3)
   0 <> <foobar>             |  3:  PLUS(5)
                                    REG_ANY can match 6 times out of 2147483647...
                                    failed...
   0 <> <foobar>             |  7:BRANCH(11)
   0 <> <foobar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   1 <f> <oobar>             |  1:BRANCH(7)
   1 <f> <oobar>             |  2:  BOL(3)
                                    failed...
   1 <f> <oobar>             |  7:BRANCH(11)
   1 <f> <oobar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   2 <fo> <obar>             |  1:BRANCH(7)
   2 <fo> <obar>             |  2:  BOL(3)
                                    failed...
   2 <fo> <obar>             |  7:BRANCH(11)
   2 <fo> <obar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   3 <foo> <bar>             |  1:BRANCH(7)
   3 <foo> <bar>             |  2:  BOL(3)
                                    failed...
   3 <foo> <bar>             |  7:BRANCH(11)
   3 <foo> <bar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   4 <foob> <ar>             |  1:BRANCH(7)
   4 <foob> <ar>             |  2:  BOL(3)
                                    failed...
   4 <foob> <ar>             |  7:BRANCH(11)
   4 <foob> <ar>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
   5 <fooba> <r>             |  1:BRANCH(7)
   5 <fooba> <r>             |  2:  BOL(3)
                                    failed...
   5 <fooba> <r>             |  7:BRANCH(11)
   5 <fooba> <r>             |  8:  EXACT <.shtml>(12)
                                    failed...
                                  BRANCH failed...
Match failed
Freeing REx: "(?:^.+/|\.shtml)"

Обратите внимание, насколько длиннее вывод. Из-за чередования оптимизатор не срабатывает и выполняется полный движок регулярных выражений. В худшем случае (нет совпадений) каждая часть чередования проверяется на соответствие каждому символу в строке. Это не очень эффективно.

Итак, чередования медленнее, верно? Нет потому что...

Это зависит от ваших данных

Опять же, мы сравниваем яблоки и апельсины, но с:

$string = 'a/really_long_string';

комбинированное регулярное выражение на самом деле может быть быстрее, потому что с s/\.shtml// оптимизатору приходится сканировать большую часть строки, прежде чем отклонить совпадение, в то время как комбинированное регулярное выражение сопоставляется быстро.

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

ThisSuitIsBlackNot 13.04.2016

arrow_upward
3
arrow_downward

Как чередование регулярных выражений реализовано в Perl, довольно хорошо объяснено в perldoc perlre

Соответствие тому или иному

Мы можем сопоставлять различные строки символов с помощью метасимвола чередования '|' . Чтобы соответствовать dog или cat, мы формируем регулярное выражение dog|cat. Как и раньше, Perl попытается сопоставить регулярное выражение с самой ранней возможной точкой строки. В каждой позиции символа Perl сначала попытается сопоставить первую альтернативу, dog. Если dog не совпадает, Perl попробует следующую альтернативу, cat. Если cat тоже не соответствует, то совпадение не выполняется, и Perl переходит к следующей позиции в строке. Некоторые примеры:
"cats and dogs" =~ /cat|dog|bird/;  # matches "cat"
"cats and dogs" =~ /dog|cat|bird/;  # matches "cat" 
Несмотря на то, что dog является первой альтернативой во втором регулярном выражении, cat может соответствовать более раннему варианту в строке.
"cats"          =~ /c|ca|cat|cats/; # matches "c"
"cats"          =~ /cats|cat|ca|c/; # matches "cats" 
Здесь все альтернативы совпадают в первой позиции строки, поэтому первая альтернатива является той, которая соответствует. Если некоторые из альтернатив являются усечениями других, поставьте самые длинные из них первыми, чтобы дать им шанс совпасть.
"cab" =~ /a|b|c/ # matches "c"
                 # /a|b|c/ == /[abc]/ 
Последний пример показывает, что классы символов подобны чередованию символов. В заданной позиции символа первая альтернатива, которая позволяет совпадению регулярного выражения быть успешным, будет той, которая соответствует.

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

Собирая простые регулярные выражения, вы не платите такую цену. Это хорошо объяснено в другом связанном вопросе в SO. При прямом поиске постоянной строки или набора символов, как в вопросе, можно выполнить оптимизацию, и не требуется откат, что означает потенциально более быстрый код.

При определении чередования регулярных выражений просто выбор хорошего порядка (сначала самые распространенные результаты) может повлиять на производительность. Это не то же самое, что выбирать между двумя вариантами или двадцатью. Как всегда, преждевременная оптимизация — корень всех зол, и вы должны инструментировать свой код (Devel::NYTProf), если есть проблемы или вы хотите улучшить. Но, как правило, чередование должно быть сведено к минимуму и по возможности его следует избегать, поскольку:

Они легко делают регулярное выражение слишком большим и сложным. Нам нравятся простые, легкие для понимания/отладки/обслуживания регулярные выражения.
Изменчивость и зависимость от ввода. Они могут стать неожиданным источником проблем, поскольку они откатываются и могут привести к неожиданному снижению производительности в зависимости от вашего ввода. Как я понимаю, нет случая, когда они будут быстрее.
Концептуально вы пытаетесь сопоставить две разные вещи, поэтому мы можем утверждать, что два разных утверждения более правильны и ясны, чем одно.

Надеюсь, этот ответ станет ближе к тому, что вы ожидали.

LaintalAy 13.04.2016

comment

Оптимизатор срабатывает как для $string=~s/^.+\///;, так и для $string=~s/\.shtml//; и немедленно отключается, если $string не содержит косых черт или .shtml соответственно. Это быстро, потому что выполнение никогда даже не доходит до полного механизма регулярных выражений. - ThisSuitIsBlackNot; 13.04.2016

arrow_upward
1
arrow_downward

Во-первых, измерьте различные варианты на ваших реальных данных, потому что никакая теория не сравнится с экспериментом (если его можно провести). На CPAN есть много модулей синхронизации, которые вам помогут.

Во-вторых, если вы решили оптимизировать регулярные выражения, не сжимайте их вручную в одного гигантского монстра, а попробуйте собрать «мастерское» регулярное выражение с помощью кода. В противном случае никто не сможет расшифровать код.

zoul 05.04.2016

comment

Не пытаюсь показаться грубым, но это больше похоже на комментарий, чем на ответ на вопрос, быстрее ли чередование, чем следующие замены. Я знаю, что могу проверить это сам, но у меня нет ни времени, ни ресурсов, чтобы поставить эксперимент. Я надеялся, что есть какой-то четкий ответ на вопрос о чередовании и множественных заменах. - Bram Vanroy; 05.04.2016

comment

Я не думаю, что вы можете получить лучший ответ, поэтому я не отправил это в качестве комментария. Производительность регулярных выражений сложна, потому что механизм регулярных выражений сильно оптимизирован для различных особых случаев. Тривиальные изменения часто могут привести к большим различиям в производительности. В общем случае на вопрос почти невозможно ответить. Что касается времени или ресурсов, необходимых для организации эксперимента, см. временные модули на CPAN, решение вашего конкретного случая должно быть тривиальным. - zoul; 05.04.2016

arrow_upward
1
arrow_downward

Комбинация — не лучший вариант

Если у вас есть три регулярных выражения, которые отлично работают, нет смысла их комбинировать. Их переписывание не только открывает двери для ошибок, но и программисту, и движку становится труднее читать регулярное выражение.

Эта страница предлагает вместо этого изменение, например:

while (<FILE>) {
    next if (/^(?:select|update|drop|insert|alter)\b/);     
    ...  
}

Вы должны использовать:

while (<FILE>) {
    next if (/^select/);
    next if (/^update/);
    ...
}

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

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

my $query = qr/foo$bar/; #compiles here
@matches = (  );
...
while (<FILE>) {
    push @matches, $_ if /$query/i;
}

Вы также можете оптимизировать файл .+. Он съест весь файл, а затем должен будет вернуться посимвольно, пока не найдет /, чтобы он мог соответствовать. Если в файле есть только один /, попробуйте использовать отрицательный класс символов, например: [^/] (экранированный: [^\/]). Где вы ожидаете найти / в вашем файле? Знание этого позволит вашему регулярному выражению стать быстрее.

Скорость замены зависит от других факторов

Если у вас есть проблемы с производительностью (в настоящее время с 3 регулярными выражениями), это может быть другая часть вашей программы. В то время как скорость обработки компьютеров выросла в геометрической прогрессии, скорость чтения и записи увеличилась незначительно.

Могут быть более быстрые движки для поиска и замены текста в файле

Perl использует NFA, который медленнее, но мощнее, чем механизм DFA sed. NFA откатывается назад (особенно с изменениями) и имеет экспоненциальное время выполнения в худшем случае. DFA имеет линейное время выполнения. Вашим шаблонам не нужен движок NFA, поэтому вы можете очень легко использовать свои регулярные выражения в движке DFA, таком как sed.

Согласно здесь sed может выполнять поиск и замену со скоростью 82,1 миллиона символов в секунду (обратите внимание, что в этом тесте записывалось /dev/null, поэтому скорость записи на жесткий диск на самом деле не имела значения).

Laurel 14.04.2016

comment

Из perlop: The bottom line is that using /o is almost never a good idea. Из perlre: o - pretend to optimize your code, but actually introduce bugs - tjd; 14.04.2016

comment

В Perl 5.6+ /$query/ перекомпилируется только в случае изменения $query, поэтому модификатор 'o' не нужен (и вводит побочные эффекты). Это происходит даже без использования qr. - ThisSuitIsBlackNot; 14.04.2016

comment

@ThisSuitIsBlackNot Я удалил часть модификатора o. Вместо этого я упоминаю предварительную компиляцию. Во многих вариантах предварительная компиляция БУДЕТ иметь определенное преимущество. В этом случае предварительная компиляция либо ничего не даст, либо принесет пользу, поэтому ее, вероятно, стоит сделать, потому что ее очень легко добавить. - Laurel; 14.04.2016

arrow_upward
0
arrow_downward

Возможно, немного не по теме, но если фактические замены редки, относительно количества comapares (10%-20%?), Вы можете увеличить скорость, используя сначала сопоставление индекса.

$string=~s/\.shtml//
    if index($string, ".shtml");

FtLie 16.04.2016

arrow_upward
-2
arrow_downward

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

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

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

mukesh bhoj 05.04.2016

Быстрее ли использовать чередование, чем последующие замены в регулярных выражениях

Ответы (6)

Ваши выражения не эквивалентны

Наверное, неважно, что быстрее

Чередования мешают оптимизатору

Это зависит от ваших данных

Комбинация — не лучший вариант

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

Скорость замены зависит от других факторов

Могут быть более быстрые движки для поиска и замены текста в файле

Похожие вопросы