Может ли эта рекурсия быть написана более эффективно? - PullRequest
Новая
       21

Может ли эта рекурсия быть написана более эффективно?

2 голосов
/ 10 марта 2012

У меня есть иерархическая организация, которая представляет собой дерево, в котором узел является дочерним, если родитель спонсирует дочернего.Кажется, я могу пройти по дереву с помощью этого кода 

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

1 Ответ

1 голос
/ 13 марта 2012

Да, есть более эффективный способ сделать это, в зависимости от ваших вычислительных компромиссов.

В настоящее время вы выполняете обход вашего дерева в глубину, что является идеальным подходом.Вы можете добавить некоторую скорость, кэшируя результаты за счет некоторого использования ОЗУ, поэтому: 

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

Если дерево довольно маленькое, вы можете просто кешировать все заранее, один раз на поток.Это требует больше оперативной памяти, чем то, что вы делаете, но намного быстрее, чем обход в глубину каждый раз, когда вам важно, каковы результаты.Многое зависит от ваших моделей использования и объема хранимых данных.

Если вы используете кеш, вы должны убедиться, что у вас есть какой-то способ справиться с изменением базовых данных, либо с таймаутами, либо с 'в конечном итоге правильный 'тип гарантии или отслеживание того, когда и как вы должны очистить кеш или элементы кеша.

...