Python 中的正则表达式出乎意料地慢

考虑下面的 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 正则表达式在这种情况下速度很慢？

未来读者请注意

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

原答案

显然这不是一个随机的侥幸 - Python 的re模块确实比较慢。看起来它在找不到匹配项时使用了递归回溯方法，而不是构建 DFA 并对其进行模拟。

即使正则表达式中没有反向引用，它也会使用回溯方法！

这意味着在最坏的情况下，Python 正则表达式需要指数时间，而不是线性时间！

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

I think this graph near the end summarizes it succinctly: