可以更有效地編寫這種遞歸嗎？

我有一個層次結構的組織，它是一個樹，如果父節點贊助孩子，節點就是一個孩子。看來我只能通過可以更有效地編寫這種遞歸嗎？

downline=user.get_team(user, [])

遍歷樹與此代碼

def get_team(self, person, team): 
    firstline = User.query(User.sponsor == person.key).fetch(99999999) 
    if firstline: 
     for person in firstline: 
      team.append(person) 
      newdownline = self.downline(person, team)   
    return team

使用上面，我可以得到用戶的組織，而是有沒有更有效的方法，因爲我必須這樣做很多時候只有一個請求，那麼多遞歸可能是無效的？或者將代碼罰款，因爲它可以正確地遍歷樹？在我的第一個版本，我用三個變量，我發現我可以在代碼重新排列只有兩個變量，而不是這樣的：

def downline(self, person, team, teamlist): 
    firstline = User.query(User.sponsor == person.key).fetch(99999999) 
    if firstline: 
     for person in firstline: 
      teamlist.append(person) 
      newdownline = self.downline(person, team, teamlist)   
      team.append(newdownline) 
    return teamlist

我發現，是不是真的需要在團隊列表變量，所以我刪除它。我做的方式，它是先用一個變量太多：

people = user.downline(user, [], [])

來源

2012-03-10 Niklas Rosencrantz

遞歸在哪裏？你的意思是迭代'firstline'嗎？ – 2012-03-10 00:21:00

newdownline = self.downline（person，team，teamlist – 2012-03-10 00:30:29

）您可以通過刪除'person'參數，比較'self.key'和循環中調用'person.downline'來優化可讀性。程序是？你確定遞歸是瓶頸嗎？ – 2012-03-10 00:50:16

是的，有這樣做，這取決於你的計算折衷的更爲有效的方法。

您目前正在對樹進行深度優先遍歷，這是一種非常好的方法。你可以通過緩存結果在一些內存使用爲代價增加一些速度，所以：

if person.id in downline_cache: 
     team.append(downline_cache[person.id]) 
else: 
     downline_cache[person.id] = results 
     team.append(results)

如果樹是相當小的，你可以只緩存整個事情的前期，每個線程一次。這需要比你所做的更多的RAM，但是比每次關心結果時進行深度優先遍歷要快得多。很大程度上取決於您的使用模式和您正在存儲的數據量。

如果您使用緩存，則必須確保您有一些方法來處理基礎數據更改，包括超時和「最終正確」類型保證，或跟蹤何時以及如何擦除緩存，或緩存的元素。

來源

2012-03-13 17:35:20

感謝您的非常有趣的答案。 – 2012-03-19 14:48:43

可以更有效地編寫這種遞歸嗎？

回答

相關問題