regex verbrät CPU

[spoi]

Hallo,

ich habe einen regulären Ausdruck geschrieben, der sowohl in regexpal, als auch in java prinzipiell funtioniert.

Ich nutze den Ausdruck wie folgt:

Pattern seRes = Pattern.compile("^ ...snip... $", Pattern.CASE_INSENSITIVE | Pattern.MULTILINE);
Matcher m = OrganicParser.seRes.matcher(inputString);
if(!m.find()) {
  // Fehlerbehandlung
}

Solange der inputString genau auf den Ausdruck matched ist alles fein. Wenn der inputString bsp. ein Zeichen länger ist, so das er nicht mehr matched blockiert der Aufruf von m.find() für immer...

Hat jemand eine Idee, woher das kommen kann?
Hat jemand eine Idee, wie ich das am besten Debuggen kann?

Gruß

 

[spoi]

DOH DOH DOH

Mein regex war schuld, da s*****e geschrieben.

Man sollte niemals so etwas schreiben:
((</?b>|[^<]+)+?)
weil folgendes ausreicht:
((</?b>|[^<])+?)

und erstere Variante zu viele kombinatorische Möglichkeiten zulässt, die die RegEx engine ausprobieren muss, bevor sie failen kann.
Wenn drei vier solcher Ausdrücke in einem RegEx vorhanden sind, kann das leicht länger dauern...

Gruß

 

[Spacerat]

Wow... wenn Grüne Fundamentalisten erfahren, wie man mit 'nem Pluszeichen Eier braten kann (auf der CPU ), bekommst bestimmt einen Umwelt-Nobelpreis.

 

[spoi]

Ich weiß jetzt nicht, was die grüne Anspielung soll. Es ging hier nicht um CPU Takte, sondern um CPU Stunden/Tage, die das Pluszeichen verursacht hat.
So gesehen ist mir der Umwelt-Nobelpreis egal, ich bin froh, dass die Anwendung damit funktioniert...

 

[Spacerat]

Okay, meine Gecks waren auch schon mal besser... Ich dachte da nur an saubere Pluszeichenenergie... nichts besonderes.

 

[Antoras]

und erstere Variante zu viele kombinatorische Möglichkeiten zulässt, die die RegEx engine ausprobieren muss, bevor sie failen kann.

Die Anzahl der Möglichkeiten wäre ziemlich egal, wenn die RegEx-Engine vernünftigerweise als deterministischer Automat implementiert wäre. Dann würden Mehrdeutigkeiten beim RegEx sogar noch wegoptimiert werden. Das Monster das momentan im JDK vorliegt gibt es aber leider auch in vielen anderen Programmiersprachen, z.B. Python, Perl oder Ruby und daran wird sich so schnell wohl auch nichts ändern.

 

[KingOfExceptions]

Wow... wenn Grüne Fundamentalisten erfahren, wie man mit 'nem Pluszeichen Eier braten kann (auf der CPU ), bekommst bestimmt einen Umwelt-Nobelpreis.

[OT]ich fand den gar nicht so schlecht ^^[/OT]