Python中的正则表达式意外地变慢

Question

考虑这个Python代码:

import timeit
import re

def one():
        any(s in mystring for s in ('foo', 'bar', 'hello'))

r = re.compile('(foo|bar|hello)')
def two():
        r.search(mystring)


mystring="hello"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])
mystring="goodbye"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])

基本上,我正在基准测试两种方法来检查大字符串中几个子串之一的存在.

我得到的(Python 3.2.3)是这个输出:

[0.36678314208984375, 0.03450202941894531]
[0.6672089099884033, 3.7519450187683105]

在第一种情况下,正则表达式很容易使any表达式失败- 正则表达式立即找到子字符串,而any必须在它到达正确的子字符串之前检查整个字符串几次.

但是在第二个例子中发生了什么？在子字符串不存在的情况下,正则表达式非常慢!这让我感到惊讶,因为从理论上讲,正则表达式只需要遍历字符串一次,而any表达式必须经过字符串3次.这有什么不对？我的正则表达式有问题,或者Python正则表达式在这种情况下是否很慢？

Answer 1

请注意未来的读者

我认为正确的答案实际上是Python的字符串处理算法真的针对这种情况进行了优化,而且re模块实际上有点慢.我在下面写的是真的,但可能与我在问题中的简单正则表达式无关.

原始答案

显然这不是一个随机的侥幸 - Python的re模块真的很慢.看起来它在找不到匹配时使用了递归回溯方法,而不是构建DFA并模拟它.

它使用回溯方法,即使正则表达式中没有反向引用!

这意味着在最坏的情况下,Python正则表达式采用指数而非线性的时间!

这是一篇非常详细的文章,描述了这个问题:http: //swtch.com/~rsc/regexp/regexp1.html

我认为这张图接近尾声总结了它简洁: