Backtracking in regexp schneller als erwartet

Question

Nach perlre sollte der folgende Code kann einige Sekunden dauern, auszuführen:

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

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

Die Dokumentation sagt:

Überlegen Sie, wie das Muster oben auf No-Match erkennt ((()aaaaaaaaaaaaaaaaaa in einigen Sekunden, aber dass jeder zusätzliche Brief diese Zeit verdoppelt.

Wie zu sehen ist, ist es nur einen Bruchteil einer Sekunde auf meinem Laptop nimmt .. Selbst mit einer Million a läuft ‚s vervollständigt in einer halben Sekunde:

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

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

Was soll ich hier fehlt?

Answer 1

Einer der Tricks, die Sie tun können, um herauszufinden, was die Regex-Engine tut, ist:

use re 'debug'; 

ZB:

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

my $str = "a" x 18; 

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

Dies wird dann drucken, was die Regex-Engine tatsächlich tut :

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: " \(([^()]+|\([^()]* \))+\)" 

Wenn Sie Ihre Klammern zurück in hinzufügen, können Sie ein anderes Ergebnis bekommen - ich um 2000 Schritte erhalten um die Regex zu verarbeiten. Dies wird mit jedem weiteren Buchstaben länger - etwa 300 Schritte.

Also würde ich sagen ja - katastrophale Backtracking ist im Gange, aber Sie können durchaus feststellen, dass Prozessoren (und Regex-Engine-Optimierungen) bedeuten, dass die Zeit erheblich kürzer ist.

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

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

Läuft deutlich länger - aber zumindest ein Teil davon ist, weil Druck von Text auf den Bildschirm vergleichsweise eigentlich recht ‚teuer‘ ist.

Mein Test schlägt vor (Anzahl der „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) 

So sieht sicher wie exponentielles Verhalten geht - aber in keinem Fall ist die Bearbeitungszeit immer noch ziemlich schnell, was ich zuschreiben würde zu schnellerer CPUs (und vielleicht ein bessere Optimierung der Regex-Engine)

Answer 2

überlegen Sie, wie das Muster auf ((()aaaaaaaaaaaaaaaaaa in mehreren Sekunden kein-Spiel oben erkennt.

Dieser Satz stammt aus mindestens April 2001, als Perl 5.6.1 veröffentlicht wurde. Sie können die perlre man-Seite für diese Version unter search.cpan.org/~gsar/perl-5.6.1/pod/perlre.pod einsehen.

Dies ist vielleicht eine Lektion, die hier in der Dokumentation von Software gelernt werden muss. Sei vorsichtig, was du schreibst, denn deine geschriebenen Worte bleiben trotz jahrelanger Verbesserungen und mehrerer Gabeln anderer unverändert.