python - 你如何遍历一棵树？

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

我想不出任何重大的算法改进，但您可以进行一个简单的微优化，就是将经常调用的方法(例如 stack.append/stack.pop)绑定(bind)到本地(这样可以节省字典查找)

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

规模不大，但如果速度很重要，则值得一试。