RegEx-Performance Beispiele

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
PmanX
User
Beiträge: 123
Registriert: Donnerstag 25. Januar 2007, 13:50
Wohnort: Germany.BB.LOS
Kontaktdaten:

Freitag 23. Februar 2007, 00:03

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.
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Freitag 23. Februar 2007, 07:45

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
[url=http://www.leckse.net/artikel/meta/profilieren]Profilieren im Netz leicht gemacht[/url]
PmanX
User
Beiträge: 123
Registriert: Donnerstag 25. Januar 2007, 13:50
Wohnort: Germany.BB.LOS
Kontaktdaten:

Freitag 23. Februar 2007, 12:47

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.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Freitag 23. Februar 2007, 13:22

Für pathologische Fälle sind die Regex von Perl, Python etc. sogar katastrophal langsam, siehe http://swtch.com/~rsc/regexp/regexp1.html.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
PmanX
User
Beiträge: 123
Registriert: Donnerstag 25. Januar 2007, 13:50
Wohnort: Germany.BB.LOS
Kontaktdaten:

Freitag 23. Februar 2007, 14:49

Unbedingt.
birkenfeld hat geschrieben:Für pathologische Fälle sind die Regex von Perl, Python etc. sogar katastrophal langsam, siehe http://swtch.com/~rsc/regexp/regexp1.html.
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?
Benutzeravatar
Luzandro
User
Beiträge: 87
Registriert: Freitag 21. April 2006, 17:03

Freitag 23. Februar 2007, 15:38

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"
[url=http://www.leckse.net/artikel/meta/profilieren]Profilieren im Netz leicht gemacht[/url]
PmanX
User
Beiträge: 123
Registriert: Donnerstag 25. Januar 2007, 13:50
Wohnort: Germany.BB.LOS
Kontaktdaten:

Freitag 23. Februar 2007, 17:36

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
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Freitag 23. Februar 2007, 18:42

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.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Antworten