Ich habe eine Website debuggt, um die Quelle für lange Seitenladezeiten zu finden, und ich habe sie auf eine Regex beschränkt, die verwendet wird, um URLs aus Text zu extrahieren:
%Vor% Dies dauert etwa 3 Sekunden, um auf einem großen Textblock zu laufen. Ich fand heraus, dass, wenn ich das Inverse der ersten Klausel zum Anfang der Regex ( (?:[^\w+.-]|^) ) hinzufüge, es fast sofort läuft:
Es scheint mir, als ob die hinzugefügte Klausel die Regex überhaupt nicht beeinflussen sollte, da nichts dazu führen kann, dass diese Klausel fehlschlägt (da diese Zeichen durch die "[\ w + .-] ++" -Klausel übereinstimmen würden). Warum lässt die Regex so viel schneller laufen?
Bearbeiten
Einige Leute haben nach einem Beispiel gefragt, was ich zu tun versuche. Um die Dinge zu vereinfachen und die Bedenken der Leute in den Kommentaren anzugehen, verwende ich die folgenden zwei Regexes:
%Vor%Starten Sie IRB / Pry und werfen Sie einen Text in eine Variable (dies ist eine geschrubbte Version dessen, wonach tatsächlich gesucht wird):
%Vor%Benutze den langsamen Regex und notiere, wie langsam es ist:
%Vor%Verwenden Sie die schnelle Regex und beachten Sie, wie schnell es ist:
%Vor%Ich habe herausgefunden, dass dieses Problem spezifisch für die Art von Daten ist, die ich im Beispiel verwendet habe (nicht sehr viele Leerzeichen). Wenn Sie es gegen RFC 3986 ausführen, was viel länger dauert, sind beide Versionen gleich schnell.
Das erste Muster ist langsam, weil es mit einem Wechsel beginnt und der erste Zweig des Wechsels sehr freizügig ist, da es eine beliebige Anzahl von Wörtern, Zeichen oder Punkten oder Bindestrichen erlaubt. Konsequenterweise benötigt diese Abwechslung eine Menge Zeit / Schritte, bevor sie fehlschlägt.
Das zweite Muster ist schneller, weil (?:[^\w+.-]|^) (das ist auch eine Alternierung) funktioniert wie eine Art Anker. In der Tat, auch wenn es sich um eine Alternierung handelt, wird es schnell getestet, da der erste Zweig nur einem Zeichen entspricht und das zweite eine Assertion mit der Breite null ist. Es dauert also weniger Zeit / Schritte zu versagen. (insbesondere weil ein Wortzeichen oder ein Punkt oder eine Hype folgen muss, das ist eine bindende Bedingung)
Aber Sie können dieses Muster besser schreiben. Da Sie nach URLs suchen, können Sie am Anfang präziser sein: Die URL kann mit, sagen wir, "http", "ftp", "sftp", "gopher", "www" beginnen (fühlen Sie sich frei um bei Bedarf weitere Schemata hinzuzufügen) . So können Sie den Anfang mit beschreiben:
%Vor%Um die Kosten für den Wechsel zu begrenzen (5 Zweige an jeder Position in der Zeichenfolge zu testen) können Sie zwei Tricks anwenden:
Sie können eine Wortgrenze verwenden, um Positionen schnell zu überspringen, die nicht der Anfang oder das Ende eines Wortes sind:
\b(?:https?:\/\/|ftp:\/\/|sftp:\/\/|gopher:\/\/|www\.)
Sie können einen Lookahead mit dem ersten Buchstaben jedes Zweigs hinzufügen, um nicht benötigte Positionen im String schnell zu vermeiden, ohne die fünf Zweige zu testen:
\b(?=[fghsw])(?:https?:\/\/|ftp:\/\/|sftp:\/\/|gopher:\/\/|www\.)
So können Sie ein effizienteres Muster wie folgt schreiben:
%Vor%Kurz gesagt: Ein Muster ist effizient, wenn es an schlechten Stellen in der Zeichenfolge schnell versagt.
Ein anderes mögliches Design, das mehr Speicher benötigt und überprüft, ob die Erfassungsgruppe für jede Übereinstimmung existiert, aber das ist schneller:
%Vor%(Die Idee besteht darin, das Muster in zwei Hauptzweige aufzuteilen, das erste beschreibt alles, was Sie vermeiden wollen, und das zweite beschreibt die URLs. Der Effekt ist ein schneller Sprung zu Schlüsselpositionen in der Zeichenfolge) / em>
Hinweis: Wenn Muster zu lang werden, können Sie den Modus für freien Abstand (oder Kommentarmodus ...) für Lesbarkeit und Wartbarkeit verwenden:
%Vor%oder Sie können eine formatierte Zeichenfolge und einen Join verwenden, wie von Cary Swoveland in Kommentaren vorgeschlagen.