이 재귀가보다 효율적으로 작성 될 수 있습니까?

Question

부모가 자녀를 후원하는 경우 노드가 자식 인 트리 인 계층 적 조직이 있습니다.이 코드로 트리를 탐색 할 수있는 것 같습니다

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

그러나 단일 요청에 대해 여러 번 수행해야하며 많은 재귀가 비효율적 일 수 있으므로보다 효율적인 방법이 있습니다.또는 그 코드가 나무를 올바르게 횡단할 수 있기 때문에 코드가 잘 될 것인가?첫 번째 버전에서는 3 개의 변수를 사용했으며 코드를 두 가지 변수로 재정렬 할 수 있습니다.

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

Yes, there is a more efficient way to do it, depending on your computational tradeoffs.

You are currently doing a depth-first traversal of your tree, a perfectly fine approach. You could add some speed by caching results at the expense of some RAM usage, so:

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

If the tree is fairly small, you could just cache the whole thing upfront, once per thread. That takes more RAM than what you're doing, but is much faster than doing a depth-first traversal every time you care what the results are. A lot depends on your usage patterns and the amount of data you're storing.

If you use a cache, you must make sure you have some way to deal with the underlying data changing, either with timeouts and 'eventually correct' type guarantees, or keeping track of when and how you must wipe the cache, or elements of the cache.