2

親が子を後援している場合、ノードが子であるツリーである階層組織があります。このコードでツリーをトラバースできるようです

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

上記を使用して、私はユーザーの組織を取得することができます

downline=user.get_team(user, [])

しかし、1つのリクエストに対してこれを何度も実行する必要があり、その多くの再帰は非効率的である可能性があるため、より効率的な方法はありますか？または、ツリーを正しくトラバースできるため、コードは問題ありませんか？私の最初のバージョンでは、3つの変数を使用しましたが、コードを次の代わりに2つの変数に再配置できることがわかりました。

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

teamlist変数は実際には必要ないことがわかったので、削除しました。私がそれをした方法は、最初は1つの変数が多すぎたというものでした。

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

4

1 に答える 1

1

はい、計算上のトレードオフに応じて、より効率的な方法があります。

現在、ツリーの深さ優先走査を実行しています。これは完全に優れたアプローチです。RAMの使用量をいくらか犠牲にして結果をキャッシュすることで、速度を上げることができます。

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

ツリーがかなり小さい場合は、スレッドごとに1回、すべてを事前にキャッシュすることができます。これは、実行しているものよりも多くのRAMを必要としますが、結果がどうなるかを気にするたびに深さ優先探索を実行するよりもはるかに高速です。多くはあなたの使用パターンとあなたが保存しているデータの量に依存します。

キャッシュを使用する場合は、タイムアウトと「最終的に正しい」タイプの保証を使用するか、キャッシュまたはキャッシュの要素をいつどのようにワイプする必要があるかを追跡することで、基になるデータの変更に対処する方法があることを確認する必要があります。キャッシュ。

于 2012-03-13T17:35:20.980 に答える