我写了一个小的,天真的正则表达式,应该在括号内找到文本:
re.search(r'\((.|\s)*\)', name)
我知道这不是出于某些原因这样做的最好方法,但它工作得很好.我正在寻找的只是一个解释,为什么对于某些字符串,这个表达式开始呈指数级增长然后永远不会完成.昨晚,在运行此代码数月之后,我们的一台服务器突然卡住了匹配类似于以下内容的字符串:
x (y) z
我已经对它进行了实验,并确定在"y"和"z"之间的每个空间所花费的时间都会翻倍:
In [62]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (22 * ' ') + 'z')
1 loops, best of 3: 1.23 s per loop
In [63]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (23 * ' ') + 'z')
1 loops, best of 3: 2.46 s per loop
In [64]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (24 * ' ') + 'z')
1 loops, best of 3: 4.91 s per loop
但是除了空格之外的字符也没有相同的效果:
In [65]: %timeit re.search(r'\((.|\s)*\)', 'x …