Python Regex比预期慢

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

local_time explict正则表达式写得不好吗？

Answer 1

正则表达式回溯的次数越多，速度就越慢。

_{这可能不适用于非常小的输入数据。然而，谁会关心小数据上的性能呢？：D}

本文详细介绍了这个主题：

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

这个问题也有一些有趣的贡献：

• 贪婪、不情愿、占有量词