看似很小的python正则表达式变化带来了2个数量级的性能变化

Question

我有一个很慢的python正则表达式，如果我简单地删除regex的最后一行，速度将增加两个数量级!下面是我复制的例子:

import re
import timeit
mystr = "14923KMLI MLI2010010206581258   0.109 b                              M     M     M     0    09 60+              "
basere = r"""
(?P<wban>[0-9]{5})
(?P<faaid>[0-9A-Z]{4})s
(?P<id3>[0-9A-Z]{3})
(?P<tstamp>[0-9]{16})s+
[?s*((?P<vis1_coef>-?d+.d*)|(?P<vis1_coef_miss>M))s*]?s*
[?(?P<vis1_nd>[0-9A-Za-z?$/ ])]?s+
((?P<vis2_coef>d+.d*)|(?P<vis2_coef_miss>[M ]))s+(?P<vis2_nd>[A-Za-z?$ ])s+
...............s+
[?s*((?P<drct>d+)|(?P<drct_miss>M))s+
((?P<sknt>d+)|(?P<sknt_miss>M))s+
((?P<gust_drct>d+)+?|(?P<gust_drct_miss>M))s*]?s+
"""
additional = r"""
[?((?P<gust_sknt>d+)R?L?F*d*+?|(?P<gust_sknt_miss>M))s*]?s+
"""
P1_RE = re.compile(basere + additional, re.VERBOSE)
P2_RE = re.compile(basere, re.VERBOSE)

for myre in ["P1_RE", "P2_RE"]:
    statement = "%s.match('%s')" % (myre, mystr)
    res = timeit.timeit(statement, "from __main__ import %s" % (myre,), 
                        number=1000)
    print('%s took %.9f per iteration' % (myre, res / 1000.))
# result on my laptop, python 2.6 and 3.3 tested
# P1_RE took 0.001489143 per iteration
# P2_RE took 0.000019991 per iteration

所以P1_RE和P2_RE之间的唯一区别是额外的正则表达式。你知道我做错了什么吗?

Answer 1

这是因为回溯;这是导致正则表达式效率低下的主要原因。

您删除的最后一行需要匹配至少1个数字或M，后跟空格，以及一路上的许多许多可选内容。

倒数第二行:

((?P<gust_drct>d+)+?|(?P<gust_drct_miss>M))s*]?s+

最初匹配最后一部分，即60+和后面的空格，不为最后一行留下任何内容。因此，regex无法匹配并每次回溯一个字符以尝试匹配最后一行。问题是，regex将尝试匹配很多东西，并且对于regex回溯的每个字符，会有越来越多的尝试匹配。

在正则表达式匹配之前，它实际上已经拒绝了之前正则表达式的前几行已经匹配的相当多的字符。

---

一个简单的例子是字符串(10a):

aaaaaaaaaa

和正则表达式:

a+a+a+a+a+a+a+a+a+a+

正则表达式a+的第一部分将匹配整个字符串(因为+是贪婪的)，但是，它需要匹配更多的a，因为正则表达式的下一部分是a+。然后引擎回溯一个字符，使第一个a+匹配aaaaaaaaa(9个a)，第二个匹配最后一个a。

下一个是第三个a+，由于没有更多的a匹配，正则表达式将回溯一个字符。由于第二个a不能回溯，它将是第一个a+，并匹配aaaaaaaa(8个a)，然后第二个a+将匹配最后一个aa。现在没有更多的a了，所以第二个a+将回溯到匹配倒数第二个a，最后，第三个a+可以匹配最后一个a。

看前3个a+做了多少?现在想象一下，检查每一个可能的匹配，直到所有匹配?

---

通常，如果你根本不想回溯，你会使用原子组和所有格量词，但python不支持这些，至少re模块不支持(然而regex模块支持)。

您可能需要修改您的regex并尝试查看它应该真正匹配的内容，真正可选的内容，特别是捕获组中可能的空格。