你如何迭代树？

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

递归函数调用并不是极其低效，这是一个古老的编程神话。（如果它们实施得不好，它们可能会产生比必要的更大的开销，但称它们“效率极低”是完全错误的。）

请记住：不要过早优化，也不要在没有首先进行基准测试的情况下进行优化。

Answer 3

我想不出任何大的算法改进,但是你可以做的一个简单的微优化是将经常调用的方法(例如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

不是很大,但如果速度很重要,那就值得做.