Внезапное снижение скорости итерации Python через 10 секунд. ⇐ Python

[Anonymous]

Я пишу код на 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 секунд он работает со скоростью около 10 000 итераций/с, но затем внезапно снижается до 1 000 итераций/с. Я попробовал это с большим входом в 10 миллионов, и происходит то же самое, работая со скоростью 10 тысяч и/с только в течение 10 секунд. После более чем 30 минут работы она падает до 100 об/с.
Есть ли узкое место, которое не позволяет использовать слишком много памяти или вычислительной мощности? Или что-то не так в моем коде?
Редактировать: похоже, что причина в постоянно увеличивающейся длине числа, которое нужно искать. Как мне оптимизировать этот поиск, чтобы он не замедлялся с каждым увеличением количества цифр?

Подробнее здесь: https://stackoverflow.com/questions/793 ... 10-seconds