python - 树遍历，递归比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%。 我搜索了很多，每个人都说递归应该更慢，我只是想知道为什么我的代码不是这样？

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