Python正则表达式比预期的慢

Question

我读了一篇很酷的文章，介绍如何避免创建缓慢的正则表达式。通常来说，正则表达式越长、越显式，它就能越快地完成匹配。贪婪的正则表达式可能会慢上数倍。

我想通过对比一个更为复杂/显式语句和一个较不复杂/贪婪语句完成所需时间来测试这一点。大部分情况下似乎都符合这个规律，但是我有一个贪婪语句比较慢。以下是两个例子：

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

本地时间正则表达式只是写得很糟糕吗？

- HammerMeetNail

---

time_local 贪婪模式并不等同于匹配方括号中的任何内容。 - Chris Wesseling

也许 time_local 贪心算法的执行速度比预期的要快？ - Chris Wesseling

time_local 贪婪算法的执行速度比预期快...也许如果被解析的字符串更长，比如完整的日志条目，由于额外的回溯，它会花费更长时间？我得试一下。 - HammerMeetNail

您最后的正则表达式速度更快，因为正则表达式引擎需要考虑的令牌很少，并且因为只需要进行一个回溯步骤即可使模式成功。 - Casimir et Hippolyte

请注意，第一个模式是错误的，因为您忘记转义点号。 - Casimir et Hippolyte

Answer 1

正则表达式回溯的次数越多，速度就会越慢。 _{对于非常小的输入数据，可能不适用。然而，谁会关心小数据的性能？ :D}

---

这个主题在这篇文章中有详细介绍：

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

此外，在这个问题中也有一些有趣的贡献：

• 贪婪 vs. 勉强 vs. 占有量词

- fferri

Answer 2

你还没有使用 Python 正则表达式的 re.compile 功能，这意味着每次迭代搜索时都需要编译正则表达式，因此搜索时间也包括编译时间。

>>> 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的答案，但对于大量的正则表达式，您真的应该提前编译正则表达式以进行公平比较。

- Alex Huszagh

---

太棒了！谢谢你的分享，re.compile看起来非常有益。 - HammerMeetNail