Почему s / ^ \ s + | \ s + $ // g; намного медленнее, чем две отдельные замены? - PullRequest
Новая
       24

Почему s / ^ \ s + | \ s + $ // g; намного медленнее, чем две отдельные замены?

13 голосов
/ 22 февраля 2010

Запись Perl FAQ Как убрать пробел из начала / конца строки? утверждает, что с помощью 

s/^\s+|\s+$//g;

медленнее, чем в два этапа: 

s/^\s+//;
s/\s+$//;

Почему этот комбинированный оператор заметно медленнее, чем отдельные (для любой входной строки)?

Ответы [ 4 ]

12 голосов
/ 22 февраля 2010

Среда выполнения регулярных выражений Perl работает намного быстрее при работе с «фиксированными» или «привязанными» подстроками, а не с «плавающими» подстроками.Подстрока фиксируется, когда вы можете заблокировать ее в определенном месте в исходной строке.И '^' и '$' обеспечивают эту привязку.Однако, когда вы используете чередование '|', компилятор не распознает варианты как фиксированные, поэтому он использует менее оптимизированный код для сканирования всей строки.И в конце процесса поиск фиксированных строк дважды намного, намного быстрее, чем поиск плавающей строки один раз.Что касается сопутствующей заметки, то чтение regcomp.c в Perl заставит вас ослепнуть.

Обновление : вот некоторые дополнительные сведения.Вы можете запустить perl с флагом '-Dr', если вы скомпилировали его с поддержкой отладки, и он выведет данные компиляции регулярного выражения.Вот что вы получите: 

~# debugperl -Dr -e 's/^\s+//g'
Compiling REx `^\s+'
size 4 Got 36 bytes for offset annotations.
first at 2
synthetic stclass "ANYOF[\11\12\14\15 {unicode_all}]".
   1: BOL(2)
   2: PLUS(4)
   3:   SPACE(0)
   4: END(0)
stclass "ANYOF[\11\12\14\15 {unicode_all}]" anchored(BOL) minlen 1

# debugperl -Dr -e 's/^\s+|\s+$//g'
Compiling REx `^\s+|\s+$'
size 9 Got 76 bytes for offset annotations.

   1: BRANCH(5)
   2:   BOL(3)
   3:   PLUS(9)
   4:     SPACE(0)
   5: BRANCH(9)
   6:   PLUS(8)
   7:     SPACE(0)
   8:   EOL(9)
   9: END(0)
minlen 1

Обратите внимание на слово «якорь» в первом дампе.

9 голосов
/ 23 февраля 2010

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

use strict;
use warnings;
use Benchmark qw(cmpthese);

my $ws = "   \t\t\n";

for my $sz (1, 10, 100, 1000){
    my $str = $ws . ('Z' x $sz) . $ws;
    cmpthese(-2, {
        "alt_$sz" => sub { $_ = $str; s/^\s+|\s+$//g },
        "sep_$sz" => sub { $_ = $str; s/^\s+//; s/\s+$// },
    });
}

           Rate alt_1 sep_1
alt_1  870578/s    --  -16%
sep_1 1032017/s   19%    --

            Rate alt_10 sep_10
alt_10  384391/s     --   -62%
sep_10 1010017/s   163%     --

            Rate alt_100 sep_100
alt_100  61179/s      --    -92%
sep_100 806840/s   1219%      --

             Rate alt_1000 sep_1000
alt_1000   6612/s       --     -97%
sep_1000 261102/s    3849%       --
3 голосов
/ 22 февраля 2010

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

В этом случае объединенное регулярное выражение в целом не закреплено, поэтому оно может потенциально совпадать в любой точке строки, в то время как ^\s+ привязывается в начале, поэтому сопоставлять тривиально, а \s+$ закрепляется в конце и предоставляет отдельный класс символов для каждого символа от конца назад - хорошо оптимизированный движок распознает этот факт и сопоставит его в обратном порядке, что делает его таким же тривиальным, как ^\s+ совпадение на обратной стороне вход.

1 голос
/ 22 февраля 2010

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

Что вы подразумеваете под "заметно медленнее"?

...