惊讶于python中的良好递归性能
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了惊讶于python中的良好递归性能，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1675字，纯文字阅读大概需要3分钟。
内容图文
我写了这个相当差的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 64bits).
解决方法:
这是因为你每次都重新计算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
我认为剩下的微小差别是因为……在范围内(…)比等效的while循环更快,因为for循环可以使用生成器而不必执行一堆比较.
内容总结
以上是互联网集市为您收集整理的惊讶于python中的良好递归性能全部内容，希望文章能够帮你解决惊讶于python中的良好递归性能所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。