我为质因数分解编写了这个相当糟糕的 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 64 位)。
最佳答案
这是因为你每次都在重新计算 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
循环可以使用生成器,而不必执行一堆比较。
关于python - 对 python 中良好的递归性能感到惊讶,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38784246/