warum python regex ist so langsam?

Nach langem Debuggen habe ich herausgefunden, warum meine Anwendung mit python regexps langsam ist. Hier ist etwas finde ich überraschend:

import datetime
import re

pattern = re.compile('(.*)sol(.*)')

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*1000 + "sal " + "ciao mandi "*1000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

Die Ausgabe auf meinem Rechner ist:

string len 220004
time spent 0:00:00.002844

string len 22004
time spent 0:00:05.339580

Den ersten test-string ist 220K lange, übereinstimmt und die Abstimmung ist Recht schnell. Die zweite test-string ist 20Km lang, passt nicht und es dauert 5 Sekunden zu berechnen!

Wusste ich, dass dieser Bericht http://swtch.com/~rsc/regexp/regexp1.html, die besagt, dass die regexp-Implementierung in python, perl, ruby ist etwas nicht optimal... das Ist der Grund? Ich hätte nicht gedacht, dass es passieren könnte, mit einem so einfachen Ausdruck.

Hinzugefügt
Meine ursprüngliche Aufgabe ist das aufteilen einer Zeichenfolge zu versuchen, verschiedene regex wiederum. So etwas wie:

for regex in ['(.*)sol(.*)', '\emph{([^{}])*)}(.*)', .... ]:
    lst = re.findall(regex, text) 
    if lst:
        assert len(lst) == 1
        assert len(lst[0]) == 2
        return lst[0]

Dies ist zu erklären, warum ich nicht verwenden split. Ich habe mein Problem gelöst durch Austausch (.*)sol(.*) mit (.*?)sol(.*) wie vorgeschlagen, durch Martijn.

Wahrscheinlich sollte ich verwenden match statt findall... aber ich glaube nicht, das hätte das Problem gelöst, da die regexp wird, um übereinstimmung im gesamten Eingangs-und daher findall sollten aufhören, auf den ersten match.

Trotzdem meine Frage war mehr wie einfach ist es, zu fallen in diesem problem für Sie ein regexp-Neuling... ich denke, es ist nicht so einfach zu verstehen, dass (.*?)sol(.*) ist die Lösung (und zum Beispiel (.*?)sol(.*?) ist nicht).

  • Nein, der Grund ist nicht die Implementierung. Der Grund dafür ist, dass die beiden .* sind zu nachsichtig und zu einer katastrophalen backtracking. Was Sie genau versuchen zu tun?
  • die katastrophale backtracking ist die Umsetzung problem. Lesen Sie den verlinkten Artikel von Emanuele.
  • Nein, die katastrophalen backtracking ist in diesem Fall aufgrund der Muster Konzeption. Sie erhalten mehr oder weniger das gleiche Resultat mit anderen NFA-Motoren.
  • Lesen Sie den Artikel. "Die anderen NFA-engines" haben die gleiche Umsetzung. Ein echter FSA würde ohne backtracking.
  • Noch eine Anmerkung: das problem ist nicht verursacht durch die doppelte (.*). Suche für (.*)sol hat genau die gleiche Zeit-Profil. In der Tat (.*)sol ist eigentlich noch schlimmer, wenn der string enthält sol und suchen Sie mit findall(), denn es löst ein gescheiterter backtracking-Suche auf dem Teilstring, der folgt sol. (Die original RE konsumieren werden, wird der gesamte string auf Erfolg).
  • Ich hatte das gleiche Langsamkeit problem - warteten mehr als 2 Minuten, als der string war sehr lang. Ich installiert das Paket regex - funktioniert Super! bekam das Ergebnis sofort für die gleiche Zeichenfolge. Heruntergeladen von hier: pypi.python.org/pypi/regex

InformationsquelleAutor Emanuele Paolini | 2014-10-06
  1. 18

    Den Thompson-NFA-Ansatz wechselt die regulären Ausdrücke aus der Standard-gierig standardmäßig nicht gierig. Normalen regelmäßige Ausdruck-Motoren können das gleiche tun; ändern Sie einfach .* zu .*?. Sie sollten nicht gierig Ausdrücken, wenn nicht-gierig zu tun.

    Schon jemand gebaut ein NFA regulärer Ausdruck parser für Python: https://github.com/xysun/regex

    Es in der Tat besser als der Standard-Python reguläre Ausdrücke parser für die pathologischen Fälle. Jedoch, es unter-führt alles andere:

    Diese regex-engine underperforms-Python-re-Modul auf normalen Eingänge (mit Glenn Fowler-test-suite-siehe unten)

    Festsetzung der pathologischen Fall auf Kosten des typischen ist wahrscheinlich ein guter Grund, nicht zu verwenden, die NFA-Ansatz als Standard-engine, auch nicht, wenn die pathologischen Fall kann einfach vermieden werden, statt.

    Ein weiterer Grund ist, dass bestimmte Funktionen (wie Rückverweise) sind entweder sehr schwer oder unmöglich zu realisieren mit der NFA Ansatz. Siehe auch die Antwort auf die Python-Ideen-mailing-Liste.

    Als solche, dein test kann gemacht werden viel besser, wenn Sie mindestens eines der Muster, nicht-gierig zu vermeiden, die katastrophale backtracking:

    pattern = re.compile('(.*?)sol(.*)')

    oder nicht mit einem regex an alle, könnten Sie str.partition() man die Präfix-und postfix statt:

    before, sol, after = s.partition('sol')

    z.B. nicht alle text-Probleme sind reguläre Ausdrücke geprägt, so legte, dass hammer und Blick auf den rest der toolbox!

    Zusätzlich, Sie könnte vielleicht an der alternative zu suchen re Modul, regex. Dieses Modul implementiert einige grundlegende Prüfungen für pathologische Fälle, und weicht Ihnen geschickt, ohne Rückgriff auf ein Thompson-NFA-Umsetzung. Zitieren ein Eintrag, um ein Python bug-report tracking regex:

    Die interne engine nicht mehr interpretiert, eine form von bytecode, sondern stattdessen
    folgt eine verknüpfte Menge von Knoten, und es kann Breite-Weise sowie
    Tiefe-zuerst, was macht es deutlich besser, wenn Sie sich mit einem
    diese 'pathologischen' regexes.

    Dieser Motor ausführen kann, Ihre pathologischen Fall mehr als 100 tausend mal schneller:

    >>> import re, regex
>>> import timeit
>>> p_re = re.compile('(.*)sol(.*)')
>>> p_regex = regex.compile('(.*)sol(.*)')
>>> s = "ciao mandi "*1000 + "sal " + "ciao mandi "*1000
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_re as p', number=1)
2.4578459990007104
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_regex as p', number=100000)
1.955532732012216

    Hinweis: die zahlen; beschränkte ich re test 1 ausführen und es dauerte 2.46 Sekunden, während die regex Testläufe 100k mal in unter 2 Sekunden.

    • Oder str.split() ist, da seine Verwendung findall() deutet darauf hin, dass mehrere Positionen gewünscht sind.
    • mein Punkt war eher, zu zeigen, dass es mehr Werkzeuge in der toolbox! 🙂
    • Gotcha, auch hier.
    • In meinem Anwendungsfall will ich split text in zwei Teile, aber die Aufteilung wird erreicht, indem viele verschiedene regexps (die ich verketten mit |) einige von Ihnen sind komplizierter als dieses (aber nicht so langsam...). So wäre es schön zu halten, dieses matching in einem regexp.
    • für Spaltung, die Sie verwenden würden re.split(), und dann würden Sie nicht brauchen, um zu verwenden .* für den Teil vor und nach der sol text.
    • Was ist falsch mit die kommende regex - Modul? Das ist schnell und viel schneller auf die meisten pathologischen lieben. Für dieses Beispiel ist es mehr als schnell genug. Wie auch immer, ich downvoted, da ich denke, Zeichnung, performance-Schlussfolgerungen aus dem Vergleich einer stark optimierten C-Implementierung mit einem hastig-aus der reinen Python-Implementierung ist über das Schlimmste, das benchmarking, die ich gesehen habe wer tun, immer.
    • Ich hatte nicht bezahlt Aufmerksamkeit auf die Besonderheiten der Umsetzung.
    • Doch Sie zogen Ihre Schlussfolgerungen daraus.
    • sicher, ich hatte polnische ausgegangen, dass Sie wussten, was Sie Taten. Ich lese die benchmarking-Ergebnisse layed out in der README-Datei.
    • was ist der status der regex Modul überhaupt? Gibt es einen plan, doch wenn es in Python stdlib?
    • Es wird immer wieder vorgeschlagen, und jeder scheint, Sie zu unterstützen, aber es wird nie fertig. Die Ausgabe hat eine gute Zusammenfassung des "warum" obwohl, die Frage wird am besten beantwortet, als "nicht genug manpower".
    • Trotzdem diese Frage beweist, dass Sie im Gegensatz zu dem, was ist anders in Ihrer Python-Ideen link, es ist einfach falsch, dass "man zu schreiben hat ziemlich nutzlos regulären Ausdruck, um es in die O(2^n) läuft die Zeit." Das einzige, was falsch mit (.*)sol ist, dass es auslösen kann pathologische backtracking.
    • ich denke, dass ich nicht verwenden können wieder.split. Einige der Muster aufteilen, mein text ist wie: r"\emph{([^{}]*)}(.*)" (vielleicht sollte ich nicht nennen dies einen "split").
    • Ich weiß nicht, der Wahnsinn, der hier passiert. Siehe meine Antwort

    InformationsquelleAutor Martijn Pieters
  2. 7

    Ich denke, das hat nichts zu tun mit katastrophalen backtracking (oder zumindest mein Verständnis davon).

    Das problem wird verursacht durch die erste (.*) im (.*)sol(.*), und die Tatsache, dass die regex ist nicht überall verankert.

    re.findall(), nachdem er mit dem index 0, würde sich wiederholen, bei index 1, 2, etc. bis zum Ende der Zeichenfolge.

    badbadbadbad...bad
^                   Attempt to match (.*)sol(.*) from index 0. Fail
 ^                  Attempt to match (.*)sol(.*) from index 1. Fail
  ^                 Attempt to match (.*)sol(.*) from index 2. Fail (and so on)

    Effektiv hat quadratische Komplexität O(n2), wobei n die Länge der Zeichenkette.

    Das problem gelöst werden kann durch eine Verankerung der Ihr Muster, so schlägt es sofort an Positionen, die Ihre Muster keine chance hat, zu entsprechen. (.*)sol(.*) suchen sol innerhalb einer Zeile text (mit Trennzeichen, die durch Zeilenende-Zeichen), also, wenn Sie nicht finden können, ein match am Anfang der Zeile, es finden nicht alle für den rest der Zeile.

    Daher können Sie verwenden:

    ^(.*)sol(.*)

    mit re.MEHRZEILIG option.

    Läuft dieser test-code (modifiziert von Euch):

    import datetime
import re

pattern = re.compile('^(.*)sol(.*)', re.MULTILINE)

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*10000 + "sal " + "ciao mandi "*10000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

    (Beachten Sie, dass beide übergeben und Versagen sind 220004 Zeichen)

    Ergibt Folgendes Ergebnis:

    string len 220004
time spent 0:00:00.002000

string len 220004
time spent 0:00:00.005000

    Dadurch wird deutlich, dass in beiden Fällen haben die gleiche Größenordnung.

    • Das ist interessant... in der Tat der Punkt ist, dass re.search ist langsam, während re.match ist schnell. Allerdings habe ich versucht, die gleiche Suche mit awk (aber ich bin mir nicht 100% sicher, dass ich eine gleichwertige Muster) und das scheint für awk eine Suche und ein match dauert die gleiche Zeit. Vielleicht ist der Punkt ist, dass mit der NFA Ansatz, den ich implementieren können, die eine Suche in linearer Zeit, wo eine wiederholte entsprechen würde, erfordert quadratische Zeit.
    • awk nicht verwenden backtracking-Motor. Das ist, warum es ist schnell.
    • Ist es nicht dies, was pathologische backtracking ist?
    • Das ist eher das Verhalten auf der obersten Ebene (wo der Motor den nächsten index, nachdem alle Möglichkeiten auf dem aktuellen index ausgeschöpft haben). Auch technisch können Sie definieren, dass es "katastrophale backtracking", aber es unterscheidet sich von dem Fall (a*)*, wo das problem geschieht aufgrund der engine erlaubt einein - Erweiterung. Die Lösung für die 2 Fälle sind andere auch. Aber ich Stimme zu, dass am Ende irgendwelche Unzulänglichkeiten werden durch übermäßiges backtracking.
    InformationsquelleAutor nhahtdh
  3. 0
    ^(?=(.*?sol))\1(.*)$

    Können Sie versuchen, diese.Dies reduziert backtracking-und scheitert schneller.Versuchen Sie Ihren Text hier.

    http://regex101.com/r/hQ1rP0/22

    • Was macht Sie denken, dass es nicht schneller und weniger backtracks?
    • So, Sie erfassen und sofort für rückreferenzierung der erfassten Gruppe, und behauptete, es schlägt schneller mit der zusätzlichen Erfassung; Was gibt? Gut, dies dauert länger, um erfolgreich zu sein, und nicht wirklich schneller scheitern.
    • naja ich check bei regexhero.net ...das Versagen in einem kleinen string war 132% schneller, und wenn Sie Erfolg es war 50 % schneller.Ich denke, das ist eine deutliche Verbesserung
    • es dauert weniger Anzahl der Schritte als auch
    • Sie sind mit non-greedy matching, welches schneller ist als greedy backtracking-Suche als Martijn hingewiesen. Dies war tatsächlich schneller als die nicht gierig - version des OP ' s regexp?
    • versucht das auch.es dauerte eine geringere Anzahl von Schritten.
    • Sie waren bereits sagte, in Ihrer eigenen Frage, die die Anzahl der Schritte ist nicht der Letzte Faktor für die Geschwindigkeit. Das einzige ist, dass diese etwas schneller als die OP ' s regex sind die Anker. Verwenden Sie Anker auf die OP 's regex, und das ist viel langsamer als OP' s current regex.
    • Ich habe getestet, es auf regexhero....Nein, der Schritte war nur ein Hinweis.....

    InformationsquelleAutor vks
Schreibe einen Kommentar