当字符串中有空格时,Python正则表达式会变慢

Question

我想使用Pythons regex模块匹配字符串.

在我的情况下,我想验证字符串的开始,结束和由"_"组合的大写字母组成.例如,以下字符串有效:"MY_HERO2".以下字符串无效:"_MY_HREO2","MY HERO2","MY_HERO2_"

要验证字符串,我使用以下代码:

import re
my_string = "MY_HERO"   

p = re.compile("^([A-Z,0-9]+_??)+[A-Z,0-9]$")
if p.match(my_string):
    print "validated"

那我的问题是什么？验证包含空格的长字符串非常非常慢.我怎么能避免这个？我的模式错了吗？这种行为的原因是什么？

这是一些数字:

MY_HERO2 --> 53 ms
MY_SUPER_GREAT_UNBELIEVABLE_HERO --> 69 microseconds
MY_SUPER_GREAT_UNBELIEVABLE HERO --> 223576 microseconds
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO --> 15 microseconds
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO --> 979429 microseconds

感谢您的提名和提前回复.:-)保罗

Answer 1

那我的问题是什么？

问题是灾难性的回溯.正则表达式引擎尝试了很多变化,这需要花费很多时间.

让我们用一个非常简单的例子来试试这个:A_B D.

发动机首先匹配A与[A-Z,0-9]+那么它现在尝试_??,但因为它是可选的(懒惰)它跳过它,现在,这已经完成([A-Z,0-9]+_??)+.

现在引擎尝试匹配,[A-Z,0-9]但是_字符串中有一个,所以它失败了,现在它需要回溯,所以它重新进入([A-Z,0-9]+_??)+最后一次失败并尝试_??成功的地方.

现在引擎([A-Z,0-9]+_??)+再次退出并尝试匹配[A-Z,0-9]并成功,然后它尝试匹配字符串结尾$但失败,现在它回溯并([A-Z,0-9]+_??)+再次进入.

我希望你能看到它的发展方向,因为我已经分层写了它并且我们还没有到达空间角色 - 实际上你的正则表达式中没有接受的任何字符,例如#or %等会导致这个,而不仅仅是空白 - 这个是一个很小的例子,在你的长字符串的情况下,它必须做这几百次,直到它能够匹配整个字符串或失败,因此大量的时间.

验证包含空格的长字符串非常非常慢.

再次,这是由于回溯和地狱的变化.

我怎么能避免这个？

您可以使用此正则表达式:

^([A-Z0-9]_?)*[A-Z0-9]$

这样可以确保字符串以大写或数字开头,后跟可选项_,重复此操作一次或多次,并确保最后有一个大写字母或数字.

我的模式错了吗？这种行为的原因是什么？

你的表达没错,但效率很低.

([A-Z,0-9]+_??)+[A-Z,0-9]$
          ^  ^ ^
        You  |see those two, they are a lot of trouble together 
             |
            These two ?? with the the other two + on the inside and outside, hell :)