为什么提高精度会使这个程序更快？

Question

我在Project Euler上解决问题26,我需要计算1/n的重复部分的长度,其中n是1到1000之间的所有整数,并且看哪个数字是最长的重复部分.这意味着我需要更精确地完成我的部门.所以我通过更改来调整我的小数精度getContext().prec,但是以某种方式提高精度使程序更快.我使用Python 3.7运行了这个程序.这是代码:

import re
import time
s = time.time()
from decimal import *
getcontext().prec = 500 #This part
recurring = 0
answer = 0
p = re.compile(r"([0-9]+?)\1{3,}")
for i in range(1, 1000):
    f = p.search(str(Decimal(1) / Decimal(i))[5:])
    if f:
        number = f.group(1)
        if len(str(number)) > len(str(recurring)):
            recurring = number
            answer = i

print(answer)
print(time.time() - s)

这是我使用500的精度时的结果:

>>> print(answer)
349
>>> print(time.time() - s)
2.923844575881958

......这就是我使用5000的精度时得到的:

>>> print(answer)
983
>>> print(time.time() - s)
0.07812714576721191

我用500交换500,不仅因为1/answer的重复部分可能超过500而给了我正确的答案,但它也快得多.我用在线Python解释器试过这个,它也给了我类似的结果.为什么会这样？

Answer 1

它是正则表达式中 + 和 \1 的组合

方法

我使用了以下测试代码：

import time
import re
import string
t=time.time()
re.compile() # I tried differend regexes here
print(time.time()-t)
def test(n):
    t=time.time()
    match = rex.search(string.ascii_lowercase*n)
    print(match, time.time()-t)

重新启动 python 会话后，第一次调用花费的时间re.compile比后续编译同一正则表达式的时间更长。

                                        compile(sec)   search (sec)    
REGEX                                   1st     2nd    short   long string
r"(abcdefghijklmnopqrstuvwxyz){6,}"     10^-4   10^-5  10^-5   10^-5
r"(abcdefghijklmnopqrstuvwxyz)\1\1\1\1" 10^-4   10^-5  10^-6   10^-6
r"([a-z]+?)\1\1\1\1"                    10^-4   10^-5  10^-4   10^-5 
r"([a-z]+)\1\1\1\1"                     10^-4   10^-5  10^-4   10^-5
r"([a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z][a-z])\1\1\1\1"
                                        10^-4  10^-5  10^-6  10^-6

有趣的是，r"([a-z]+?)\1\1\1"对于太短的字符串有时也会很快（10^-5 秒）。

讨论

编译 rexex 时涉及一些缓存，但这不是这里的原因。

看来+组内的运算符（贪婪和非贪婪）和正则\1表达式中的 的组合有问题。由于某种原因，这种组合如果实际匹配，则比不匹配要快。

要了解更多信息，我们可能必须了解该sre模块的 C 源代码