9

我想匹配字符串，使用 Pythons 正则表达式模块。

就我而言，我想验证字符串是否由“_”组合的大写字母开始、结束和组成。例如，以下字符串是有效的：“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

提前感谢您的回答和回复。:-) 保罗

4

2 回答 2

13

那么我的问题是什么？

问题是灾难性的回溯。正则表达式引擎正在尝试大量变体，这需要花费大量时间。

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

引擎首先匹配Athen[A-Z,0-9]+它现在尝试_??但由于它是可选的（惰性）它现在跳过它，并且 this has finished ([A-Z,0-9]+_??)+。

现在引擎尝试匹配[A-Z,0-9]，但_字符串中有 a 所以它失败了，现在它需要回溯，所以它重新进入([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 :)
于 2013-08-28T10:45:47.190 回答
0

您可以使用这个简单的正则表达式获得相同的结果：

import timeit

stmt = '''
import re
reg = '^(?:[A-Z0-9][A-Z0-9_]*)?[A-Z0-9]$'
p = re.compile(reg)
p.match('%s')
'''

str_list = ['MY_HERO2', 'MY_SUPER_GREAT_UNBELIEVABLE_HERO', 'MY_SUPER_GREAT_UNBELIEVABLE HERO', 'MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO', 'MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO']

for s in str_list:
    t = timeit.timeit(stmt%s, number=1000)
    print '%s: %s' % (s, t)

import re
reg = '^(?:[A-Z0-9][A-Z0-9_]*)?[A-Z0-9]$'
p = re.compile(reg)
for s in str_list:
    result = p.match(s) is not None
    print '%s: %s' % (s, result)

结果：

MY_HERO2: 0.00375986099243
MY_SUPER_GREAT_UNBELIEVABLE_HERO: 0.00417900085449
MY_SUPER_GREAT_UNBELIEVABLE HERO: 0.00534510612488
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO: 0.00419306755066
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO: 0.00567102432251

MY_HERO2: True
MY_SUPER_GREAT_UNBELIEVABLE_HERO: True
MY_SUPER_GREAT_UNBELIEVABLE HERO: False
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO: True
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO: False
于 2013-08-28T11:04:08.010 回答