Was ist der effizienteste Regex?
Ich habe vor kurzem einige Testergebnisse von Stellenbewerbern erhalten, in denen eine Person behauptete, dass die von ihnen gegebene Lösung effizienter sei (ich werde nicht sagen, was ich tun soll, weil ich die Antworten nicht beeinflussen möchte). Unnötig zu sagen, dass ich skeptisch war, aber ich weiß nicht genug über die inneren Abläufe von RE-Compilern, um intelligent zu kommentieren.
Die Frage war: Geben Sie einen regulären Ausdruck, um Zahlen von 0 bis einschließlich 99 zu erkennen.
Die Antworten waren:
%Vor%Ich wäre daran interessiert, warum einige von diesen schneller sind (oder besser in irgendeiner anderen Weise). Bonuspunkte, um Beweise zu liefern, statt Vermutungen, aber ich nehme immer noch Vermutungen an, wenn Sie es überzeugend genug klingen lassen: -)
7 Antworten
Der Ausdruck [0-9]{1,2} sollte der schnellste sein, den ich mir vorstellen kann, obwohl es von der spezifischen Engine abhängt.
Meine Argumentation ist:
- [0-9] {1,2} - das beschreibt genau, was Sie suchen möchten.
- [0-9]? [0-9] - Dies kann zu einem Zurückverfolgen führen, wenn die erste Übereinstimmung fehlschlägt.
- [0-9] | ([0-9] [0-9]) - dies erfordert, dass das erste Zeichen zweimal überprüft wird, wenn es fehlschlägt, und die Klammern hier sind unnötig und verursachen eine nicht benötigte Aufnahme.
Hier sind die Iterationen pro Sekunde, die ich beim Testen in .NET (ohne RegexOptions.Compiled) bekommen habe:
%Vor%Mit RegexOptions.Compiled:
%Vor%Und als Graph:
Hinweis: Ich habe jeden regulären Ausdruck so geändert, dass eine genaue Übereinstimmung erforderlich ist, anstatt eine Suche durchzuführen.
Mindestens in der Theorie , identische Regexe wie diese ergeben identische Automaten. Ein DFA-basierter Matcher wird jeweils einem Zeichen entsprechen und die verschiedenen möglichen Zweige in seinen Zuständen codieren (im Gegensatz dazu, jeweils einen Zweig zu nehmen und dann bei einem Fehler zurückzurücken), so dass die Leistung jedes derselben gleich ist .
Alle drei Regexes würden von diesem DFA abgeglichen:
%Vor% Status A : Startzustand. Geht zu B, wenn eine Ziffer angezeigt wird, andernfalls zu einem ERROR-Status.
Status B : Eine bis jetzt gültige Ziffer. EOL ($) wird akzeptiert. Eine Ziffer bewegt sich zu C. Alles andere ist ein Fehler.
Status C : Zwei übereinstimmende Ziffern. EOL wird akzeptiert, alles andere ist ein Fehler.
Das ist meine theoretische Antwort auf die Sprache. Ich kann nicht mit realen Regex-Engine-Implementierungen sprechen. Ich ignoriere die einfangende Semantik der Klammern, da ich vermute, dass das nicht der Punkt der Frage ist. Automaten behandeln auch nicht andere "nicht-theoretische" Konstrukte wie Gier, Lookahead, etc. Zumindest nicht in ihrer Lehrbuchpräsentation.
Ohne die Regex-Engine zu kennen, kann man nicht einmal entscheiden, ob diese korrekt sind.
Beispiel: Ein POSIX-ERE ist am längsten links, nicht am weitesten links, so dass es in einer Reihe von Alternativen die längste auswählt. Wählen Sie daher eine Zeichenfolge mit "ab" und /a|ab/ mit der gesamten Zeichenfolge. %Code%. Aber ein normales Backtracking von NFA, wie man es am häufigsten sieht, würde etwas anderes tun: Es würde Ordnung schaffen, und wenn man also die gleiche "ab" -Zeichenkette mit dem gleichen "ab" -Muster vergleicht, würde nur der Anfangsteil,% co_de, ausgewählt %.
Die nächste Frage ist die Erfassungsgruppe im selben Muster. Wenn sie beabsichtigt sind, sind sie merkwürdig, da Sie zweistellige Zahlen, aber keine einstelligen Zahlen behalten. Die anderen Muster tun das nicht, doch wird gesagt, dass sie im Verhalten identisch sind. Ich gehe also davon aus, dass sie hier Fehler machen. Andernfalls wird die Speicherbelegung der Capture-Gruppe natürlich mehr kosten, als dass sie nicht nehmen würde.
Das nächste Problem ist das Fehlen jeglicher Anker. Auch hier können wir nicht wissen, ob diese korrekt sind, weil nicht klar ist, wie die Input-Menge aussehen würde und was diese Engine mit nicht verankerten Patterns macht. Die meisten Suchmaschinen werden überall in der Zeichenfolge suchen, aber einige der weniger programmierbaren werden "hilfreich" hinzufügen, Anfang der Zeile (BOL) und End-of-Line (EOL) Anker dort. In eher üblichen Engines, in denen dies nicht der Fall ist, würde eine Postleitzahl in der Mitte der Zeile ebenfalls übereinstimmen, da fünf Ziffern offensichtlich ein- und zweistellige Teilstrings enthalten. Ob Sie /a|ab/ und "a" Anker oder ^ Anker wollen, kann ich nicht erraten.
Also muss ich hier ein paar Vermutungen anstellen. Ich werde die Anker auslassen, aber ich werde den Zweig der dritten Versionen neu anordnen, weil Sie sonst nie eine zweistellige Zahl mit den normalen (Nicht-POSIX) Arten von Backtracking-NFAs erreichen können, die meisten Dinge laufen / p>
Bevor man überhaupt das Timing in Betracht zieht, kann es sich wirklich lohnen, zu schauen, welche Art von Programm der Regex-Compiler aus diesen Mustern erstellt.
%Vor%Es ist wirklich eine gute Idee, sich die kompilierten Muster anzuschauen. Es kann noch aufschlussreicher sein, das kompilierte Muster zu beobachten, das gerade ausgeführt wird. Hier sehen wir beide:
%Vor%Hier hat der Compiler wirklich clever auf uns bekommen und das in eine Aho-Corasick-Trie-Struktur übersetzt. Offensichtlich wird dies ganz anders funktionieren als bei einem normalen Backtracking NFA auf demselben Programm.
Wie auch immer, hier ist das Timing für Ihre Muster oder in deren Nähe. Ich fügte eine alternative Formulierung für Nummer zwei hinzu und tauschte die Reihenfolge der Alternativen in Nummer drei.
%Vor%Das wurde von diesem Programm produziert:
%Vor%Hier sind Zahlen mit hinzugefügten Ankern:
%Vor%Und hier ist das minimal modifizierte Programm, das die zweite Reihe von Zahlen produziert:
%Vor%Wenn man schneller sein muss (wird wahrscheinlich von der verwendeten Regex-Engine abhängen), dann eindeutig die erste aus meiner Sicht (die im Gegensatz zu den anderen beiden eine einfache Morris-Pratt-Tabelle DFA sein kann), als die andere Zwei erfordern wahrscheinlich ein Zurückverfolgen oder führen zusätzliche Arbeit aus:
[0-9]?[0-9] - für den Fall mit einer Ziffer wird die Engine gierig sein und die erste Ziffer treffen, dann die zweite fehlschlagen; Backtrack und dann erfolgreich
[0-9]|([0-9][0-9]) - hier wird eine einfangende Gruppe verwendet, die die Dinge verlangsamt
Ich habe keine Ahnung von den Interna, aber was ist mit einem Pseudo-Benching? : D
Python
%Vor%Ergebnisse in Sekunden
%Vor%JavaScript
%Vor%Ergebnisse in Sekunden
%Vor%Was lernen wir? Well Pythons scheint ziemlich langsam zu sein, und V8 scheint ziemlich schnell zu sein Aber hey benching macht immer Spaß!
Update: Java Version
%Vor%Ergebnisse in Sekunden (Zeiten des vierten Laufs)
%Vor%Diese Regex sind so trivial, dass es egal sein sollte. Wenn ich jedoch eine effizientere Implementierung wählen müsste, wäre es entweder [0-9] {1,2} oder [0-9] [0-9] ?, was nicht in Ihrer Auswahl ist, da es kein Backtracking gibt notwendig.
Genau wie C und ++i gegenüber i=i+1 sollte ein guter Regex-Compiler alle drei zu genau dem gleichen endlichen Automaten kompilieren. Wenn nicht, würde ich das als Fehler betrachten.
(Ausnahme: Wenn die Markierung in Klammern für Unterausdrücke aktiviert ist, würde die dritte Datei offensichtlich kompilieren, um die zusätzlichen Markierungsinformationen zu enthalten.)
Tags und Links regex performance