研究（）挂起

Question

此代码片段旨在在所提供文件的每一行上搜索正则表达式匹配项。re.search() 被挂在文件中包含“#”字符的行 3e+5 次。这个问题的解决方案是什么？import reprint "Started..."exp = "(.*)\$\$\$Uniqueterm:(.*)"with open("sample.txt", 'r') as file:    for line in file:         if re.search(exp, line):            print "Found match: " + re.search(exp,line).groups()[1].strip()    print "File finished..."示例输入文件（sample.txt）：abcpqr ##### (3e+5 times '#' in a single line)xyz$$$Uniqueterm: Match itqaz预期输出：Match it

Answer 1

正则表达式引擎可以达到很高的复杂性，特别是当它必须回溯时，就像你的情况一样。

因此，当要搜索的表达式很长并且您的组必须通过大量试错（即回溯）进行计算时，搜索可能需要很长时间（请参阅StackOverflow 网络上正则表达式失败的著名示例）。

2016 年 7 月 20 日，我们经历了 34 分钟的中断，从 UTC 时间 14:44 开始。找出原因花了 10 分钟，编写代码来修复它花了 14 分钟，将修复程序推出到 Stack Overflow 再次可用的点上花了 10 分钟。

直接原因是一篇格式错误的帖子，导致我们的一个正则表达式在我们的 Web 服务器上消耗了大量 CPU。该帖子位于主页列表中，这导致在每次主页视图上调用昂贵的正则表达式。...

此正则表达式已替换为子字符串函数。

我提出了一个解决方法，因为你在这里并不真正需要正则表达式，使用str.split会做并且很快，因为它只是搜索子字符串（O(N)方法）然后创建2个字符串，这相当于你正在尝试做的常用表达：

a = "foo$$$Uniqueterm:bar"

g1,g2 = a.split("$$$Uniqueterm:")

print(g1,g2)

结果

foo bar

Answer 2

您正在使用re.search以(.*). re.search在任何起始位置查找匹配项，这意味着它必须从每个可能的起始索引开始搜索，直到找到匹配项或用完要搜索的位置。前导(.*)强制从搜索起始位置开始扫描整个字符串，对于每个起始位置。

这是经典的灾难性回溯，只是部分回溯隐含在使用re.search而不是内置于正则表达式本身中。您可以调整正则表达式以消除灾难性的回溯，但为什么要使用正则表达式呢？像str.split或str.find可以很好地完成工作的基本方法。Jean-François Fabre 的回答显示了一种方法。