regexp-geschwindigkeit

[seth_not@home]

gudn tach!

klaert mich bitte mal auf - welcher ausdruck wuerde denn nach der theorie von
   einer regex-engine performanter verarbeitet werden - der von mir ueberarbeitete,
   oder seths dahingeperlter - (/^(?:2(?:5[0-5]|[0-4]\d)|(?:1\d|[1-9])?\d)$/) - und
   vor allem, warum?

puh, also das kommt sehr darauf an, wie die strings aussehen, auf welche die ausdruecke losgelassen werden.

ein regexp-parser arbeitet den ausdruck von links nach rechts ab, und schaut jeweils, ob's passt. der string wird ebenfalls von links nach rechts abgearbeitet; wobei wird dort u.u. wieder an den anfang des strings gesprungen. ebenso kann beim regexp durch backtracking (siehe z.b. wikipedia) gesprungen werden.

am bsp. wird's klarer:
string = "7":

regexp = /^[0-9]$|^[1-9][0-9]$|^1[0-9][0-9]$|^2[0-4][0-9]$|^25[0-5]$/

^     matcht den anfang
  [0-9] matcht 7
  $     matcht das ende
  fertig

das gleiche in umgekehrter reihenfolge, also
regexp = /^25[0-5]$|^2[0-4][0-9]$|^1[0-9][0-9]$|^[1-9][0-9]$|^[0-9]$/

^       matcht den anfang
  2       matcht nicht
  5[0-5]$ erst recht nicht
  |       vergesse bisher gematchtes
  ^       matcht den anfang
  2       usw.
  usw.  bis halt irgendwann...
  ^       matcht den anfang
  [0-9]   matcht die 7
  $       matcht das ende
  endlich fertig

und jetzt meins:
regexp = /^(?:2(?:5[0-5]|[0-4]\d)|(?:1\d|[1-9])?\d)$/

^       matcht den anfang
  2       matcht nicht
  |       vergiss die "2", veraendere den pointer im string aber nicht
  1       matcht nicht
  |
  [0-9]   matcht 7
  ?       wird vorerst ignoriert, aber falls spaeter etwas nicht gematcht wird, wird gebacktracked
  \d      matcht nicht!
          backtracking (gematchte '7' wird vergessen)
  \d      matcht '7'
  $       matcht das ende
  endlich fertig

so in etwa.

das backtracking frisst sehr viel zeit. sieht man auch beim benchmarking:

#!/usr/bin/perl  
use strict;  
use Benchmark qw(:all) ;  
my $s = '7';  
my $results = timethese(5_000_000, {  
  'schnell' => sub{$s=~/^[0-9]$|^[1-9][0-9]$|^1[0-9][0-9]$|^2[0-4][0-9]$|^25[0-5]$/;},  
  'lahm'    => sub{$s=~/^25[0-5]$|^2[0-4][0-9]$|^1[0-9][0-9]$|^[1-9][0-9]$|^[0-9]$/;},  
  'seth'    => sub{$s=~/^(?:2(?:5[0-5]|[0-4]\d)|(?:1\d|[1-9])?\d)$/;},  
  'seth2'   => sub{$s=~/^(?:2(?:5[0-5]|[0-4]\d)|(?:1\d|[1-9])\d|\d)$/;},  
 },'none'  
);  
cmpthese($results);

fuehrt bei mir zu
("7")
             Rate    seth    lahm   seth2 schnell
seth    1016260/s      --    -34%    -42%    -59%
lahm    1533742/s     51%      --    -12%    -38%
seth2   1742160/s     71%     14%      --    -30%
schnell 2487562/s    145%     62%     43%      --

ist natuerlich relativ ungenau, aber nicht zu sehr.
hier spiegelt sich in etwa das wieder, was ich oben beschrieben habe.
"seth2" ist derselbe ausdruck wie "seth" mit dem unterschied, dass das backtracking ansichtlich umgangen wird.

bei einem laengeren string dagegen, also z.b. "250", waere "schnell" lahm und "lahm" schnell:

("250")
            Rate schnell    seth    lahm   seth2
schnell 1445087/s      --    -20%    -27%    -33%
seth    1798561/s     24%      --     -9%    -16%
lahm    1968504/s     36%      9%      --     -8%
seth2   2145923/s     48%     19%      9%      --

da hier backtracking gar nicht noetig waere, waere "schnell" sogar der lahmste, wobei die unterschiede hier nicht ganz so gross waeren.

sorry, dass ich's nur so grob erklaert habe, auf papier waer's einfacher und wuerde nicht so viel arbeit machen. ;-)

prost
seth