この再帰をより効率的に書くことはできますか？

Question

私は、親が子をスポンサーする場合、ノードが子であるツリーである階層的な組織を持っています。私がちょうど

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 

とツリーをたどることができそうです。しかし、私はこれをしなければならないので、そこには、より効率的な方法であります1回のリクエストで何度も何度も再帰が不十分なことがありますか？それとも、ツリーを正しくトラバースできるので、コードはうまくいくのでしょうか？私の最初のバージョンでは、私は三つの変数を使用し、私が代わりにこれの2つの変数のみにコードを並べ替えることができた：私はteamlist変数が本当に必要でないことが判っ

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, [], [])

Answer 1

：。私がやった方法は、それはあまりにも多くの一つの変数で最初でした

現在、ツリーの深さ優先トラバースを行っています。これは完璧な方法です。あなたはそう、いくつかのRAMの使用量を犠牲にして結果をキャッシュすることによって、いくつかの速度を追加することができます。

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

木がかなり小さい場合、あなたは一度だけのスレッドあたり、全部が先行キャッシュ可能性があります。それはあなたがやっているよりも多くのRAMを必要としますが、結果が何であるか気にするたびに、深さ優先のトラバーサルを行うよりもはるかに高速です。多くは、使用パターンと保存しているデータの量によって異なります。

キャッシュを使用する場合は、タイムアウトと「最終的には正しい」型保証のどちらかで、基になるデータの変更に対処する方法があることを確認するか、キャッシュを消去する必要がある場合、キャッシュの要素に依存します。