为什么使用Python生成器遍历二叉树比不使用慢得多？

Question

我有一个二叉树，树里的节点会处理一些数据。一开始，我用了一种标准的后序递归遍历方法。

def visit_rec(self, node, data):
    if node:
        self.visit_rec(node.left, data)
        self.visit_rec(node.right, data)

        node.do_stuff(data)

我想我可以通过使用生成器来改进这个方法，这样我就可以在其他地方也用同样的遍历方式，而不需要一直传递相同的数据。下面是这个实现的代码。

def visit_rec_gen(self, node):
    if node:
        for n in self.visit_rec_gen(node.left):
                yield n
        for n in self.visit_rec_gen(node.right):
                yield n

        yield node

for node in self.visit_rec_gen():
    node.do_stuff(data)

但是，这个新方法比之前的版本慢了很多（大约从50秒变成了17秒），而且用了更多的内存。我在生成器函数的实现上是不是犯了什么错误？我希望能用这个方法，但不想牺牲性能。

补充说明：我应该一开始就提到，这些结果是在PyPy 2.3.1下得到的，而不是标准的CPython。

Answer 1

生成方法的效率比较低，这是因为使用生成器的实际情况。不过，如果你使用基于回调的系统，你可以在保持生成器灵活性的同时，获得接近非生成器方法的效率。

# NOTE that this should be a method on Node, not Tree
def apply_to_children_and_self(self, func, *args, **kwargs):
    if self.left:
        self.left.apply_to_children_and_self(func, *args, **kwargs)
    if self.right:
        self.right.apply_to_children_and_self(func, *args, **kwargs)
    func(self, *args, **kwargs)

...

head.apply_to_children_and_self(Node.do_stuff, data)

Answer 2

如果你在使用python3.3，yield from 这个语句被优化得比普通的循环更快，目的是为了更高效地返回值：

def visit_rec_gen(self, node):
    if node:
        yield from self.visit_rec_gen(node.left)
        yield from self.visit_rec_gen(node.right)
        yield node

Answer 3

在PyPy中，函数调用的效率比生成器或迭代器要高得多。

在PyPy中，有很多东西的性能表现各不相同（比如，PyPy的itertools.islice()性能非常差）。

你通过测量性能来找出最快的方法，这样做是对的。

另外，PyPy有一些工具可以显示生成的代码，这样你就能更详细地了解“它是怎么做的”。当然，关于“为什么这样做”的问题，答案中也涉及到人类的因素，比如实现的方便程度或者开发者的习惯。