Nichterminierende Regexp

[schalentier]

Folgendes Stueck Java funktioniert nicht:

public static void main(String[] args) {
    Pattern p = Pattern.compile("(aa|aab?)+");
    int count = 0;
    for (String s = ""; s.length() < 200; s += "a") {
        if (p.matcher(s).matches()) {
            count++;
        }
    }
    System.out.println(count);
}

Siehe http://www.java-forum.org/plauderecke/22639-java-quiz-71.html#post805970



Wieso klappt das problemlos mit Ruby?

count = 0
(0..199).each do |i|
   s = "a"*i
   # if s =~ /(aa|aab?)+/   -> liefert ab "aa" immer true
   res = s.match(/(aa|aab?)+/)
   if !res.nil? and res[0]==s
      count = count + 1
   end
end

puts count

> time ruby test.rb
99

real    0m0.151s
user    0m0.046s
sys     0m0.015s

 

[musiKk]

edit: Nach dem geänderten Anfangspost ergibt dieser hier keinen Sinn mehr.

 

[tfa]

Versteh ich nicht. Wieso soll das nicht klappen oder was soll denn sonst rauskommen?

Siehe: http://www.java-forum.org/plauderecke/22639-java-quiz-71.html#post805970

Keine Ahnung, warum Ruby das besser macht. Das hat vielleicht einen ausgefeilteren Regex-Algorithmus.

 

[musiKk]

Ok, der Link wäre oben ganz praktisch gewesen.

Perl machts auch gut (alles andere wäre aber sehr verwunderlich gewesen). Letztens hatte hier doch schonmal jemand einen regulären Ausdruck, der nicht terminieren wollte. Mein Vertrauen in die Regex-Engine von Java ist ziemlich erschüttert. Ich hatte auch einen äquivalenten Bug-Report bei Sun gefunden, der mit not a defect geschlossen wurde.

 

[schalentier]

Der Vollstaendigkeit halber, die Perl Version:

my $s="";
my $count = 0;
for my $i ( 0..199 ) {
   if( $s =~ m/^(aa|aab?)+$/ ){
      $count ++;
   }
   $s .= "a";
}

print $count;

>  time perl test.pl
99

real    0m0.119s
user    0m0.031s
sys     0m0.030s

 

[JohannisderKaeufer]

Wenn man zugrunde legt

wenn aa gilt, dann gilt auch aab?

aber nicht!:

wenn aab? gilt, dann gilt auch aa.

denn aab? ist nichts anderes als aa | aab.
somit wäre aa|aab? nichts anderes als aa| aa| aab.

Das doppelte aa zu erkennen dürfte nicht schwierig sein.

Wenn eine Regex-Implementierung diesen Zusammenhang bei einem "Oder" berücksichtigt. Dann kann es hingehen und das aa entfernen und nur noch nach aab? überprüfen.

Sprich, wenn Java das genauso Effizient machen wollte, wie Ruby oder Perl, dann müßte beim Aufruf von compile("(aa|aab?)+") mindestens das gleiche rauskommen wie ein equivalenter Aufruf von compile("(aab?)+").
Letzteres kann Java sehr gut verarbeiten. Die Komplexität dürfte bei O(n) = 2n liegen.

Ich kann mir also nur vorstellen, dass Ruby und Perl so eine Optimierung vornehmen.

In Java läuft "(aa|aab)+" auch schnell, "(aa|aa)+" hingegen langsam obwohl der zusammenhang zwischen aa und aa offensichtlich ist.