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

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 换成 5000，它不仅给了我正确的答案，因为 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 session 后，第一次调用 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源代码