Die Schleife aufbrechen

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

Die größten Leistungsverbesserungen einer Regex sind oft unabhängig von den internen Optimierungen. Sie sind oft dann möglich, wenn man die Arbeitsweise der Regex-Maschine genau versteht und so der Maschine helfen kann, den Treffer zu finden. Wir haben uns nun zur Genüge mit Einzelheiten befasst und wollen das Gelernte jetzt im größeren Rahmen anwenden. Eine Methode, die ich »Schleifen aufbrechen« (loop unrolling) nenne, kann bestimmte reguläre Ausdrücke sehr viel schneller machen. Wir können damit beispielsweise das unendliche Matching vom Anfang des Kapitels (siehe Zurück zur Realität) in eine Regex verwandeln, die einen Fehlschlag innerhalb nützlicher Frist erkennt und die als Zugabe auch im Erfolgsfall schneller ist.

Die angesprochene »Schleife« ist die, die implizit durch den Gebrauch eines Sterns entsteht, wenn der Ausdruck die allgemeine Form ˹(dies|das|...)*˼ hat. Das ist in der Tat das Schema, nach dem unser »ewiges Matching« ˹"(\\.|[^\\"]+)*"˼ gestrickt ist. Wenn man bedenkt, dass dieser Ausdruck ungefähr unendlich lange braucht, bis er herausfindet, dass kein Treffer möglich ist, dann kann eine leichte Geschwindigkeitsverbesserung ganz angenehm sein.

Es gibt dazu zwei konkurrierende Verfahren:

1. Wir können untersuchen, welche Teile von ˹(\\.|[^\\"]+)*˼ bei einer Anzahl von Testfällen wirklich etwas erkennen. Dadurch erhalten wir eine Anzahl von Unterausdrücken, aus denen wir einen effizienteren regulären Ausdruck zusammenstellen können.

   Vor meinem geistigen Auge sehe ich einen großen Ball, der über einen Text rollt und der der ˹(...)*˼-Regex entspricht. Die Teile innerhalb der Klammer (...), die passen, lassen dabei eine Spur von benutzten Unterausdrücken zurück wie ein schmutziger Ball auf einem Teppich.

   Der Vergleich ist etwas weit hergeholt, ich weiß.

2. Die zweite Methode betrachtet den Ausdruck von einer höheren Warte aus. Wir treffen intelligente Annahmen, wie Texte wohl aussehen, die passen werden, und formulieren damit einen effizienteren Ausdruck.

In beiden Fällen muss der Ausdruck natürlich dasselbe bewirken. Ich beginne mit dem »Schleifen aufbrechen«-Ansatz und übertrage die gewonnenen Einsichten auf das zweite Verfahren.

Damit im Folgenden die Beispiele nicht durch zu viele Interpunktionszeichen unübersichtlich werden, verwende ich hier immer ˹(...)˼ als Klammern. Wenn nicht-einfangende Klammern mit ˹(?:...)˼ unterstützt sind, werden die Ausdrücke noch effizienter. Wir untersuchen später auch den Einfluss von atomaren Gruppen (siehe dazu Atomare Klammern) und possessiven Quantoren.

  

• Methode 1: Eine Regex anhand früherer Erfahrungen aufbauen
• Ein Rezept zum Aufbrechen von Schleifen
• Methode 2: Die kritische Schleife im größeren Zusammenhang betrachten
• Methode 3: Ein Internet-Hostname in Anführungszeichen
• Beobachtungen
• Atomare Gruppen und possessive Quantoren verwenden
• Beispiele zum Aufbrechen von Schleifen
• C-Kommentare aufbrechen

  

<< zurück

vor >>