ツリートラバーサル、再帰は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

私は、イテレータの機能を単純化し、変数の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