Wir haben die folgenden Regeln für die Validierung unseres Benutzernamens:
Wir haben die folgende Regex für dasselbe:
%Vor%Beim Versuch, einen bestimmten String zu finden, wächst die CPU-Auslastung exponentiell. Zum Beispiel:
%Vor%Natürlich sollte ein String wie oben beschrieben sofort fehlschlagen, aber ich möchte wissen, warum es so viele CPU-Zyklen benötigt. Endgültiger Code:
%Vor%Mit anderen Zeilen habe ich die Regex wie unten beschrieben umgeschrieben und es ist gut:
%Vor%Wenn Engines für reguläre Ausdrücke viel Backtracking verwenden, wird der Anpassungsprozess sehr langsam. Backtracking passiert sehr häufig, wenn Sie verschiedene Teile Ihres Ausdrucks mit überlappenden Teilen Ihrer Eingabe vergleichen, insbesondere wenn keine Übereinstimmung vorhanden ist: Die Engine versucht verschiedene Möglichkeiten, die Eingabe zwischen den Teilen Ihres regulären Ausdrucks aufzuteilen.
Betrachten Sie dieses einfache Beispiel aus Ihrem Regex: Lassen Sie uns [a-zA-Z0-9]+[_-]*[a-zA-Z0-9]* verwenden, um M45766235H. zu entsprechen Beachten Sie, dass es zwei Unterausdrücke gibt, die alle Zeichen beginnend mit dem zweiten abdecken können: p>
%Vor%
Da es keine Übereinstimmung gibt, sind das genau zehn sinnlose Wiederholungen. Aber das ist nicht das Ende! Wenn es andere Unterausdrücke in der Mischung gibt, die eine mehrdeutige Abdeckung erzeugen könnten, werden diese zehn möglichen Übereinstimmungen für jede der möglichen Übereinstimmungen in der Folge versucht.
Zu sagen, dass sich die Auswirkungen des Backtrackings schnell addieren, wäre eine Untertreibung: Sie multiplizieren sich in geometrischer Progression und verbrauchen schließlich einen Großteil Ihrer CPU.
Die Moral dieser Geschichte besteht darin, zu versuchen, die Menge an Backtracking zu reduzieren. Zum Beispiel Ihr zweiter Ausdruck
%Vor%kann wie folgt umgeschrieben werden:
%Vor% Die beiden Ausdrücke stimmen mit der gleichen Menge von Eingaben überein, aber wenn es eine Übereinstimmung gibt, wird der zweite Ausdruck eine eindeutige Übereinstimmung haben, während der ursprüngliche Ausdruck ungefähr (N-2)^3 verschiedene Möglichkeiten haben würde, die übereinstimmende Zeichenfolge unter den dreien aufzuteilen Unterausdrücke, die mit Wortzeichen übereinstimmen.
Hier finden Sie weitere Informationen zu einem verwandten Thema: Performance von Greedy vs. Lazy Quantifiers .