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

Question

我正在解决欧拉计划的第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解释器上尝试过，也得到了类似的结果。为什么会这样呢？

- 0''

---

请注意：我在本地机器上多次执行了您的代码，并得到了一致的结果：精度为500时为1.5804040432，精度为5000时为1.96949100494。实际答案与您的情况相同。您能告诉我您使用的在线Python解释器是哪一个吗？ - Max Kapsecker

我在这里得到了类似的行为，349是1.5289030075073242，983是0.09225702285766602。@MaxKapsecker 我是在Anaconda安装的Python 3.6上使用Spyder运行的。 - Paritosh Singh

我在 Ubuntu 14.04 上使用 Python 2.7.6 编写的代码中，对于精度为 500，得到了 349 ~ 1.40679907799 的结果；对于精度为 5000，得到了 983 ~ 2.08120393753 的结果。 - duong_dajgja

@MaxKapsecker https://www.onlinegdb.com/online_python_interpreter - 0''

我一直在使用Python 2.7。在我的本地机器上使用Python 3.6得到了与@HerO_0110相同的结果。此外，结果表明，在Python 2.7上运行代码时，使用不同的值（例如1000和5000）也显示出不一致性。对于1000，581〜3.19620895386，对于5000，983〜2.04031896591。 - Max Kapsecker

同样适用于 re.search(r"([a-z]+?)\1{3,}", string.ascii_lowercase*4)。如果找到匹配项，则速度更快。 - Bernhard

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秒）。

讨论

编译正则表达式时会涉及到一些缓存，但这不是本例的原因。

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

要了解更多信息，我们可能需要理解模块的C源代码。

- Bernhard

Answer 2

在prec == 4000附近发生了一些事情。所有答案都等于983，时间只是从4000开始略微线性变化。也许需要仔细查看。

在2000附近还有一个小的下降。您需要分别测量十进制除法期间经过的时间和正则表达式搜索期间经过的时间以获取更多信息。

在这张图片上：prec（水平）与时间（垂直）的秒数

- user2622016

---

分析显示问题出在re.search上。此外，在迭代到1000的大多数情况下都很快，但有些特殊情况需要很长时间。（例如，对于prec=2000，有27个案例需要0.08秒，而其余的很快）当prec>4000时，这些特殊情况就消失了。 - Bernhard