树的遍历，在Python中递归比迭代快吗？

Question

我已经在Python中实现了树的前序遍历，但发现我的递归版本比迭代版本更快。

代码如下：

from __future__ import print_function
import time

class Tree():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(string):
    nodes = [0] + [Tree(s) for s in string]
    for i in range(2, len(nodes)):
        p = i/2
        if i%2 == 0:
            nodes[p].left = nodes[i]
        else:
            nodes[p].right = nodes[i]
    return nodes[1]

def preorder(tree):
    if tree:
        #  print(tree.value,end='')
        preorder(tree.left)
        preorder(tree.right)

def preorder2(tree):
    t = tree
    s = []
    while t or s:
        while t:
            #  print(t.value,end='')
            s.append(t)
            t = t.left
        if s:
            t = s.pop()
            t = t.right

def main():
    tree = build_tree('abcdefghi'*1000)
    t = time.time()
    for _ in range(100):
        preorder(tree)
    print(time.time() - t)
    t = time.time()
    for _ in range(100):
        preorder2(tree)
    print(time.time() - t)


if __name__ == '__main__':
    main()

结果:

0.751042842865
1.0220580101

这意味着递归版本大约快25%。

我搜索了很多资料，每个人都说递归应该更慢，但我不明白为什么在我的代码中情况并非如此？

- Yuguang Chan

---

你正在比较二进制查找和完全扫描。不是递归与循环。 - RickyA

您的迭代算法存在一些低效性，而且它是否使用递归/迭代更快很大程度上取决于某些因素。 - Willem Van Onsem

你的迭代版本有冗余的条件检查。在这个gist中可以看到更精细的版本。然而，我在这里也感到困惑，因为更精细的版本也有点慢。是像pop或append这样的方法调用导致递归版本更快吗？两种遍历的输出都相同，所以不是遍历顺序导致性能差异。 - Selçuk Cihan

Answer 1

我相信您可以通过消除其中一个变量来简化迭代器函数并减少时间。此外，在这种情况下，deque 比 set 或 list 更有效率。

from collections import deque

def preorder3(initial_node):
    queue = deque([initial_node])
    while queue:
        node = queue.pop()
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

基准测试：

from __future__ import print_function
from timeit import timeit

class Tree():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_tree(string):
    nodes = [0] + [Tree(s) for s in string]
    for i in range(2, len(nodes)):
        p = i/2
        if i%2 == 0:
            nodes[p].left = nodes[i]
        else:
            nodes[p].right = nodes[i]
    return nodes[1]

def preorder(tree):
    if tree:
        preorder(tree.left)
        preorder(tree.right)

def preorder2(tree):
    t = tree
    s = []
    while t or s:
        while t:
            s.append(t)
            t = t.left
        if s:
            t = s.pop()
            t = t.right

from collections import deque

def preorder3(initial_node):
    queue = deque([initial_node])
    while queue:
        node = queue.pop()
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

tree = build_tree('abcdefghi'*100)

# Repetitions to time
number = 20

# Time it
print('preorder:  ', timeit('f(t)', 'from __main__ import preorder as f, tree as t', number=number))
print('preorder2: ', timeit('f(t)', 'from __main__ import preorder2 as f, tree as t', number=number))
print('preorder3: ', timeit('f(t)', 'from __main__ import preorder3 as f, tree as t', number=number))

输出：

preorder:   0.0256490707397
preorder2:  0.0419111251831
preorder3:  0.0269520282745

- Ivan Chaer

---

谢谢你的回答。我运行了你的代码，preorder3比递归版本稍微好一些。但是我发现，在preorder2中消除额外变量对性能影响不大，关键是使用deque而不是list。 - Yuguang Chan