nawracaniem w regexp szybszego niż oczekiwano

Question

Według perlre poniższy kod powinien trwać kilka sekund, aby wykonać:

$ time perl -E '$_="((()" . ("a") x 18; say "ok" if m{ \(([^()]+|\([^()]* \))+\)}x;' 

real 0m0.006s 
user 0m0.000s 
sys 0m0.005s 

Dokumentacja mówi:

Zastanów się, jak wyżej wzór wykrywa no-mecz na ((()aaaaaaaaaaaaaaaaaa w kilka sekund, ale tym razem każdy kolejny list podwaja się tym razem.

Jak widać, to trwa tylko ułamek sekundy na moim laptopie .. Nawet działa z milionów a „s kończy się w pół sekundy:

$ time perl -E '$_="((()" . ("a") x 1000000; say "ok" if m{ \(([^()]+|\([^()]* \))+\)}x;' 

real 0m0.454s 
user 0m0.446s 
sys 0m0.008s 

Co ja tu brakuje?

Answer 1

Jednym z trików, które możesz zrobić, aby dowiedzieć się, co silnik regex robi, jest:

use re 'debug'; 

Np

use strict; 
use warnings; 
use re 'debug'; 

my $str = "a" x 18; 

$str =~ m{ \(([^()]+|\([^()]* \))+\)}x; 

ten będzie następnie wydrukować co silnik regex jest rzeczywiście robi :

Compiling REx " \(([^()]+|\([^()]* \))+\)" 
Final program: 
    1: EXACT <(> (3) 
    3: CURLYX[0] {1,32767} (40) 
    5: OPEN1 (7) 
    7:  BRANCH (20) 
    8:  PLUS (37) 
    9:   ANYOF[^()][{above_bitmap_all}] (0) 
    20:  BRANCH (FAIL) 
    21:  EXACT <(> (23) 
    23:  STAR (35) 
    24:   ANYOF[^()][{above_bitmap_all}] (0) 
    35:  EXACT <)> (37) 
    37: CLOSE1 (39) 
    39: WHILEM[1/3] (0) 
    40: NOTHING (41) 
    41: EXACT <)> (43) 
    43: END (0) 
anchored "(" at 0 floating ")" at 2..2147483647 (checking floating) minlen 3 
Matching REx " \(([^()]+|\([^()]* \))+\)" against "aaaaaaaaaaaaaaaaaa" 
Intuit: trying to determine minimum start position... 
    doing 'check' fbm scan, [2..18] gave -1 
    Did not find floating substr ")"... 
Match rejected by optimizer 
Freeing REx: " \(([^()]+|\([^()]* \))+\)" 

Jeśli dodasz nawiasy z powrotem, otrzymasz inny wynik - otrzymam około 2000 kroków do przetworzenia wyrażenia regularnego. Wydłuża się to z każdą kolejną literą - około 300 kroków.

Powiedziałbym, że tak - ma miejsce katastroficzne cofanie, ale można również stwierdzić, że te procesory (i optymalizacje silnika wyrażeń regularnych) oznaczają, że czas jest znacznie krótszy.

use strict; 
use warnings; 
use re 'debug'; 

my $str = "((()"."a" x 100_000; 
$str =~ m{ \(([^()]+|\([^()]* \))+\)}x; 

Działa znacznie dłużej - ale co najmniej część z nich polega na tym, że drukowanie tekstu na ekranie jest stosunkowo "drogie".

Moje badanie sugeruje (liczbę „a” S)

10 : 1221 lines of output (broadly correlated with regex steps) 
11 : 1324 (+103) 
12 : 1467 (+143) 
13 : 1590 (+129) 
14 : 1728 (+138) 
15 : 1852 (+124) 

20 : 2630 (approx +155/extra) 
30 : 4536 (+190/extra) 
40 : 6940 (+240/extra) 
50 : 9846 (+290/extra) 

100 - 31,846 (+440/extra letter) 

Więc na pewno wygląda wykładniczy zachowanie dzieje - ale w żadnym przypadku, czas przetwarzania jest nadal dość szybko, co bym przypisują szybsze cpus (i być może lepsza optymalizacja silnika regex)

Answer 2

Zastanów się, jak powyższy wzór wykrywa brak dopasowania na ((()aaaaaaaaaaaaaaaaaa w kilka sekund.

To zdanie powstało co najmniej w kwietniu 2001 roku, kiedy został wydany plik perl 5.6.1. Możesz zobaczyć stronę perlre man dla tego wydania pod adresem search.cpan.org/~gsar/perl-5.6.1/pod/perlre.pod.

To może być lekcja, której można się nauczyć w dokumentacji oprogramowania. Uważaj na to, co piszesz, ponieważ twoje pisemne słowa pozostaną niezmienione pomimo wielu lat ulepszeń i wielokrotnych rozwidleń przez innych.