如何在树上进行迭代？

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

- Utku

---

无效？您是指效率低下吗？ - nickf

Answer 1

除非你的树非常大或者你对速度有着极高（真实的）要求，否则我会选择递归方法。它更易于阅读，编码也更容易。

- rebra

---

我正在遍历一个3D应用程序的场景图，因此速度是一个问题，但这种类型的生成器使得将代码放在不同类型的对象的一个地方变得更容易，当你需要过滤时，代码会变得混乱。 - M. Utku ALTINKAYA

Answer 2

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

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

- JesperE

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％（对每个节点有4个子节点的8层树进行100次遍历时，以下是时间记录）：

children     :  5.53942348004
children_bind:  4.77636131253

虽然规模不大，但如果速度很重要，这个任务还是值得做的。

- Brian

---

我必须承认，我的应用程序分析结果以前更加精确，可能是因为树形结构或调用的方法。但这也不是无关紧要的，而且缓存的能力可以导致非常有趣的优化。 - M. Utku ALTINKAYA

Answer 4

我不确定你能否在完整的树遍历中减少开销，如果使用递归，调用堆栈会增长一些，否则您必须手动使用堆栈来推送每个节点访问时的子节点引用。哪种方法更快，使用的内存更少，取决于调用堆栈与普通堆栈的昂贵程度。（我猜调用堆栈更快，因为它应该针对其使用进行了优化，并且递归更容易实现）

如果您不关心访问节点的顺序，则某些树的实现实际上存储在动态数组、链表或堆栈中，如果您不关心遍历的顺序，可以通过线性遍历来访问。

但是，为什么快速遍历很重要呢？树适用于搜索，数组/链表适用于完整遍历。如果您经常需要完整的顺序遍历，但只有少量的搜索和插入/删除操作，则有序链表可能是最佳选择；如果搜索是您最常使用的操作，则使用树。如果数据非常庞大，以至于内存开销可能使递归变得不可能，则应使用数据库。

- Stein Gauslaa Strindhaug

Answer 5

如果您拥有大量的RAM，并且树不经常更改，您可以缓存调用的结果：

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

每当树结构发生变化时，将缓存设置为None。在这种情况下，使用递归调用可能更有效，因为结果会更快地累积。

- Aaron Digulla

---

这是一个好主意，同时生成器可以更改为使用缓存。如果 e 有 children_cache，则应该遍历节点而不是将其推入堆栈中。 :) - M. Utku ALTINKAYA

Answer 6

我以前写过迭代树遍历代码：它非常丑陋，而且不快，除非你知道每个子树不仅有多少个孩子，还知道有多少层。

- warren

Answer 7

我对Python函数调用的内部机制不是很了解，但我真的无法想象你的代码片段比递归遍历树更快。

调用堆栈（用于函数调用，包括递归调用）通常非常快。转到下一个对象只会花费一个函数调用。但在你的代码片段中 - 当你使用一个堆栈对象时，转到下一个对象将会花费你一个stack.append（可能在堆上分配内存），一个stack.push（可能从堆上释放内存），和一个yield。

递归调用的主要问题是，如果你的树太深，你可能会炸掉堆栈。这不太可能发生。

- cadabra

---

我已经发布了一些简单的测试数据。 - M. Utku ALTINKAYA

函数调用实际上是非常昂贵的。每次调用都必须分配一个帧对象（也在堆上），填充参数，然后调用它。将这样做N次用于N个子项与单个追加N个项目进行比较，您将看到为什么堆栈方法更快。 - Brian

生成器的速度比函数调用要快得多，因为它们不会创建新的帧 - 现有的帧对象被重复使用。 - Brian

Answer 8

这里有一对小修正。

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

我认为生成器使用append方法时，并没有访问所有节点。我想你的意思是用extend方法将所有实体添加到堆栈中，而不是将简单的实体列表附加到堆栈上。

此外，在for循环终止时，原始示例中的while循环也将终止，因为在for循环之后对空堆栈没有任何更改。

- S.Lott

---

我使用了一个列表的列表来防止更新正在迭代的列表对象，我认为这样做是未定义的？ - M. Utku ALTINKAYA

你可能在想Java，改变结构会引起迭代器混乱。 - S.Lott

好的，我已经测试过了，它可以工作，但是似乎有点慢，我想可能是因为扩展的原因。递归：1.96200013161 生成器：1.68400001526 新生成器：1.74000000954 - M. Utku ALTINKAYA

此时，似乎您应该关闭此问题，并使用已更正的算法和当前时间重新开始。这些时间更符合我的预期 - 差异相对较小。 - S.Lott

我不确定这很有用，因为你最初的代码示例（使用append）和你最初的时间（基于append）实际上是错误的。那个算法实际上并不正确地工作。我认为发布这样一个错误的算法会让人困惑，可能是一种糟糕的策略。 - S.Lott