考虑一下这个 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 正则表达式很慢?
最佳答案
future 读者须知
我认为正确的答案其实是Python的字符串处理算法真的针对这种情况进行了优化,而re
模块其实慢了一点。我在下面写的是真的,但可能与我在问题中的简单正则表达式无关。
原答案
显然这不是偶然的——Python 的 re
模块确实比较慢。看起来它在找不到匹配项时使用递归回溯方法,而不是构建 DFA 并对其进行模拟。
即使正则表达式中没有反向引用,它也使用回溯方法!
这意味着在最坏的情况下,Python 正则表达式需要指数而非线性时间!
这是一篇描述该问题的非常详细的论文: http://swtch.com/~rsc/regexp/regexp1.html
我认为这个接近结尾的图表简洁地总结了它:
关于python - Python中的正则表达式出乎意料地慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11190835/