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

然而,这比以前的版本(~50s到~17s)慢得多,并且使用了更多的内存.我的发电机功能版本有错吗？我更喜欢使用这种方法,但不是以牺牲性能为代价.

编辑:我最初应该提到的一点是,这些结果是在PyPy 2.3.1下获得的,而不是标准的CPython.

Answer 1

在PyPy上,函数调用比生成器或迭代器更加优化.

在PyPy中有许多具有不同性能特征的东西(例如,PyPy的itertools.islice()执行非常规).

你通过测量性能来做正确的事情,看看哪种方式最快.

另请注意,PyPy具有显示生成的代码的工具,因此您可以更详细地回答"它做什么"的问题.当然,"为什么这样做"的问题在答案中有一个人的组成部分,涉及方便实施或实施者的倾向.