为什么Python正则表达式如此缓慢？

Question

经过长时间的调试，我发现了为什么我的使用Python正则表达式的应用程序很慢。这是我发现的一个令人惊讶的问题：

import datetime
import re

pattern = re.compile('(.*)sol(.*)')

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*1000 + "sal " + "ciao mandi "*1000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

我的电脑上的输出是：

string len 220004
time spent 0:00:00.002844

string len 22004
time spent 0:00:05.339580

第一个测试字符串长度为220K，匹配成功，而且匹配速度相当快。第二个测试字符串长度为20K，不匹配，计算需要5秒钟！

我看过这篇报告http://swtch.com/~rsc/regexp/regexp1.html，它说python、perl、ruby中的正则表达式实现有些非最优的地方...难道这就是原因吗？我没想到如此简单的表达式也会出现这种情况。

添加：我的原始任务是尝试不同的正则表达式来拆分一个字符串。类似于：

for regex in ['(.*)sol(.*)', '\emph{([^{}])*)}(.*)', .... ]:
    lst = re.findall(regex, text) 
    if lst:
        assert len(lst) == 1
        assert len(lst[0]) == 2
        return lst[0]

这是为了解释为什么我不能使用split。我按照Martijn的建议用(.*?)sol(.*)替换了(.*)sol(.*)来解决我的问题。

也许我应该使用match而不是findall，但我认为这并不能解决问题，因为正则表达式将匹配整个输入，因此findall应该在第一次匹配后停止。

无论如何，我的问题更多地是关于一个正则表达式新手会遇到这个问题有多容易... 我认为理解(.*?)sol(.*)是解决方案并不简单(例如(.*?)sol(.*?)就不是)。

- Emanuele Paolini

---

不，原因不是实现方式。原因在于两个.*太宽泛并导致了灾难性的回溯。你到底想做什么？ - Casimir et Hippolyte

@casimir，灾难性回溯是实现问题。请阅读Emanuele提供的文章链接。 - alexis

@alexis：不，这种情况下的灾难性回溯是由于模式设计造成的。使用其他NFA引擎可能会得到更多或更少相同的结果。 - Casimir et Hippolyte

阅读文章。“其他NFA引擎”具有相同的实现。真正的FSA不需要任何回溯。 - alexis

另外需要注意的是，问题不是由于双重使用 (.*) 导致的。搜索 (.*)sol 的时间复杂度完全相同。实际上，如果字符串包含 sol，并且您使用 findall() 进行搜索，那么 (.*)sol 实际上会更糟糕，因为它会在跟随 sol 的子字符串上触发一个失败的回溯搜索（原始正则表达式将在成功时消耗整个字符串）。 - alexis

我遇到了同样的缓慢问题 - 等待了超过2分钟，因为字符串非常长。我安装了regex包 - 运行得很好！对于相同的字符串立即得到了结果。从这里下载：https://pypi.python.org/pypi/regex - SomethingSomething

Answer 1

Thompson NFA方法将正则表达式从默认贪婪改为默认非贪婪。普通的正则表达式引擎也可以做到相同的效果，只需将.*更改为.*?。当非贪婪表达式可行时，不应使用贪婪表达式。

有人已经为Python构建了一个NFA正则表达式解析器：https://github.com/xysun/regex 它确实在病态情况下优于默认的Python正则表达式解析器。然而，在其他所有情况下，它都表现不佳：

引用： 这个正则表达式引擎在正常输入（使用Glenn Fowler的测试套件--见下文）上表现不佳。

以牺牲典型情况为代价来修复病态情况可能是不使用NFA方法作为默认引擎的一个很好的理由，因为可以简单地避免病态情况。

另一个原因是某些特性（例如回溯引用）使用NFA方法非常困难或不可能实现。也可以参见Python Ideas邮件列表上的响应。

因此，如果将至少一个模式设置为非贪婪以避免灾难性回溯，则可以使测试性能大大提高。

pattern = re.compile('(.*?)sol(.*)')

或者根本不使用正则表达式；您可以使用str.partition()获取前缀和后缀。

before, sol, after = s.partition('sol')

例如，并非所有的文本问题都能用正则表达式解决，因此请放下锤子，看看您的工具箱中的其他工具！

另外，您可以考虑使用替代模块re，regex。该模块实现了一些基本的检查以避免病态情况的发生，无需采用 Thompson NFA 实现。引用 一个 Python bug 报告的条目跟踪 regex：

内部引擎不再解释一种字节码形式，而是遵循一组链接的节点，并且它可以以广度优先和深度优先的方式工作，这使得它在面对这些“病态”的正则表达式时性能更加优越。

相比于原来的引擎，这个引擎可以使您的病态情况快100多倍。

>>> import re, regex
>>> import timeit
>>> p_re = re.compile('(.*)sol(.*)')
>>> p_regex = regex.compile('(.*)sol(.*)')
>>> s = "ciao mandi "*1000 + "sal " + "ciao mandi "*1000
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_re as p', number=1)
2.4578459990007104
>>> timeit.timeit("p.findall(s)", 'from __main__ import s, p_regex as p', number=100000)
1.955532732012216

请注意数字；我将re测试限制为1次运行，用时2.46秒，而regex测试在不到2秒的时间内运行了100,000次。

- Martijn Pieters

---

在我的使用场景中，我想将一些文本分成两个部分，但是这种分割是通过许多不同的正则表达式实现的（我用|连接它们），其中一些比这更复杂（但不会太慢...）。因此，保持这种匹配在一个正则表达式中会很好。 - Emanuele Paolini

@EmanuelePaolini：对于分割，您可以使用re.split()，然后在sol文本之前和之后的部分根本不需要使用.*。 - Martijn Pieters

即将推出的regex模块有什么问题吗？它在大多数病态情况下都非常快，比其他模块更快。对于这个例子来说，它已经足够快了。无论如何，我投了反对票，因为我认为从比较一个经过高度优化的C实现和一个匆忙制作的纯Python实现中得出性能结论是我见过的最糟糕的基准测试之一。 - Veedrac

@MartijnPieters，然而您从中得出了结论。 - Veedrac

@Veedrac：当然，我错误地认为他们知道自己在做什么。我阅读了README中列出的基准测试结果。 - Martijn Pieters

Answer 2

我认为这与灾难性回溯无关（或者至少与我自己的理解无关）。

问题是由(.*)sol(.*)中的第一个(.*)引起的，而且正则表达式没有任何锚定。 re.findall()在索引0失败后，会在索引1、2等处重试，直到字符串的末尾。

badbadbadbad...bad
^                   Attempt to match (.*)sol(.*) from index 0. Fail
 ^                  Attempt to match (.*)sol(.*) from index 1. Fail
  ^                 Attempt to match (.*)sol(.*) from index 2. Fail (and so on)

这段代码的时间复杂度是O(n²)，其中n是字符串长度。为了解决这个问题，你可以锚定你的模式，这样在不可能匹配的位置就会立即失败。

比如(.*)sol(.*)会在一行文本中查找sol，如果它无法在行首找到匹配项，那么它在后面也找不到任何匹配项。

因此，您可以使用以下代码：

^(.*)sol(.*)

使用re.MULTILINE选项。

运行以下测试代码（从您的代码修改）：

import datetime
import re

pattern = re.compile('^(.*)sol(.*)', re.MULTILINE)

lst = ["ciao mandi "*10000 + "sol " + "ciao mandi "*10000,
       "ciao mandi "*10000 + "sal " + "ciao mandi "*10000]
for s in lst:
    print "string len", len(s)
    start = datetime.datetime.now()
    re.findall(pattern,s)
    print "time spent", datetime.datetime.now() - start
    print

（请注意，通过和失败都是220004个字符）

给出以下结果：

string len 220004
time spent 0:00:00.002000

string len 220004
time spent 0:00:00.005000

这清楚地表明现在两种情况的数量级相同。

- nhahtdh

---

这很有趣...事实上，关键在于re.search很慢，而re.match很快。然而，我尝试使用awk进行相同的搜索（但我不确定是否使用了等效的模式），似乎对于awk来说，搜索和匹配所花费的时间是一样的。也许关键在于使用NFA方法可以在线性时间内实现搜索，而重复匹配则需要二次时间。 - Emanuele Paolini

@EmanuelePaolini：awk不使用回溯引擎，这就是它快的原因。 - nhahtdh

这不就是病态回溯吗？ - Veedrac

@Veedrac：这更多是在顶层行为（引擎在当前索引的所有可能性耗尽后前进到下一个索引）。从技术上讲，您可以将其定义为“灾难性回溯”，但它与情况（a）不同，其中问题发生在引擎允许aa扩展。这2种情况的解决方案也不同。但我同意，最终任何低效都是由于过度回溯造成的。 - nhahtdh

Answer 3

^(?=(.*?sol))\1(.*)$

你可以尝试这个。这将减少回溯并更快地失败。在此处尝试您的字符串。

http://regex101.com/r/hQ1rP0/22

- vks

---

你认为它为什么会更快地失败并且回溯的次数更少？ - Jerry

所以你正在捕获并立即回溯捕获的组，并声称它通过额外的捕获更快地失败；这是怎么回事？嗯，这确实需要更长时间才能成功，并且并不能真正更快地失败。 - Unihedron

@Unihedron，我在regexhero.net上检查了一下...在一个小字符串的失败情况下，速度提高了132％，而在成功时则提高了50％。我想这是一个显着的改进。 - vks

@Jerry，它也需要更少的步骤。 - vks

@vks 在你自己的问题中已经被告知，步骤数量并不是速度的最终因素。唯一使这比 OP 的正则表达式稍快的是锚点。在 OP 的正则表达式上使用锚点，那个正则表达式比 OP 当前的正则表达式慢得多。 - Jerry