Python Regex медленнее, чем ожидалось

Question

Я прочитал классный article о том, как избежать создания медленных регулярных выражений. Вообще говоря, это выглядит как более длинный и более явный, а регулярное выражение - быстрее. Жадное регулярное выражение может быть экспоненциально медленнее.

Я думал, что смогу проверить это, измерив время, необходимое для завершения более сложного/явного заявления с менее сложным/жадным утверждением. По большей части все, кажется, держится, но у меня есть одно жадное утверждение, которое замедлялось медленнее. Вот два примера:

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 

Является ли local_time expliction регулярным выражением плохо написанным?

Answer 1

Чем больше регулярное выражение должно возвращаться, тем медленнее оно.

_{Это может не соответствовать очень малым входным данным. Однако кто будет заботиться о производительности на небольших данных? : D}

---

Эта тема хорошо освещена в этой статье:

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

Также есть интересные вклады в этом вопросе:

• Greedy vs. Reluctant vs. Possessive Quantifiers

Answer 2

Вы также не используете функцию регулярных выражений Python, что означает, что время поиска также включает время для повторного модуля для компиляции регулярного выражения на каждой итерации.

>>> 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 
>>> 

Разница между жадным и не жадным регулярным выражением здесь на самом деле гораздо ближе к ожидаемым при предварительной компиляции. Остальное объяснение идет к отступлению.

Мы можем видеть, что ваши тесты ускоряются почти в 3 раза, если вы предварительно скомпилируете свои регулярные выражения для большого количества итераций.

Этот ответ предназначен для дополнения ответа @ mescalinum, но для большого количества регулярных выражений вы действительно должны компилировать регулярные выражения досрочно для справедливого сравнения.