10秒后Python迭代速度突然降低

Question

我正在用Python编写一些代码来找出第一个没有出现在圆周率的前十亿位数字中的自然数。这是我写的：

import datetime
from tqdm import tqdm
def findpi(end):
    notin = []
    stop = 0
    s1 = datetime.datetime.now()
    with open(r"C:\Users\shamm\Desktop\Text Documents\1 BILLION Digits of pi.txt", 'rt') as p:
        pi = str(p.read())
        for i in tqdm(range(1,end+1)):
            if str(i) not in pi:
                if notin == []:
                    stop = i
                notin.append(i)
    s2 = datetime.datetime.now()
    tdelta = s2 - s1
    ts = tdelta.total_seconds()
    return [notin, stop, ts]

pi = findpi(1000000)
print("Not in:", pi[0])
print("Last:", pi[1])
print("Time taken:", pi[2])

它对于小数字工作得很好，当我尝试使用前一百万个自然数时，代码突然面临封锁。在前 10 秒，它以大约 10k 迭代/秒的速度运行，但随后突然下降到 1k 迭代/秒。我尝试使用更大的输入 1000 万，同样的事情发生，以 10k it/s 的速度运行仅 10 秒。运行 30 多分钟后，速度降至 100 it/s。

是否存在限制其使用过多内存或处理能力的瓶颈？还是我的代码有问题？

Answer 1

这是预料之中的。每次达到更多位数时，速度就会减慢 10 倍。查找具有 k+1 位数字的数字所需的时间大约是查找具有 k 位数字的数字的十倍。因为它们的前 k 位数字同样难以找到，但额外的数字也匹配的可能性只有 10%。