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

我用 5000 交换了 500，它不仅给了我正确的答案，因为 1/answer 的重复部分可能比 500 长，而且速度也快得多。我已经使用在线 Python 解释器进行了尝试，它也给了我类似的结果。为什么会这样？

标签： pythonpython-3.xperformance

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 源代码