python - 为什么使用 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

在 PyPy 上，函数调用比生成器或迭代器更优化。

PyPy 中有很多东西具有不同的性能特征(例如，PyPy 的 itertools.islice() 执行得非常糟糕)。

您通过衡量性能来确定哪种方式最快是在做正确的事情。

另请注意，PyPy 具有显示生成的代码的工具，因此您可以更详细地回答“它是做什么的”这个问题。当然，“为什么这样做”的问题在答案中有人为因素，涉及实现起来方便或实现者的倾向。