为什么在python中后向递归比前向递归执行得快？
为什么在python中后向递归比前向递归执行得快？
提问于 2014-05-08 02:32:02
我用Python做了一个算法，用来计算获得不同硬币面额的钱的方式的数量：
@measure
def countChange(n, coin_list):
maxIndex = len(coin_list)
def count(n, current_index):
if n>0 and maxIndex>current_index:
c = 0
current = coin_list[current_index]
max_coeff = int(n/current)
for coeff in range(max_coeff+1):
c+=count(n-coeff*current, current_index+1)
elif n==0: return 1
else: return 0
return c
return count(n, 0)我的算法使用索引来获得硬币面值，正如您所看到的，我的索引在我进入的每个堆栈帧中都在增加。我意识到算法也可以这样写：
@measure
def countChange2(n, coin_list):
maxIndex = len(coin_list)
def count(n, current_index):
if n>0 and 0<=current_index:
c = 0
current = coin_list[current_index]
max_coeff = int(n/current)
for coeff in range(max_coeff+1):
c+=count(n-coeff*current, current_index-1)
elif n==0: return 1
else: return 0
return c
return count(n, maxIndex-1)这一次，索引在我进入的每个堆栈帧中递减。我比较了这些函数的执行时间，得到了一个非常值得注意的差异：
print(countChange(30, range(1, 31)))
print(countChange2(30, range(1, 31)))
>> Call to countChange took 0.9956174254208345 secods.
>> Call to countChange2 took 0.037631815734429974 secods.如果我甚至没有缓存结果，为什么算法的执行时间会有很大的差异？为什么索引的递增顺序会影响这个执行时间？
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-05-08 03:15:40
据我所知，这与动态编程没有任何关系。仅仅颠倒索引不应该使某些东西变得“动态”。
实际情况是，该算法是输入敏感的。尝试以相反的顺序输入。例如,
print(countChange(30, list(reversed(range(1, 31)))))
print(countChange2(30, list(reversed(range(1, 31)))))就像一些排序算法对于已经排序的数据非常快，而对于反向数据非常慢一样，你可以在这里得到这种算法。
在输入不断增加的情况下，countChange需要更多的迭代才能得到最终的答案，因此似乎要慢得多。然而，当输入减少时，性能特征是相反的。
Stack Overflow用户
发布于 2014-05-08 02:40:26
三个数字组合并不是很大
原因是往前走你必须探索每一种可能性，然而当你向后走时，你可以消除大量无效的解决方案，而不必实际计算它们
继续往前，你会调用count 500k次
向后返回你的代码只会进行30k次调用...
您可以通过对调用进行记忆(或更改算法以避免重复调用)来加快这两个过程的执行速度
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23525603
复制相关文章
相似问题
腾讯云开发者
