Schlechte Leistung regulärer Ausdrücke?

Gepostet von Eyal Schneider am 21. Mai 2009 Das Paket java.util.regex wurde in Version 1.4 zu Java hinzugefügt. Es ist ein sehr mächtiges Werkzeug und man muss ein Meister werden, um es richtig zu verwenden. Selbst wenn ein regulärer Ausdruck wahr ist, kann er sehr langsam sein, wenn er nicht intelligent geschrieben ist. Lesen Sie weiter, wenn Sie die Ursache der Probleme verstehen möchten, oder scrollen Sie zum Ende der Seite, wo Sie 10 nützliche Tipps zur Verbesserung der Leistung regulärer Ausdrücke in Java finden.

Ist es wirklich so langsam?

Nehmen wir an, wir möchten nur Zeilen auswählen, die die Zeichenfolge „a“ und „b“ enthalten. Die richtige Lösung könnte sein: (a*b*)* Wenn Sie den Ausdruck jedoch beispielsweise mit der Zeichenfolge „aaaaaaaaaaaaaaaaaaaaaaaaaaaaax“ ausführen, dauert es mehrere Minuten, bis er abgeschlossen ist und keine Übereinstimmungen meldet! Der beste reguläre Ausdruck wäre in diesem Fall natürlich: (a|b)* Das dauert auf meinem Rechner mit dem gleichen String weniger als eine Millisekunde. Hier liegt eindeutig ein Leistungsproblem vor.

Warum passiert das?

Wie die meisten Regexp-Engines verwendet Java einen NFA-Ansatz (Non-Deterministic Finite Automata). Die Engine scannt die Regex-Komponenten nacheinander und geht die Eingabezeichenfolge entsprechend durch. Und er kann zum Anfang zurückkehren, um geeignete Alternativen zu finden, wenn er in eine „Sackgasse“ gerät. Alternative Ergebnisse werden durch die Verwendung regulärer Strukturen wie Quantoren ( *, +, ? ) und Alternationen (z. B. a|b|c|d ) erzielt. Diese Forschungstechnik wird Backtracking genannt. Im schrecklichen Beispiel oben durchsucht die Engine tatsächlich ALLE Serienzerlegungen des Symbols „a“ in kleinere Serien, bis sie erkennt, dass es keine Übereinstimmungen gibt. Dieses Beispiel zeigt, wie der Backtracking-Algorithmus zu einer exponentiellen Zeitschätzung führen kann (abhängig von der Länge der Eingabezeichenfolge). Dies zeigt auch eine wichtige Eigenschaft von NFA: Es wird immer schlimmste Fälle geben, die fast dem Muster entsprechen. Wenn eine Übereinstimmung gefunden wird, wird die Suche beendet. Der andere Hauptansatz zur Verwendung in Regex ist DFA (Deterministic Finite Automaton). Bei diesem Ansatz erstellt der reguläre Ausdruck tatsächlich einen Automaten, der verwendet wird, um die Eingabezeichenfolgen Zeichen für Zeichen ohne Rückverfolgung zu durchlaufen. Dadurch erhält die gesamte Eingabe lineare Zeit, unabhängig von der Komplexität des regulären Ausdrucks. Anstatt eine Zeichenfolge nacheinander nach Übereinstimmungen zu durchsuchen (wie in NFA), simuliert DFA ein paralleles Durchsuchen. Warum also verwendet Java (und .NET, Perl, Python, Ruby, PHP usw.) NKA und nicht DKA, das sich viel besser verhält? Der Grund dafür ist, dass NKA eine Reihe wesentlicher Vorteile hat:

Lässt sich schneller kompilieren und benötigt viel weniger Speicher
Ermöglicht einige nützliche Funktionen (Einzelheiten finden Sie im Tutorial von Sun ):

Gruppenerfassung und Backlinks
Positionskontrolle
Erweiterte Quantifizierer (Gierig und Faul)

Es ist wichtig zu beachten, dass die gängigen Begriffe NKA und DKA ungenau sind, wenn sie im Kontext regulärer Ausdrücke verwendet werden. Theoretisch verfügen diese beiden Modelle über die gleiche Rechenleistung. Das bedeutet, dass Sie in einem Automatenmodell keinen regulären Ausdruck schreiben können, der in einem anderen nicht ausgedrückt werden könnte. In der Praxis besteht ein Bedarf an mehr Fähigkeiten, damit die beiden Arten der Implementierung semantisch voneinander abweichen. NKA-Engines bieten mehr Flexibilität und sind DKA in der Rechenleistung überlegen. Aufgrund der Geschwindigkeit von DFA und der einzigartigen Funktionen von NFA gibt es zwei weitere „vorgefertigte“ Möglichkeiten, reguläre Ausdrücke zu implementieren. Einige Implementierungen verwenden beide Typen (z. B. GNU egrep, das zur Laufzeit eine bestimmte Engine auswählt), und einige haben es geschafft, eine wirklich hybride Version (z. B. Tcl regexps) mit allen Vorteilen zu implementieren.

Rat

Im Folgenden finden Sie einige Tipps, wie Sie Probleme mit der Regex-Effizienz in Java vermeiden können. Viele davon zielen darauf ab, die Rendite zu reduzieren.

1) Vorkompilierung

Banal, aber erwähnenswert. Wenn Sie den regulären Ausdruck mehr als einmal verwenden, kompilieren Sie ihn unbedingt vorher:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Lazy Quantifiers vs. Greedy Quantifiers

Standardmäßig sind Quantoren ( * + ? ) gierig. Das heißt, sie beginnen mit der längstmöglichen Sequenz und arbeiten dann bei Bedarf schrittweise zurück. Wenn Sie im Voraus wissen, dass die Übereinstimmungen normalerweise kurz sind, sollten Sie Lazy-Quantifizierer verwenden. Sie beginnen mit der kleinsten Übereinstimmung und gehen bei Bedarf weiter. Nehmen wir an, wir möchten nur Zeilen finden, die mit der Sequenz „Hallo“ übereinstimmen. Das reguläre .*hello.* macht alles richtig, aber wenn wir wissen, dass „hello“ normalerweise näher am Anfang des Textes erscheint, dann wird .*?hello.* im Durchschnitt schneller funktionieren.

3) Verwenden Sie nach Möglichkeit supergierige Quantoren

Im Gegensatz zu Lazy-Quantoren, die sich auf die Leistung, aber nicht auf das reguläre Verhalten auswirken, können Super-Greed-Quantoren tatsächlich die Bedeutung eines regulären Ausdrucks ändern. Wenn *+ anstelle von * verwendet wird, ist die erste Übereinstimmung gierig (d. h. die größtmögliche, als wäre sie nur *), aber es gibt keinen Fallback, wenn sie fehlschlägt, selbst wenn dies dazu führt, dass die gesamte Suche fehlschlägt. Wann könnte dies nützlich sein? Nehmen wir an, wir müssen Text in Anführungszeichen finden. Das reguläre \"[^\"]*\" wird gut funktionieren. Allerdings führt es in negativen Fällen zu unnötigen Einrückungen (z. B. „bla bla bla). Durch die Verwendung von \"[^\"]*+\" wird dies vermieden Rollbacks ohne Änderung der Bedeutung des Ausdrucks. Unabhängige Gruppierung erzielt den gleichen Effekt und bietet noch mehr Kontrolle (siehe Suns Tutorial ).

4) Vermeiden Sie Gruppeneinnahmen

Jeder Ausdruck in Klammern wird standardmäßig als Gruppe betrachtet. Dies hat einen geringen Einfluss auf die Leistung. Machen Sie Ihre Gruppen wann immer möglich „uneinnehmbar“, indem Sie sie mit (?: statt ( ) beginnen .

5) Setzen Sie Interleaving mit Bedacht ein

Wenn Interleaving verwendet wird (z. B. Paul|Jane|Chris ), ist die Reihenfolge, in der die Engine versucht, die Optionen abzugleichen, dieselbe wie die Reihenfolge, in der sie erscheinen. Sie können diese Funktion nutzen und die häufigsten Optionen näher am Anfang platzieren. Dadurch wird die durchschnittliche positive Antwortzeit verbessert.

6) Vermeiden Sie Unklarheiten

Schreiben Sie reguläre Ausdrücke so, dass die Anzahl unterschiedlicher Übereinstimmungen in der Eingabezeichenfolge minimiert wird. Beispiel: Der am Anfang des Artikels angegebene reguläre Ausdruck (a*b*)* lässt die Zeichenfolge „aabb“ auf zu viele Arten interpretieren: (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)* hingegen interpretiert nur eindeutig Kombinationen positiv. Dies ist sehr wichtig, um Rücksendungen in Fällen mit Beinahe- Übereinstimmung zu reduzieren.

7) Vorschau

Mit der Vorschau können Sie Beschränkungen für Sequenzen links/rechts von der aktuellen Position hinzufügen. Insbesondere können Sie mit einem negativen Lookahead nach Zeilen suchen, die keine Sequenz enthalten (was würden wir ohne diese tun!). Wie kann dies dazu beitragen, die Produktivität zu steigern? Nehmen wir an, wir möchten die URL aus dem Link-Tag übernehmen. Betrachten Sie den folgenden regulären Ausdruck: a .* href=(\S*).*/ Bei regulären Tags stimmt dieser Ausdruck nur mit der Adresse überein, wenn der Text das Attribut „href“ enthält (\S wird für alle Zeichen außer Trennzeichen verwendet). Bei einigen ungewöhnlichen Tags kommt es jedoch beispielsweise zu einem Rollback. Zum Beispiel: „a href= href=href=…. href=etwas.“ Der folgende reguläre Ausdruck verhindert, dass dies geschieht, wenn „.*“ in einem Ausdruck durch etwas ersetzt wird, das nicht mit „href“ übereinstimmt: a ((?!href).)* href=(\S*)((?!href).)*/

8) Geben Sie die Länge an

Java enthält einen Regexp-Optimierer, der die Länge der Eingabezeichenfolge anhand der aus dem regulären Ausdruck erhaltenen Mindest- und Höchstlängen vergleicht. Dadurch können Sie die Suche in manchen Fällen sofort beenden. Um diesen Mechanismus zu unterstützen, sollte nach Möglichkeit die Anzahl der Wiederholungen angegeben werden (z. B. entspricht [01]{6} allen binären Zeichenfolgen mit einer Länge von sechs Zeichen).

9) Wählen Sie identische Zeilen aus

Manchmal sind gleiche Zeichenfolgen in Gruppen oder Alternativen versteckt: (hello|hell|heel) Dieser Ausdruck kann wie folgt vereinfacht werden: he(llo|ll|el) Auf diese Weise geben wir dem Regexp-Optimierer mehr Informationen.

10) Testen Sie Ihren regulären Ausdruck

Es kann sinnvoll sein, den regulären Ausdruck zuerst zu testen, wenn er in einer leistungskritischen Anwendung verwendet wird. Schreiben Sie einen Mikro-Benchmark, der Ihren Ausdruck anhand verschiedener Eingabedaten testet. Stellen Sie sicher, dass Sie die Tests mit Daten unterschiedlicher Länge und auch mit Daten durchführen, die Ihrer Stichprobe sehr nahe kommen.

Links:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Expression-Processing/