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

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