Как вы перебираете дерево?

Question

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

def children(self):
    stack = [self.entities]
    while stack: 
        for e in stack.pop():
            yield e
            if e.entities:
                stack.append(e.entities) 

Вот некоторые тестовые данные. Первый рекурсивный, второй использует генератор:

s = time.time()
for i in range(100000):
    e.inc_counter()
print time.time() - s

s = time.time()
for i in range(100000):
    for e in e.children():
        e.inc_counter_s()
print time.time() - s

Результаты:

0.416000127792
0.298999786377

Тестовый код:

import random

class Entity():
    def __init__(self, name):
        self.entities = []
        self.name = name
        self.counter = 1
        self.depth = 0

    def add_entity(self, e):
        e.depth = self.depth + 1
        self.entities.append(e)

    def inc_counter_r(self):
        for e in self.entities:
            e.counter += 1
            e.inc_counter_r()

    def children(self):
        stack = [self.entities]
        while stack:
            for e in stack.pop():
                yield e
                if e.entities:
                    stack.append(e.entities)

root = Entity("main")
def fill_node(root, max_depth):
    if root.depth <= max_depth:
        for i in range(random.randint(10, 15)):
            e = Entity("node_%s_%s" % (root.depth, i))
            root.add_entity(e)
            fill_node(e, max_depth)
fill_node(root, 3)

import time
s = time.time()
for i in range(100):
    root.inc_counter_r()
print "recursive:", time.time() - s

s = time.time()
for i in range(100):
    for e in root.children():
        e.counter += 1
print "generator:",  time.time() - s

Answer 1

Если ваше дерево не очень большое или у вас очень высокие (реальные) требования к скорости, я бы выбрал рекурсивный метод. Легче читать, легче кодировать.

Answer 2

Я не могу придумать каких-либо больших алгоритмических улучшений, но простая микрооптимизация, которую вы можете сделать, это связать часто вызываемые методы (такие как stack.append / stack.pop) с местными жителями (это сохраняет поиск в словаре)

def children(self):
    stack = [self.entities]
    push = stack.append
    pop = stack.pop
    while stack: 
        for e in pop():
            yield e
            if e.entities:
                push(e.entities)

Это дает небольшое (~ 15%) ускорение по моим тестам (использование 100 обходов дерева глубиной 8 с 4 дочерними узлами в каждом узле дает мне следующие значения времени:)

children     :  5.53942348004
children_bind:  4.77636131253

Не огромно, но стоит делать, если важна скорость.

Answer 3

Рекурсивные вызовы функций не являются невероятно неэффективными, это старый миф программирования. (Если они плохо реализованы, они могут повлечь за собой большие издержки, чем это необходимо, но называть их «невероятно неэффективными» совершенно неправильно.)

Помните: не оптимизируйте преждевременно, а никогда оптимизируйте без предварительного тестирования.

Answer 4

Я не уверен, что вы можете значительно уменьшить накладные расходы при полном обходе дерева по порядку, если вы используете рекурсию, стек вызовов вырастет, иначе вы должны будете вручную использовать стек толкать ссылки детей при посещении каждого узла. Какой из способов быстрее и использует меньше памяти, зависит от дороговизны стека вызовов по сравнению с обычным стеком. (Я полагаю, что стек вызовов работает быстрее, поскольку он должен быть оптимизирован для его использования, а рекурсия гораздо проще реализовать)

Если вас не волнует порядок посещения узлов, некоторые реализации деревьев на самом деле хранятся в динамическом массиве или связанном списке или стеке, которые вы можете перемещать линейно, если вам не важен порядок, через который они проходят.

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

Answer 5

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

def children(self):
    if self._children_cache is not None:
        return self._children_cache
    # Put your code into collectChildren()
    self._children_cache = self.collectChildren()
    return self._children_cache

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

Answer 6

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

Answer 7

Вот пара небольших исправлений.

def children(self):
    stack = [self.entities]
    for e in stack:
        yield e
        if e.entities:
            stack.extend(e.entities)

Я действительно думаю, что генератор, использующий append, не посещает все узлы. Я думаю, что вы имеете в виду extend стек со всеми сущностями, а не append простой список сущностей в стеке.

Кроме того, когда цикл for завершается, цикл while в исходном примере также завершается, поскольку после цикла for нет изменений в пустом стеке.

Answer 8

Я не слишком много знаю о внутренностях Python для вызовов функций, но я действительно не могу представить, что ваш фрагмент кода быстрее, чем рекурсивный обход дерева.

Стек вызовов (используется для вызовов функций, в том числе рекурсивных), как правило, очень быстрый. Переход к следующему объекту обойдется вам всего в один вызов функции. Но в вашем фрагменте - когда вы используете объект стека, переход к следующему объекту будет стоить вам stack.append (возможно, выделение памяти в куче), stack.push (возможно, освобождение памяти из кучи) и выход. *

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