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

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

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

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

6 ответов

Решение

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

Это:

$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//оптимизатор должен отсканировать большую часть строки перед тем, как отклонить совпадение, в то время как объединенное регулярное выражение сопоставляется быстро.

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

Как чередование регулярных выражений реализовано в 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), если есть проблемы или вы хотите улучшения. Но, как правило, изменения должны быть сведены к минимуму и по возможности избегаться, поскольку:

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

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

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

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

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

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, который работает медленнее, но мощнее, чем SFA. NFA возвращается (особенно с изменениями) и имеет экспоненциальное время выполнения в худшем случае. DFA имеет линейное время выполнения. Для ваших шаблонов не нужен механизм NFA, поэтому вы можете очень легко использовать свои регулярные выражения в механизме DFA, например sed.

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

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

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

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

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

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

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

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

Другие вопросы по тегам