python - 可以更有效地编写此递归吗？

Question

我有一个分层组织，它是一棵树，如果 parent 赞助 child ，节点就是 child 。看来我可以用这段代码遍历树

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

但有没有一种更有效的方法，因为我必须为单个请求多次执行此操作，而且太多的递归可能效率低下？或者代码是否可以正确遍历树？在我的第一个版本中，我使用了三个变量，我发现我可以将代码重新排列为只有两个变量而不是这个:

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 变量并不是真正需要的，所以我删除了它。我这样做的方法是首先使用一个变量太多:

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，但比每次你关心结果是什么时进行深度优先遍历要快得多。很大程度上取决于您的使用模式和您存储的数据量。

如果你使用缓存，你必须确保你有一些方法来处理底层数据的变化，或者超时和“最终正确”的类型保证，或者跟踪你必须何时以及如何删除缓存，或者缓存的元素。