regex - содержит - регулярные выражения примеры



Почему добавление еще одной альтернативы делает мое регулярное выражение более чем в 600 раз медленнее? (1)

Долгое время оптимизация TRIE perl не применялась, когда начальная компиляция регулярного выражения создавала longjmp вместо jmp (я думаю) инструкций (который зависит от количества чередований и общей длины задействованных строк и что еще ( ранее?) в регулярном выражении).

См. Разницу между:

perl -we'use re "debug"; qr/@{[join"|","a".."afhd"]}/'

а также

perl -we'use re "debug"; qr/@{[join"|","a".."afhe"]}/'

Вы можете разбить свое чередование на более мелкие куски и предварительно скомпилировать их отдельно и, например, (??{$rxa})|(??{$rxb})|(??{$rxc}) .

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

В принципе, я создаю регулярное выражение следующим образом:

my $regex = join "|", map quotemeta, @prefixes;
$regex = qr/^($regex)/;   # anchor the regex and precompile it

Здесь, в первоначальном тестировании, @prefixes состоит из шестнадцатеричных строк с 32 символами. Я обнаружил, что все работает красиво и плавно до 6552 префиксов - но как только я попробовал 6 553, время исполнения скрипта подскочило более чем на 25 (от 1,8 секунды до 51 секунды)!

Я играл с ним и построил следующий ориентир. Первоначально я использовал 32-символьные шестнадцатеричные строки, как в моей исходной программе, но обнаружил, что если бы я сократил длину строк до всего лишь 8 символов, пороговое значение переместилось выше - до 16383, по сути, в то время как коэффициент замедления резко увеличился еще выше: регулярное выражение с 16383 альтернативами почти в 650 раз медленнее, чем у только с 16382!

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(timethese cmpthese);

my $count = shift || 10;

our @items = map unpack("H8", pack "V", $_), 0..99999;

our $nA = 16382; our $reA = join "|", @items[1 .. $nA];
our $nB = 16383; our $reB = join "|", @items[1 .. $nB];

$_ = qr/^($_)/ for $reA, $reB;  # anchor and compile regex

my $results = timethese( $count, {
    $nA => q{ our (@items, $nA, $reA); $nA == grep /$reA/, @items or die; },
    $nB => q{ our (@items, $nB, $reB); $nB == grep /$reB/, @items or die; },
} );
cmpthese( $results );

Ниже приведены результаты выполнения этого теста на моем ноутбуке с использованием Perl (v5.18.2):

Benchmark: timing 10 iterations of 16382, 16383...
     16382:  2 wallclock secs ( 1.79 usr +  0.00 sys =  1.79 CPU) @  5.59/s (n=10)
     16383: 1163 wallclock secs (1157.28 usr +  2.70 sys = 1159.98 CPU) @  0.01/s (n=10)
      s/iter  16383  16382
16383    116     --  -100%
16382  0.179 64703%     --

Обратите внимание на разницу в скорости 64,703%.

Моя первоначальная догадка, основанная на численном совпадении 6553 ≈ 2 16/10, заключалась в том, что это могло быть своего рода произвольным пределом внутри движка регулярных выражений Perl, или, может быть, там может быть какой-то массив из 10 -byte, которые были ограничены до 64 кБ или что-то в этом роде. Но тот факт, что пороговое число альтернатив зависит от их длины, делает вещи более запутанными.

(С другой стороны, это явно не только длина регулярного выражения: исходное регулярное выражение с 6553 32-байтовыми альтернативами было 2 + 6 553 × 33 = 216,251 байта, а одно с 16383 8-байтными альтернативами 2 + 16,383 × 9 = 147,450 байт.)

Что вызывает этот странный прыжок в времени согласования регулярных выражений и почему это происходит в этой конкретной точке?





perl