python - время выполнения цикла увеличивается внезапно

Question

У меня есть небольшой программный продукт, который вычисляет количество факторов для каждого номера треугольника, чтобы увидеть, что первый из них имеет больше, чем число X факторов (да, это проблема проектировщика, число 12 , хотя я еще не решил) ... так как я пытаюсь сделать X несколько случайных значений, чтобы увидеть, что делает код и через какое время, я заметил кое-что странное (по крайней мере для меня): пока X =47 время выполнения, очевидно, увеличивается обычным образом, но когда X = 48, оно увеличивается больше, чем обычно, и вызовы функций намного превышают скорость, это (взрывается), если я скажу, что ... почему это происходит ??

код:

def fac(n):
    c=0
    for i in range (1,n+1):
        if n%i==0:
            c=c+1
    return c

n=1

while True:
    summ=0
    for i in range (1,n+1):
        summ=summ+i
    if fac(summ)>X:
        break
    n=n+1

print summ

и при профилировании:

when X=45 :  314 function calls in 0.027 CPU seconds
when X=46 :  314 function calls in 0.026 CPU seconds
when X=47 :  314 function calls in 0.026 CPU seconds
when X=48 :  674 function calls in 0.233 CPU seconds
when X=49 :  674 function calls in 0.237 CPU seconds

Я предполагаю, что если я продолжу, я столкнусь с другими моментами, что системные вызовы увеличиваются и время внезапно увеличивается,и раньше были такие моменты, но время было таким маленьким, что это не имело большого значения .. Почему вызовы функций внезапно увеличиваются ??Разве это не должно просто вызвать функцию еще раз для нового значения ??

PS я использую cProfile в качестве профилировщика, и X в коде здесь только для демонстрации, я пишу значениепрямо в коде ... заранее спасибо ...

Answer 1

Рассматривали ли вы действительные значения?

Первое треугольное число с более чем 47 факторами - это T (104) = 5460, что имеет 48 факторов.

Но первое треугольноечисло с более чем 48 факторами равно T (224) = 25200, что имеет 90 факторов.Поэтому неудивительно, что для этого требуется намного больше работы.

Если ваш код работает до T ( n ), то он вызывает range 2 n раз и fac n раз, всего 3 n вызовов функций.Таким образом, для T (104) требуется 312 вызовов функций, а для T (224) требуется 672 вызова функций.Предположительно, есть где-то 2 служебных вызова накладных расходов, которые вы нам не показываете, что объясняет результаты профилирования, которые вы получаете.

---

Ваша текущая стратегия не даст вам ответа на вопрос Project Eulerпроблема.Но я могу дать некоторые подсказки.

• Вам нужно начинать заново с summ=0 каждый раз, когда вы вычисляете треугольное число?
• Вам нужно циклически повторять все числадо n , чтобы определить, сколько у него делителей?Может ли быть более быстрый путь?(Сколько делителей у 2 ¹⁶ = 65536? Нужно ли циклически перебирать все числа от 1 до 65536?)
• Сколько делителей имеют треугольные числа?(Посмотрите на некоторые маленькие треугольные числа, где вы можете вычислить ответ.) Можете ли вы увидеть какие-либо шаблоны, которые помогут вам вычислить ответ для гораздо больших треугольных чисел?

Answer 2

Если вы проверите вывод, вы увидите несколько всплесков (внезапное увеличение) во время выполнения.

Причина в том, что количество необходимых циклов не увеличивается постепенно, а резко. Распечатайте n после цикла while True, и вы увидите его.

Примечание: Эйлер - математический сайт, не пишите алгоритмы грубой силы;)