Удивлен хорошей рекурсивной производительностью в 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).