30

考虑这个 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 正则表达式很慢？

4

4 回答 4

27

给未来的读者的注意事项

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

原始答案

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

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

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

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

我认为这张接近结尾的图表简洁地总结了它： 各种正则表达式实现的性能图，时间与字符串长度

于 2012-06-25T15:31:54.057 回答
3

我的同事找到了 re2 库 ( https://code.google.com/p/re2/ )？有一个 python 包装器。在某些系统上安装有点麻烦。

对于一些复杂的正则表达式和长字符串，我遇到了同样的问题——re2 显着加快了处理时间——从几秒到几毫秒。

于 2014-10-07T17:11:38.103 回答
2

正则表达式如此缓慢的原因是因为它不仅必须遍历整个字符串，而且还必须对每个字符进行多次计算。

第一个只是这样做：

Does f match h? No.
Does b match h? No.
Does h match h? Yes.
Does e match e? Yes.
Does l match l? Yes.
Does l match l? Yes.
Does o match o? Yes.
Done. Match found.

第二个这样做：

Does f match g? No.
Does b match g? No.
Does h match g? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match d? No.
Does b match d? No.
Does h match d? No.
Does f match b? No.
Does b match b? Yes.
Does a match y? No.
Does h match b? No.
Does f match y? No.
Does b match y? No.
Does h match y? No.
Does f match e? No.
Does b match e? No.
Does h match e? No.
... 999 more times ...
Done. No match found.

我只能推测 theany和 regex 之间的区别，但我猜 regex 速度较慢主要是因为它在高度复杂的引擎中运行，并且使用状态机的东西和所有东西，它只是不如特定实现那么有效( in)。

在第一个字符串中，正则表达式几乎会立即找到匹配项，而any在找到任何内容之前必须遍历该字符串两次。

然而，在第二个字符串中，any执行与正则表达式基本相同的步骤，但顺序不同。这似乎表明any解决方案更快，可能是因为它更简单。

特定代码比通用代码更有效。任何关于问题的知识都可以用于优化解决方案。简单代码优于复杂代码。本质上，当模式接近字符串的开头时，正则表达式更快，但是in当模式接近字符串的结尾时，正则表达式更快，或者根本找不到。

免责声明：我不知道 Python。我知道算法。

于 2012-06-25T14:17:00.997 回答
1

您有一个由三个正则表达式组成的正则表达式。如果正则表达式不检查这三遍，您认为这究竟是如何工作的？:-) 计算没有魔法，你仍然需要做三项检查。

但是正则表达式将逐个字符地执行每三个测试，而“one()”方法将检查整个字符串是否有一个匹配项，然后再进行下一个匹配项。

在第一种情况下，正则表达式要快得多，因为您检查最后匹配的字符串。这意味着one()需要首先查看整个字符串以查找“foo”，然后查找“bar”，然后查找匹配的“hello”。首先移动“hello”，并且 one() 和 two() 的速度几乎相同，因为在这两种情况下完成的第一个匹配都成功了。

正则表达式比“in”要复杂得多，所以我希望它会更慢。我怀疑当您使用“|”时这种复杂性会增加很多，但是我还没有阅读 regexp 库的源代码，所以我知道什么。:-)

于 2012-06-25T14:22:39.110 回答