Почему повышение точности делает эту программу быстрее?

Question

Я решал задачу 26 в Project Euler, где мне нужно вычислить длину повторяющейся части 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

Что-то происходит в преддверии == 4000. Все ответы равны 983, а время изменяется незначительно линейно от 4000 до. Может быть, там поближе.

Существует также небольшое падение около 2000 года. Вам нужно измерить отдельно время, прошедшее во время десятичного деления, и время, прошедшее во время поиска по регулярному выражению, чтобы получить больше информации.

На этом изображении: предварительное (горизонтальное) и время в секундах (вертикальное)

Answer 2

Это комбинация + и \ 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 в регулярном выражении ошибочна. По какой-то причине эта комбинация быстрее, если она действительно совпадает, чем если она не совпадает.

Чтобы узнать больше, мы, вероятно, должны понимать исходный код C модуля sre