Programmiermethoden für schnellere Ausdrücke

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Auf den letzten Seiten wurden interne Optimierungstechniken beschrieben, die bei traditionellen NFA-Maschinen implementiert sind. Kein Programm vereint alle davon, und auch wenn Ihr Lieblingsprogramm eine bestimmte Optimierung benutzt, kann das schon in der nächsten Version anders aussehen. Dennoch ist die Untersuchung der verschiedenen internen Optimierungsmethoden wertvoll; sie zeigt uns nämlich, welche Dinge in einer Regex-Maschine schnell ablaufen und welche langsam. Zusammen mit dem Wissen, wie eine traditionelle NFA-Maschine prinzipiell funktioniert, können wir diese Erkenntnisse auf drei Arten anwenden:

Optimierungsfreundlich formulieren

Wir können unsere regulären Ausdrücke so schreiben, dass die Möglichkeit zur Optimierung sicher erkannt wird. Zum Beispiel kann bei ˹xx*˼ statt ˹x+˼ die Optimierung »Literale Strings« (siehe dazu Suche nach einzelnen Zeichen oder festen Substrings) oder die »Erstes Zeichen«-Optimierung viel leichter erkannt werden.

Optimierungen imitieren

Wenn Ihr Programm eine bestimmte Optimierungsmethode nicht kennt, kann diese Optimierung unter Umständen durch eine explizite Programmierung der Regex imitiert werden. Folgendes Beispiel werden wir in Kürze in allen Einzelheiten untersuchen: Wir setzen vor ˹klipp|klar˼ das Lookahead-Konstrukt ˹(?=k)˼ und imitieren so die »Erstes Zeichen«-Optimierung auch bei den Systemen, die nicht von sich aus bemerken, dass jeder Treffer mit einem ›k‹ beginnen muss.

Die Maschine auf den Treffer hinsteuern

Mit unserem Wissen, wie ein traditioneller NFA funktioniert, können wir eine Regex so formulieren, dass sie schneller zu einem Treffer führt. Nehmen wir wieder das Beispiel ˹klipp|klar˼. Beide Alternativen beginnen mit ˹kl˼, und wenn schon bei der ersten Alternative das ˹kl˼ nicht passt, ist der erneute Test auf ˹kl˼ bei der zweiten Alternative eigentlich überflüssig. Wir können den zweiten Test also vermeiden, indem wir das ˹kl˼ aus der Alternation herausnehmen und stattdessen ˹kl(?:ipp|ar)˼ schreiben. So wird nur einmal auf ˹kl˼ geprüft, und die relativ aufwendige Alternation kommt nur dann ins Spiel, wenn sie wirklich benötigt wird. Mit dem Literal am Anfang können unter Umständen noch andere Optimierungen greifen.

Die verschiedenen Regex-Maschinen können aber empfindlich auf bestimmte Optimierungen von Hand reagieren:

• Manche Änderungen, die der Maschine eigentlich helfen sollten, können genau das Gegenteil bewirken, weil eine andere, bessere Optimierungstechnik nun nicht mehr anwendbar ist.
• Wenn Sie eine Optimierung imitieren, von der Sie wissen, dass die Maschine sie nicht selbst anwenden kann, kann es dennoch sein, dass der Aufwand den Gewinn übersteigt.
• Wenn Sie eine Optimierung imitieren, von der Sie wissen, dass die Maschine sie nicht selbst kennt, kann es doch sein, dass sie in einer neuen Version des Programms implementiert wird.
• Wenn Sie eine Regex umschreiben, damit eine bestimmte Optimierung angewendet werden kann, kann genau das bei einer neuen Programmversion die Anwendung einer besseren Optimierung unmöglich machen.
• Eine umformulierte Regex kann schwerer verständlich sein; das erschwert die Wartung des Programms.
• Wie viel die Optimierung ausmacht, hängt fast immer auch von der Art der zu bearbeitenden Daten ab. Eine Optimierung, die bei bestimmten Daten sehr viel bringt, kann sich bei anderen sogar negativ auswirken.

Ein wirklich sehr merkwürdiges Beispiel ist Folgendes: In einem Perl-Skript finden Sie ˹(000|999)$˼ vor und stellen fest, dass der Text aus den einfangenden Klammern nie benutzt wird. Wenn die Klammern durch nicht-einfangende Klammern ersetzt werden, wird das sicher schneller. Überraschung: Diese kleine und anscheinend nützliche Änderung verschlechtert die Leistung der Regex um mehrere Größenordnungen (um mehr als den Faktor Tausend). Wie bitte? Es stellt sich heraus, dass dadurch aus irgendwelchen Gründen die Optimierung für den Zeilenende-Anker verhindert wird (siehe Optimierungen mit Zeilen- und String-Ankern). Ich will Sie keineswegs davon abhalten, in Perl die nicht-einfangenden Klammern zu verwenden – in den allermeisten Fällen sind diese wirklich schneller als die einfangenden –, aber es gibt offenbar pathologische Situationen wie diese, in denen das Gegenteil erreicht wird.

Im Einzelfall und in der praktischen Anwendung kann nur das Austesten mit Benchmarks zeigen, ob eine Änderung der Regex für bestimmte Daten eine positive oder negative Wirkung hat. Sie müssen dann die einzelnen Punkte gegeneinander abwägen. Nach all diesen Warnungen komme ich jetzt dennoch zu den Tuning-Methoden, mit denen man das Letzte aus einer Regex-Maschine herausholen kann.

Gesunden Menschenverstand walten lassen

Eine der wirkungsvollsten Optimierungsmethoden ist die Anwendung von gesundem Menschenverstand.

Neukompilierung vermeiden

Definieren oder kompilieren Sie die Regex nur so oft, wie es wirklich notwendig ist. Beim objektorientierten Ansatz (siehe Prozeduraler und objektorientierter Ansatz) haben Sie die direkte Kontrolle darüber. Wenn eine Regex in einer Schleife wiederholt angewendet wird, soll das Regex-Objekt vorher – außerhalb der Schleife – erzeugt und kompiliert werden.

Beim prozeduralen Ansatz wie bei Tcl oder GNU Emacs sollten Sie darauf achten, dass die Anzahl der in einer Schleife verwendeten unterschiedlichen Ausdrücke kleiner bleibt als die Größe des Regex-Caches (siehe Kompilations-Caching beim prozeduralen Ansatz).

Bei Programmen mit integrierten regulären Ausdrücken wie Perl sollten Sie versuchen, in einer Regex innerhalb einer Schleife keine Variablen zu interpolieren. Das würde im Minimum bedeuten, dass die Regex jedes Mal neu ausgewertet werden muss, auch dann, wenn sich die interpolierten Variablen gar nicht ändern. (In Perl gibt es allerdings gute Möglichkeiten, das Problem zu vermeiden oder zu umgehen, siehe unter Regex-Kompilierung, der /o-Modifikator, qr/.../ und Effizienz.)

Nicht-einfangende Klammern verwenden

Wenn Sie den von den Klammern eingefangenen Text nicht weiterverwenden, ist es effizienter, die nicht-einfangenden Klammern ˹(?:...)˼ zu verwenden (siehe dazu Lösung 5). Einerseits muss der erkannte Substring nicht abgespeichert werden, und darüber hinaus wird der für das Backtracking gespeicherte Zustand weniger kompliziert. Außerdem können damit unter Umständen weitere Optimierungen ermöglicht werden, z.B. können unnötige Klammern beseitigt werden (siehe Entfernen von unnötigen Klammern).

Keine unnötigen Klammern

Setzen Sie Klammern, wo sie gebraucht werden; aber überflüssige Klammern können bewirken, dass bestimmte Optimierungen nicht mehr angewendet werden können. Benutzen Sie so etwas wie ˹(.)*˼ nur dann, wenn Sie das letzte von ˹.*˼ erkannte Zeichen benötigen. Das mag offensichtlich sein, aber dieser Abschnitt heißt ja auch »Gesunden Menschenverstand walten lassen«.

Keine unnötigen Zeichenklassen

Auch das scheint mir selbstverständlich zu sein, aber dennoch sehe ich in Programmen von Ungeübten nicht selten reguläre Ausdrücke, in denen so etwas wie ˹^.*[:]˼ vorkommt. Es ist mir nicht klar, warum jemand eine Zeichenklasse benutzt, die nur ein einziges Zeichen enthält – das verursacht den zusätzlichen Aufwand für eine Zeichenklasse, ohne irgendwelchen Gewinn abzuwerfen.

Bei einem Metazeichen wie ˹[.]˼ oder ˹[*]˼ ist anzunehmen, dass der Programmierer die Konvention zum Maskieren von Metazeichen wie bei ˹\.˼ und ˹\*˼ nicht kennt. Oft sieht man das auch mit Whitespace im  Modus »Freie Form«.

Leser der ersten Auflage dieses Buches verwenden möglicherweise Ausdrücke in der Art von ˹^[Ff][Rr][Oo][Mm]:˼, anstatt den Modus zum Ignorieren der Groß- und Kleinschreibung zu benutzen. Bei alten Perl-Versionen war dieser Modus in der Tat sehr ineffizient programmiert, deshalb hatte ich so etwas empfohlen. Diese Einschränkung ist aber seit mehreren Jahren hinfällig.

Anker ganz am Anfang der Regex verwenden

In beinahe allen Fällen kann man einer Regex, die mit ˹.*˼ beginnt, ein ˹^˼ oder ein ˹\A˼ (siehe Zeilenanfang, Stringanfang) voranstellen. Wenn eine solche Regex am Anfang des Suchstrings nicht passt, wird sie kaum passen, wenn das Getriebe die gleiche Regex an der zweiten Position ansetzt oder an der dritten, der vierten usw. Mit dem Zeilenanker (ob explizit oder durch eine interne Optimierung, mehr dazu unter Optimierungen mit dem Getriebe) kann hier viel unnötige Arbeit eingespart werden.

  

• Literalen Text herausstellen
• Anker herausstellen
• Gierig oder genügsam?
• Aufteilen in mehrere reguläre Ausdrücke
• Die »Erstes Zeichen«-Optimierung imitieren
• Atomare Gruppen und possessive Quantoren verwenden
• Die Regex-Maschine zum Treffer hinführen

  

<< zurück

vor >>