Почему `s+ 'намного быстрее `чем` ss*' в этом регулярном выражении Perl?


почему замена s* (или даже ss*) С s+ привести к такому ускорению для этого ввода?

use Benchmark qw(:all);
$x=(" " x 100000) . "_n";
$count = 100;
timethese($count, {
    '/ss*n/' => sub { $x =~ /ss*n/ },
    '/s+n/' => sub { $x =~ /s+n/ },
});

ссылка на онлайн-версию

я заметил медленное регулярное выражение s/s*ns*/n/g в моем коде-когда дается входной файл 450KB, состоящий из множества пробелов с несколькими не-пробелами здесь и там, и финальной новой строкой в конце - регулярное выражение зависало и никогда не заканчивалось.

я интуитивно заменил регулярное выражение на s/s+n/n/g; s/ns+/n/g; и все стало что ж.

но почему это так быстро? После использования re Debug => "EXECUTE" я заметил s+ версия каким-то образом оптимизирована для запуска только в одной итерации:http://pastebin.com/0Ug6xPiQ

Matching REx "s*n" against "       _%n"
Matching stclass ANYOF{i}[x09x0ax0cx0d ][{non-utf8-latin1-all}{unicode_all}] against "       _%n" (9 bytes)
   0 <> <       _%n>         |  1:STAR(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   1 < > <      _%n>         |  1:STAR(3)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   2 <  > <     _%n>         |  1:STAR(3)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   3 <   > <    _%n>         |  1:STAR(3)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   4 <    > <   _%n>         |  1:STAR(3)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   5 <     > <  _%n>         |  1:STAR(3)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   6 <      > < _%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   8 <       _> <%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
   8 <       _> <%n>         |  3:  EXACT <n>(5)
   9 <       _%n> <>         |  5:  END(0)
Match successful!
Matching REx "s+n" against "       _%n"
Matching stclass SPACE against "       _" (8 bytes)
   0 <> <       _%n>         |  1:PLUS(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...

Я знаю, что Perl 5.10 + немедленно завершит регулярное выражение (без его запуска), если новая строка отсутствует. Я подозреваю, что он использует местоположение новой строки, чтобы уменьшить объем поиска, который он делает. Для всех случаев выше это, кажется, умно уменьшить отступление участвует (обычно /s*n/ против строки пробелов потребуется экспоненциальное время). Может ли кто-нибудь предложить понимание того, почему s+ версия намного быстрее?

также обратите внимание, что s*? не предлагает какого-либо ускорения.

4 56

4 ответа:

когда есть узел "плюс" (например \s+) в начале шаблона и узел не соответствует, механизм регулярных выражений пропускает вперед к точке отказа и пытается снова; с \s*, С другой стороны, движок продвигает только один символ за раз.

Ив Ортон прекрасно объясняет эту оптимизацию здесь:

оптимизация класса запуска имеет два режима: "попробуйте каждую допустимую стартовую позицию" (doevery) и " режим флип-флопа" (!doevery), где он пробует только первую допустимую стартовую позицию в последовательности.

рассмотреть вопрос о /(\Д+)х/ и строку "123456Y", теперь мы знаем, что если мы не в состоянии соответствовать X после согласования "123456", то мы также не матч за "23456" (при условии, что никакие злые трюки в месте, которое отключить оптимизацию в любом случае), поэтому мы знаем, что можем пропустить вперед до тех пор, пока /не/ и только потом начать искать реальный матч. Это режим триггера.

/\s+/ запускает режим триггера;/\s*/,/\s\s*/ и /\s\s+/ нет. Эта оптимизация не может быть применена к" звездным " узлам, таким как \s* потому что они могут соответствовать нулевым символам, поэтому сбой в одной точке последовательности не указывает на сбой позже в той же последовательности.


вы можете увидеть это в выходных данных отладки для каждого регулярного выражения. Я выделил пропущенные символы ^. Сравните это (пропускает четыре символа одновременно):

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d+x/'
   ...
   0 <> <123 456 78>         |  1:PLUS(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:PLUS(3)
      ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:PLUS(3)
         ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...

для этого (пропускает один или два символа одновременно):

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d*x/'
   ...
   0 <> <123 456 78>         |  1:STAR(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   1 <1> <23 456 789>        |  1:STAR(3)
      ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   2 <12> <3 456 789 >       |  1:STAR(3)
       ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:STAR(3)
        ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   5 <123 4> <56 789 x>      |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   6 <23 45> <6 789 x>       |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:STAR(3)
           ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   9 <23 456 7> <89 x>       |  1:STAR(3)
             ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
  10 <23 456 78> <9 x>       |  1:STAR(3)
              ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
  12 <23 456 789 > <x>       |  1:STAR(3)
               ^^
                                  POSIXD[\d] can match 0 times out of 2147483647...
  12 <23 456 789 > <x>       |  3:  EXACT <x>(5)
  13 <23 456 789 x> <>       |  5:  END(0)

обратите внимание, что оптимизация не применяется к /\s\s+/, потому что \s+ не находится в начале шаблона. Оба /\s\s+/ (логически эквивалентно /\s{2,}/) и /\s\s*/ (логически эквивалентно /\s+/), наверное может быть оптимизированы, хотя; это может иметь смысл спросить на perl5-porters будет ли это стоить усилий.


в случае, если вы заинтересованы, "режим триггера" включается путем установки PREGf_SKIP флаг на регулярном выражении при его компиляции. Смотрите код вокруг строк 7344 и 7405 в regcomp.c и строка 1585 в regexec.c в источнике 5.24.0.

во-первых, даже если полученное регулярное выражение не будет иметь того же значения, давайте уменьшим регулярные выражения до \s*0 и \s+0 и использовать (" " x 4) . "_0" в качестве входных данных. Для скептиков, вы можете видеть здесь что отставание все еще присутствует.

Теперь рассмотрим следующий код:

$x = (" " x 4) . "_ 0";
$x =~ /\s*0/; # The slow line 
$x =~ /\s+0/; # The fast line

копать немного с use re debugcolor; мы получаем следующий результат:

Guessing start of match in sv for REx "\s*0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
   0 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
   1 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 3 times out of 2147483647...
                                  failed...
   2 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 2 times out of 2147483647...
                                  failed...
   3 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 1 times out of 2147483647...
                                  failed...
   5 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 0 times out of 2147483647...
   5 <    _0>|  3:  EXACT <0>(5)
   6 <    _0>|  5:  END(0)
Match successful!

-----------------------

Guessing start of match in sv for REx "\s+0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes)
   0 <    _0>|  1:PLUS(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed

Perl кажется быть оптимизированы для отказа. Он будет сначала искать постоянные строки(которые потребляют только O (N)). Вот, он будет искать 0:Found floating substr "0" at offset 5...

затем он с переменная часть регулярного выражения, соответственно \s* и \s+, против всей минимальной строки для проверки:

Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes) # Only 5 bytes because there should be at least 1 "\s" char

после этого он будет искать первую позицию встречи stclass требование, здесь в положении 0.

  • \s*0:
    • начинается с 0, затем найдите 4 пробела провал;
    • начинается с 1, Найти 3 пробела, а затем не удается;
    • начинается с 2, найти 2 пробела, а затем не удается;
    • начинается с 3, найти 1 пробел, а затем не удается;
    • начинается с 4, Найти 0 пробелов, то не;
    • найти точное 0
  • \s+0:
    • начинается с 0, найти 4 пробела, а затем не удается. Поскольку минимальное количество пробелов не совпадает, регулярное выражение не выполняется немедленно.

если вы хотите получить удовольствие от оптимизации регулярных выражений Perl, вы можете рассмотреть следующие регулярные выражения / *\n и / * \n. На первый взгляд они выглядят одинаково, имеют одинаковый смысл... Но если вы запустите его против (" " x 40000) . "_\n" первый будет проверять все возможности, а второй будет искать " \n" и сразу фейл.

в ванильном, неоптимизированном движке регулярных выражений, оба регулярных выражения могут вызвать катастрофическое отступление, так как они должны повторить шаблон, как он натыкается вдоль. Однако, в приведенном выше примере, второй не удастся с Perl, потому что он был оптимизирован, чтобы find floating substr "0%n"


вы можете увидеть другой пример на блог Джеффа Этвуда.

обратите внимание также, что вопрос не о \s рассмотрение, но любой шаблон, где xx* вместо x+ посмотреть пример с 0s и регулярное выражение взрывчатого вещества кванторы

С таким коротким примером поведение "находимо", но если вы начинаете играть со сложными шаблонами, это далеко не легко обнаружить, например: регулярное выражение зависает программа (100% загрузка ЦП)

The \s+\n требуется, чтобы символ, предшествующий \n это SPACE.

по данным use re qw(debug) компиляция устанавливает, что ей нужна прямая строка из известного числа пробелов, вплоть до подстроки \n, который сначала проверяется на входе. Затем он проверяет подстроку только с фиксированной длиной по отношению к оставшейся части ввода, терпя неудачу, когда дело доходит до _. Это единственная возможность проверить, независимо от того, сколько пространства на входе. (Когда есть больше _\n каждый из них находится в состоянии сбоя одинаково непосредственно, на отладочный вывод.)

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

С \s*\n это не так. После того, как \n найден, и предыдущий символ не является пробелом, поиск не завершился неудачей так как \s* ничего не позволяет (ноль символов). Также нет подстрок фиксированной длины, и это в игре с обратным отслеживанием.

Я не уверен во внутренних компонентах механизма регулярных выражений, но похоже, что он не признает это \s+ в некотором роде тот же как \s\s*, так как во втором он соответствует пространству, а затем пытается соответствовать постоянно растущему числу пространств, в то время как в первом он сразу же приходит к выводу, что совпадения нет.

выход через use re qw( Debug ); ясно показывает это, используя гораздо короче строка:

test_re.pl

#!/usr/bin/env perl
use re qw(debug);

$x=(" " x 10) . "_\n";
print '-'x50 . "\n";
$x =~ /\s+\n/;
print '-'x50 . "\n";
$x =~ /\s\s*\n/;
print '-'x50 . "\n";

выход

Compiling REx "\s+\n"
Final program:
    1: PLUS (3)
    2:   SPACE (0)
    3: EXACT <\n> (5)
    5: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2
Compiling REx "\s\s*\n"
Final program:
    1: SPACE (2)
    2: STAR (4)
    3:   SPACE (0)
    4: EXACT <\n> (6)
    6: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2
--------------------------------------------------
Guessing start of match in sv for REx "\s+\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:PLUS(3)
                                  SPACE can match 10 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Guessing start of match in sv for REx "\s\s*\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s\s*\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:SPACE(2)
   1 < > <         _>        |  2:STAR(4)
                                  SPACE can match 9 times out of 2147483647...
                                  failed...
   1 < > <         _>        |  1:SPACE(2)
   2 <  > <        _>        |  2:STAR(4)
                                  SPACE can match 8 times out of 2147483647...
                                  failed...
   2 <  > <        _>        |  1:SPACE(2)
   3 <   > <       _%n>      |  2:STAR(4)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   3 <   > <       _%n>      |  1:SPACE(2)
   4 <    > <      _%n>      |  2:STAR(4)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   4 <    > <      _%n>      |  1:SPACE(2)
   5 <     > <     _%n>      |  2:STAR(4)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   5 <     > <     _%n>      |  1:SPACE(2)
   6 <      > <    _%n>      |  2:STAR(4)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   6 <      > <    _%n>      |  1:SPACE(2)
   7 <       > <   _%n>      |  2:STAR(4)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   7 <       > <   _%n>      |  1:SPACE(2)
   8 <        > <  _%n>      |  2:STAR(4)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   8 <        > <  _%n>      |  1:SPACE(2)
   9 <         > < _%n>      |  2:STAR(4)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   9 <         > < _%n>      |  1:SPACE(2)
  10 <          > <_%n>      |  2:STAR(4)
                                  SPACE can match 0 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Freeing REx: "\s+\n"
Freeing REx: "\s\s*\n"