平衡存儲器和性能在遞歸

Question

使用收率我有產生出置換函數：

def all_perms(str): 
    if len(str) <=1: 
     yield str 
    else: 
     for perm in all_perms(str[1:]): 
      for i in range(len(perm)+1): 
       yield perm[:i] + str[0:1] + perm[i:] 

據我所知，yield需要即時計算而不是存儲在堆上的中間計算結果。這是很好的蟒蛇是not aggressive at freeing up memory。但是it takes longer to calculate。這是否意味着，它每次調用時都必須計算遞歸樹的整個分支？如果是這樣，運行時間的時間複雜度將增加N * log（N），對嗎？

如果確實yield需要每次計算整個一個分支，則在每個級別上，計算需要按照子級的數量成比例地重複，這在每個級別上相加爲N.並且由於深度是log（N），所以總和爲N * log（N）。這看起來像是一筆過大的交易。當使用yield或更好的選擇時，有一個很好的經驗法則嗎？

Answer 1

如果您檢查documentation，您會看到yield凍結了發生器的狀態。當控制流程返回時，就好像它是外部呼叫一樣，所有狀態都保持不變。

因此，由於運行時複雜性沒有差異，我不會過多擔心列表和生成器之間的性能差異。發電機的內存節省方面值得考慮，如果你經歷了大型收藏，以及創造'無限'收藏的能力。

另外，itertools.permutations。