为什么这需要很长时间才能匹配？ 这是一个错误？
我需要匹配的Web应用程序中的某些url，即/123,456,789 ，并写了这个正则expression式匹配的模式：
r'(\d+(,)?)+/$'
我注意到它似乎没有评估，即使在testing模式几分钟后：
re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523')
预期的结果是没有匹配。
然而，这个expression式几乎立即执行（注意结尾的斜线）：
re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523/')
这是一个错误？
有一些灾难性的回溯正在进行，这将导致指数的处理量取决于不匹配string的长度。 这与你的嵌套重复和可选的逗号（即使一些正则expression式引擎可以确定这不会是尝试所有多余的重复匹配）。 这是通过优化expression式来解决的。
最简单的方法是只查找1+数字或逗号，后跟斜杠和string的结尾： [\d,]+/$ 。 然而，这不是完美的，因为它会允许像,123,,4,5/ 。
为此，您可以使用初始尝试的稍微优化的版本： (?:\d,?)+/$ 。 首先，我让你的重复组不捕获 （ (?:...) ），这是不必要的，但它提供了一个“更清洁的匹配”。 接下来，也是唯一关键的一步，因为小组已经在重复，所以我不再重复小组内部的工作。 最后，我删除了可选的不必要的组,因为? 只影响最后一个字符。 几乎这将会寻找一个数字，也许一个逗号，然后重复，最后跟着一个尾随/ 。
这仍然可以匹配一个奇怪的string1,2,3,/ ，所以对于它的heck，我改善了你的原始正则expression式负面向后看 ： (?:\d,?)+(?<!,)/$ 。 这将断言在尾部之前没有直接的逗号。
首先，我必须说这不是一个BUG 。 正因为如此，它尝试了所有的可能性，这需要时间和计算资源。 有时它可以吞噬很多时间。 当它变得非常糟糕时，它被称为灾难性的回溯 。
这是python源代码中findall函数的代码：
def findall(pattern, string, flags=0): """Return a list of all non-overlapping matches in the string. If one or more groups are present in the pattern, return a list of groups; this will be a list of tuples if the pattern has more than one group. Empty matches are included in the result.""" return _compile(pattern, flags).findall(string)
正如你所看到的，只是使用compile（）函数，所以基于_compile()函数，实际使用Python的正则expression式匹配使用Traditional NFA ，并基于这个简短的解释在Mastering正则expression式，正规expression式回溯第三版，由杰弗里EF弗里德尔 ！
NFA引擎的本质是这样的：它依次考虑每个子expression式或组件，并且每当需要在两个同样可行的选项之间做出决定时，就select一个并记住另一个，以便在需要时返回。 必须在行动过程中作出决定的情况包括任何有量词的人（决定是否尝试另一场比赛）和轮换（决定哪一个本来的尝试，以及哪个稍后离开）。 无论采取什么样的行动，如果成功，正则expression式的其余部分也是成功的，则匹配结束。 如果正则expression式的其余部分最终导致失败，则正则expression式引擎知道它可以回溯到它select第一个选项的位置，并且可以通过尝试另一个选项继续匹配。 这样，它最终尝试正则expression式的所有可能的排列（或者至lessfind所需的直到find一个匹配）。
让我们进入你的模式 ：所以你有r'(\d+(,)?)+/$'这个string'12345121,223456,123123,3234,4523,523523'我们有这个步骤：
- 首先，string的第一部分（
12345121）与\d+匹配，然后与(,)?匹配(,)?。 - 然后基于第一步，整个string在分组之后由于
+而匹配（(\d+(,)?)+） - 那么最后，没有什么可以匹配
/$。 因此，(\d+(,)?)+需要在最后检查/$之前“回溯”到一个字符。 再次，它没有find任何适合的匹配，所以之后（（））回到原点，那么\d+将会回溯，并且这个回溯将继续结束直到它返回None。 所以根据string的长度，需要花费很多时间，在这种情况下，这个时间非常长，并且它会完全创build一个嵌套的量词 ！
作为一个近似的基准testing，在这种情况下，你有39个字符，所以你需要3 ^ 39回溯尝试 （我们有3 个回溯方法）。
现在为了更好的理解，我在测量程序的运行时间的同时改变了string的长度：
'12345121,223456,123123,3234,4523,' 3^33 = 5.559060567×10¹⁵ ~/Desktop $ time python ex.py real 0m3.814s user 0m3.818s sys 0m0.000s '12345121,223456,123123,3234,4523,5' 3^24 = 1.66771817×10¹⁶ #X2 before ~/Desktop $ time python ex.py real 0m5.846s user 0m5.837s sys 0m0.015s '12345121,223456,123123,3234,4523,523' 3^36= 1.500946353×10¹⁷ #~10X before ~/Desktop $ time python ex.py real 0m15.796s user 0m15.803s sys 0m0.008s
所以为了避免这个问题，你可以使用下面的方法之一 ：
- primefaces分组 （目前不支持Python，创build一个RFE将其添加到Python 3）
- 通过打破嵌套组来分开正则expression式来减less回溯的可能性。
为了避免灾难性的回溯，我build议
r'\d+(,\d+)*/$'
