Seite 1 von 1
RegEx-Performance Beispiele
Verfasst: Freitag 23. Februar 2007, 00:03
von PmanX
Hallo,
die Grundidee ist aus der englischen Gruppe.
Code: Alles auswählen
#
import timeit
import re
loop = 1000000
line = """
a sample line that will not match any condition, but long enough to
be meaninful in the context of this problem, or at least I thik so. This has 174
characters, is it enough?
"""
error_l1 = re.compile(r'error|miss|issing|inval|nvalid|math')
error_l2 = re.compile(r'error|m?(iss(?:ing)?|ath)|i?nval(?:id)?')
tokens = "error|miss|issing|inval|nvalid|math".split("|")
s1 = """#
from __main__ import line, error_l1
if error_l1.search(line): pass
"""
t1 = timeit.Timer(stmt = s1)
print "%.2f usec/pass" % (loop * t1.timeit(number = loop) / loop)
s2 = """#
from __main__ import line, tokens
for token in tokens:
if token in line: break
"""
t2 = timeit.Timer(stmt = s2)
print "%.2f usec/pass" % (loop * t2.timeit(number = loop) / loop)
s3 = """#
from __main__ import line
if "error" in line or "miss" in line or "issing" in line or "inval" in line or "nvalid" in line or "math" in line: pass
"""
t3 = timeit.Timer(stmt = s3)
print "%.2f usec/pass" % (loop * t3.timeit(number = loop) / loop)
s4 = """#
from __main__ import line, error_l2
if error_l2.search(line): pass
"""
t4 = timeit.Timer(stmt = s4)
print "%.2f usec/pass" % (loop * t4.timeit(number = loop) / loop)
Interressant ist vor allem, dass ein unglücklicher RegEx sehr langsam werden kann.
Sind die Vergleiche für Euch gültig?
Code: Alles auswählen
t1 -- 29.95 usec/pass
te -- 39.47 usec/pass
t3 -- 37.33 usec/pass
t4 -- 85.57 usec/pass
Gruß P.
Re: RegEx-Performance Beispiele
Verfasst: Freitag 23. Februar 2007, 07:45
von Luzandro
Code: Alles auswählen
print "%.2f usec/pass" % (loop * t1.timeit(number = loop) / loop)
Was soll denn der Sinn von diesem *loop/loop sein?
Code: Alles auswählen
error_l1 = re.compile(r'error|miss|issing|inval|nvalid|math')
error_l2 = re.compile(r'error|m?(iss(?:ing)?|ath)|i?nval(?:id)?')
Die Ausdrücke sind auch nicht wirklich equivalent, da im zweiten Fall z.B. auch 'missing' gematcht würde, wo der erste nur 'miss' matcht.
Wenn man die zweite Variante sinnvoller/korrekt angibt wäre es sogar etwas schneller (wobei ich hier wohl dennoch die besser lesbare erste Variante nehmen würde):
Code: Alles auswählen
error_l3 = re.compile(r'error|m(?:iss|ath)|i(?:ssing|nval)|nvalid')
Code: Alles auswählen
30.46 usec/pass
32.76 usec/pass
30.39 usec/pass
99.30 usec/pass
28.51 usec/pass
Re: RegEx-Performance Beispiele
Verfasst: Freitag 23. Februar 2007, 12:47
von PmanX
Luzandro hat geschrieben:
...
Was soll denn der Sinn von diesem *loop/loop sein?
...
Die Ausdrücke sind auch nicht wirklich equivalent, da im zweiten Fall z.B. auch 'missing' gematcht würde, wo der erste nur 'miss' matcht.
Code: Alles auswählen
print "%.2f usec/pass" % (loop * t1.timeit(number = loop) / loop)
Über die Sinnhaftigkeit habe ich nicht wirklich nachgedacht
aus einem Beispiel ausgeborgt.
zu 2) Der Match ist nicht 100%ig korrekt. Ich habe ihn aufgeführt, um zu zeigen, wie die Performance bei unglücklich geschriebenem RegEx leidet.
Vorrangig ging es darum, Logfiles zu parsen und zu zeigen, wie gut/schlecht RegExe, im Vergleich zu konventionellen Methoden, dabei abschneiden.
Für den einen oder anderen kann es vllt eine Entscheidungshilfe sein.
Natürlich nur, wenn die Beispiele vergleichbar sind
Kennt jemand weitere Methoden?
Gruß P.
Verfasst: Freitag 23. Februar 2007, 13:22
von birkenfeld
Für pathologische Fälle sind die Regex von Perl, Python etc. sogar katastrophal langsam, siehe
http://swtch.com/~rsc/regexp/regexp1.html.
Verfasst: Freitag 23. Februar 2007, 14:49
von PmanX
Unbedingt.
Beim NFA kann die RegEx schnell mal gegen die Wand laufen.
Die Frage stellt sich dann; kann man mit vertretbarem Aufwand dieses Problem konventionell lösen?
Verfasst: Freitag 23. Februar 2007, 15:38
von Luzandro
Was verstehst du unter "dieses Problem" und "konventionell"? Das erste dort angegebene Beispiel mit "a?^na^n" ist ja sowieso nur zur Demonstration geeignet, um zu sehen _dass_ ein Problem auftritt und recht einleuchtend ist _warum_ es in diesem Fall auftritt - allerdings würde sowieso niemand auf die Idee kommen etwas zu suchen, "wo am Anfang 0-n optionale a sein könnten und danach n a kommen müssen"
Verfasst: Freitag 23. Februar 2007, 17:36
von PmanX
Code: Alles auswählen
if token in line
if "error" in line or "miss" in line or "issing" in line or "inval" in line or "nvalid" in line or "math" in line:
Nenne ich "konventionell". Zu komplizierten RegEx'es gibt es selten vertretbare Alternativen.
Avoiding recursion
If you create regular expressions that require the engine to perform a lot of recursion, you may encounter a RuntimeError exception with the message maximum recursion limit exceeded. For example,
http://www.python.org/doc/lib/node49.html
Code: Alles auswählen
>>> import re
>>> s = 'Begin ' + 1000*'a very long string ' + 'end'
>>> re.match('Begin (\w| )*? end', s).end()
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "/usr/local/lib/python2.5/re.py", line 132, in match
return _compile(pattern, flags).match(string)
RuntimeError: maximum recursion limit exceeded
Verfasst: Freitag 23. Februar 2007, 18:42
von birkenfeld
Luzandro hat geschrieben:Was verstehst du unter "dieses Problem" und "konventionell"? Das erste dort angegebene Beispiel mit "a?^na^n" ist ja sowieso nur zur Demonstration geeignet, um zu sehen _dass_ ein Problem auftritt und recht einleuchtend ist _warum_ es in diesem Fall auftritt - allerdings würde sowieso niemand auf die Idee kommen etwas zu suchen, "wo am Anfang 0-n optionale a sein könnten und danach n a kommen müssen"
Ja, aber solche Fälle kommen auch in der Praxis vor. Z.b. im Falle von Pygments' C#-Lexer, der Property-Definitionen finden sollte -- letztendlich kam dabei auch exponentielle Zeit heraus.