樹遍歷，遞歸比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