Tree Traversals, recursion is faster than iteration in python?

Question

I have implement tree preorder traversal in python, but found that my recursive version is faster than iteration version.

code is as below:

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()

results:

0.751042842865
1.0220580101

It means recursive version is about 25% faster. I search a lot, everybody says recursive should be slower, I just wonder why it is not the case in my code?

You are comparing a binary lookup vs. a complete scan. Not recursive vs. looping. — RickyA
– RickyA, Commented Feb 28, 2017 at 10:22
Your iterative algorithm contains some inefficiencies and furthermore it depends a lot on some factors whether recursion/iteration is faster. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 28, 2017 at 10:25
Your iterative version has redundant conditional check. See a more refined version in this gist However, I am also confused here, as the refined version is also somewhat slower. What would cause the recursive version to be faster? Is it the method calls like pop or append? The output of both traversals are same, so it is not the order of traversal that's causing the difference in performance. — Selçuk Cihan
– Selçuk Cihan, Commented Feb 28, 2017 at 12:07

Ivan Chaer · Accepted Answer · 2017-02-28 18:35:49Z

I believe you can simplify the iterator function and reduce the timing by eliminating one of the variables. Also, deque performs better than a set or a list in those kinds of cases.

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)

The benchmarks:

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))

Prints:

preorder:   0.0256490707397
preorder2:  0.0419111251831
preorder3:  0.0269520282745

Thank you for your answer. I run your code, preorder3 is slightly better than the recursive version. But I found that eliminating the additional variable in preorder2 has little effect on performance, the key point is using deque instead of list.

Collectives™ on Stack Overflow

Tree Traversals, recursion is faster than iteration in python?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related