sub { $x =~ /\s\s*\n/ }, '/\s+\n/' => sub { $x =~ /\s+\n/" />

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

regex perl regex-greedy

3917 просмотра

4 ответа

42751 Репутация автора

Почему замена \s*(или даже \s\s*) \s+результатом такого ускорения для этого ввода?

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

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

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

Я интуитивно заменил регулярное выражение на s/\s+\n/\n/g; s/\n\s+/\n/g;и все было хорошо.

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

Matching REx "\s*\n" against "       _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{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*?не предлагает никакого ускорения.

Автор: rjh Источник Размещён: 18.07.2016 08:28

Ответы (4)


7 плюса

5575 Репутация автора

Я не уверен , внутренности регулярных выражений, но похоже , что он не понимает , что \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"
Автор: xxfelixxx Размещён: 18.07.2016 08:57

28 плюса

23668 Репутация автора

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

Автор: Thomas Ayoub Размещён: 18.07.2016 09:24

14 плюса

41680 Репутация автора

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

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

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

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

Автор: zdim Размещён: 18.07.2016 09:38

20 плюса

19768 Репутация автора

Решение

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

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

Оптимизация начального класса имеет два режима: «пробовать каждую действительную стартовую позицию» (doevery) и «триггерный режим» (! Doevery), где он пробует только первую действительную стартовую позицию в последовательности.

Рассмотрим / (\ d +) X / и строку «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-переносчиков, стоит ли того или другого.


В случае, если вам интересно, «режим триггера» активируется установкой PREGf_SKIPфлага в регулярном выражении при его компиляции. См. Код в строках 7344 и 7405 в regcomp.c и строку 1585 в regexec.c в источнике 5.24.0.

Автор: ThisSuitIsBlackNot Размещён: 21.07.2016 04:54
Вопросы из категории :
32x32