Удивлен хорошей рекурсивной производительностью в python

Я написал эту довольно плохую функцию Python для простой факторизации:

import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

и это работало, как и ожидалось, теперь меня интересовало, может ли производительность быть лучше при использовании итеративного подхода:

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r

Но то, что я заметил (хотя функции дали одинаковые результаты), заключалось в том, что итеративная функция выполнялась дольше. По крайней мере, у меня было чувство, когда я делал это:

number = 31123478114123
print(factor(number))
print(factor_it(number))

поэтому я измерил:

setup = '''
import math

def factor(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if not n % i:
            return [i] + factor(n//i)
    return [n]

def factor_it(n):
    r = []
    i = 2
    while i < int(math.sqrt(n)+1):
        while not n % i:
            r.append(i)
            n //= i
        i +=1
    if n > 1:
        r.append(n)
    return r
'''

import timeit

exec(setup)

number = 66666667*952381*290201
print(factor(number))
print(factor_it(number))

print(timeit.Timer('factor('+str(number)+')',setup=setup).repeat(1,1))
print(timeit.Timer('factor_it('+str(number)+')',setup=setup).repeat(1,1))

И вот что я получил:

[290201, 952381, 66666667]
[290201, 952381, 66666667]
[0.19888348945642065]
[0.7451271022307537]

Почему рекурсивный подход в этом случае быстрее, чем итеративный?

Я использую WinPython-64bit-3.4.4.2 (Python 3.4.4 64bit).

Ответы на вопрос(1)

Решение Вопроса

Это потому, что вы пересчитываетеsqrt каждый раз. Эта модификация работает так же быстро, как и ваша рекурсивная версия:

def factor_it2(n):
    r = []
    i = 2
    lim = int(math.sqrt(n)+1)
    while i < lim:
        while not n % i:
            r.append(i)
            n //= i
        lim = int(math.sqrt(n)+1)
        i += 1
    if n > 1:
        r.append(n)
    return r

timeit дает мне эти времена:

factor      0.13133816363922143
factor_it   0.5705408816539869
factor_it2  0.14267319543853973

Я думаю, что крошечная разница, которая остаетсяfor … in range(…) быть быстрее, чем эквивалентwhile петля, какfor Цикл может использовать генератор вместо того, чтобы выполнять кучу сравнений.

 Wolf05 авг. 2016 г., 10:34
@MariusSiuram Хороший вопрос! Хорошо, но ... как я могу знать это раньше, когда делаю неизвестные числа? Но вы правы, может быть, я должен посмотреть на вероятности и принять этот ответ. С другой стороны, могут быть языки с дешевой рекурсией и дорогими переменными.
 Wolf05 авг. 2016 г., 10:27
Естьпо-прежнему разрыв в производительности несмотря на то, что квадратный корень вычисляется одинаково часто в обеих функциях.
 Wolf05 авг. 2016 г., 10:21
Эй, отлично! Но что интересно, не совсем так быстро;)
 Wolf05 авг. 2016 г., 10:50
@MariusSiuram Да, я думал об Эрланге. Я не учитываю действительно большие числа, поэтому производительность питонов абсолютно достаточна для моих нужд (я знаю C / C ++, но ненавижу его, когда пытаюсь просто что-то проверить). Я был просто «шокирован», что произошел хит производительности. (Я все еще полностью игнорировал вызов sqrt, когда задавал вопрос.)
 MariusSiuram05 авг. 2016 г., 10:28
@ Волк Ну, это зависит. Вы сравниваете "рекурсивную" функцию с3 звонки. Это несправедливо. Просто выберите номер какnumber = 2**8 * 3**4 * 4**3 * 5**2 * 7 * 11 * 13 * 15 и таблицы превращаются.
 MariusSiuram05 авг. 2016 г., 10:43
@ Волк первым делом думаю: не надоfactor в Python - по крайней мере, не в интерпретаторе Python, сделать расширение C, Cython или что-то в этом роде. В заголовке вы спрашивали о «производительности рекурсии», и я хочу сказать, что говорить о «рекурсии» для теста с 3 глубинами несколько неожиданно. Конечно, вы правы, для этого конкретного примера производительность странная, а также есть языки с дешевой рекурсией (возможно, Erlang?, Если я правильно помню). Но для глубоких рекурсивных функций Python перейдите к итерационным алгоритмам.

Ваш ответ на вопрос