Python Regex wolniej niż oczekiwano

Question

Przeczytałem fajne article, jak uniknąć tworzenia wolnych wyrażeń regularnych. Ogólnie rzecz biorąc wygląda na to, że dłuższe i bardziej wyraźne, a wyrażenie regularne jest tym szybsze, co zostanie ukończone. Chciwe wyrażenie regularne może być wykładniczo wolniejsze.

Pomyślałem, że przetestuję to, mierząc czas potrzebny do ukończenia bardziej złożonego/wyraźnego stwierdzenia z mniej złożonym/chciwym stwierdzeniem. W przeważającej części wszystko wydaje się być prawdziwe, ale mam jedno zachłanne stwierdzenie, które jest wolniejsze. Oto dwa przykłady:

import re 
from timeit import timeit 

# This works as expected, the explicit is faster than the greedy. 
# http_x_real_ip explicit 
print(timeit(setup="import re", stmt='''r = re.search(r'(\d{1,3}\.\d{1,3}.\d{1,3}.\d{1,3})', '192.168.1.1 999.999.999.999')''', number=1000000)) 
1.159849308001867 

# http_x_real_ip greedy 
print(timeit(setup="import re", stmt='''r = re.search(r'((?:\d{1,3}\.){3}\d{1,3})', '192.168.1.1 999.999.999.999')''', number=1000000)) 
1.7421739230003368 

# This does not work as expected, greedy is faster. 
# time_local explicit 
print(timeit(setup="import re", stmt='''r = re.search(r'(\d{1,2}/\w{3}/[2][0]\d{2}:\d{2}:\d{2}:\d{2}\s[+][0]{4})', "[23/Jun/2015:11:10:57 +0000]")''', number=1000000)) 
1.248802040994633 

# time_local greedy 
print(timeit(setup="import re", stmt='''r = re.search(r'\[(.*)\]', "[23/Jun/2015:11:10:57 +0000]")''', number=1000000)) 
1.0256699790043058 

Czy lokalne wyrażenie czasowe jest niedokładne?

Answer 1

Im więcej wyrażeń regularnych ma cofać, tym wolniej.

_{Może to nie wystarczyć dla bardzo małych danych wejściowych. Kto jednak chciałby mieć wydajność na małych danych? : D}

---

Ten temat jest dobrze opisane w tym artykule:

• http://www.regular-expressions.info/catastrophic.html

Również tam są ciekawe wkłady w tej kwestii:

• Greedy vs. Reluctant vs. Possessive Quantifiers

Answer 2

Nie używasz również funkcji wyrażeń regularnych w języku Python, co oznacza, że ​​czas wyszukiwania obejmuje również czas, w którym moduł re ma skompilować wyrażenie regularne w każdej iteracji.

>>> print(timeit(setup="import re", stmt='''r = re.search(r'(\d{1,3}\.\d{1,3}.\d{1,3}.\d{1,3})', '192.168.1.1 999.999.999.999')''', number=1000000)) 
0.73820400238 
>>> print(timeit(setup="import re; regex = re.compile(r'(\d{1,3}\.\d{1,3}.\d{1,3}.\d{1,3})')", stmt='''r = regex.search('192.168.1.1 999.999.999.999')''', number=1000000)) 
0.271140813828 
>>> print(timeit(setup="import re; regex = re.compile(r'((?:\d{1,3}\.){3}\d{1,3})')", stmt='''r = regex.search('192.168.1.1 999.999.999.999')''', number=1000000)) 
0.31952214241 
>>> print(timeit(setup="import re; regex = re.compile(r'(\d{1,2}/\w{3}/[2][0]\d{2}:\d{2}:\d{2}:\d{2}\s[+][0]{4})')", stmt='''r = regex.search("[23/Jun/2015:11:10:57 +0000]")''', number=1000000)) 
0.371844053268 
>>> 

Różnica między chciwy i nie chciwy regex tutaj jest rzeczywiście znacznie bliżej oczekiwaniami podczas pre-kompilacji. Reszta wyjaśnienia idzie do tyłu.

Widzimy, że twoje testy przyspieszają prawie trzykrotnie, jeśli skompilujesz swoje wyrazy regularne dla dużej liczby iteracji.

Ta odpowiedź ma na celu uzupełnienie odpowiedzi @ mescalinum, ale w przypadku dużej liczby wyrażeń regularnych powinieneś naprawdę kompilować wyrażenia z wyprzedzeniem, aby uzyskać rzetelne porównanie.