How do you iterate over a tree ?

Question

Hello,

What is you preferred method of traversing a tree data structure, since recursive method calls can be pretty inefficient in some circumstances, I am simply using a generator like the one above. Do you have any hints to make it faster ?

def children(self):
    stack = [self.entities]
    while stack: 
        for e in stack.pop():
            yield e
            if e.entities:
                stack.append(e.entities)

here is some test data: first one is recursive, second uses the generator

s = time.time()
for i in range(100000):
    e.inc_counter()
print time.time() - s

s = time.time()
for i in range(100000):
    for e in e.children():
        e.inc_counter_s()
print time.time() - s

results:

0.416000127792

0.298999786377

test code:

import random

class Entity():
    def __init__(self, name):
        self.entities = []
        self.name = name
        self.counter = 1
        self.depth = 0

    def add_entity(self, e):
        e.depth = self.depth + 1
        self.entities.append(e)

    def inc_counter_r(self):
        for e in self.entities:
            e.counter += 1
            e.inc_counter_r()

    def children(self):
        stack = [self.entities]
        while stack:
            for e in stack.pop():
                yield e
                if e.entities:
                    stack.append(e.entities)

root = Entity("main")
def fill_node(root, max_depth):
    if root.depth <= max_depth:
        for i in range(random.randint(10, 15)):
            e = Entity("node_%s_%s" % (root.depth, i))
            root.add_entity(e)
            fill_node(e, max_depth)
fill_node(root, 3)

import time
s = time.time()
for i in range(100):
    root.inc_counter_r()
print "recursive:", time.time() - s

s = time.time()
for i in range(100):
    for e in root.children():
        e.counter += 1
print "generator:",  time.time() - s

Answer 1

Unless your tree is really large or you have really high (real) requirements for speed, I would choose the recursive method. Easier to read, easier to code.

Answer 2

If you have a lot of RAM and the tree doesn't change often, you can cache the result of the call:

def children(self):
    if self._children_cache is not None:
        return self._children_cache
    # Put your code into collectChildren()
    self._children_cache = self.collectChildren()
    return self._children_cache

Whenever the tree changes, set the cache to None. In this case, using recursive calls might be more effective since the results will accumulate faster.

Answer 3

I'm not sure if you can reduce the overhead much on a full in-order traversal of a tree, if you use recursion the call stack will grow some, otherwise you must manually use a stack to push references of the children while visiting each node. Which way is fastest and uses less memory, depends on the expensiveness of the call stack vs. a normal stack. (I would guess the callstack is faster since it should be optimized for its use, and recursion is much easier to implement)

If you don't care about the order you visit the nodes, some implementations of trees is actually stored in a dynamic array or linked list or stack wich you can traverse linearly if you don't care about the order it's traversed.

But why is it important to have a fast traversal anyway? Trees are good for searching, arrays/linked lists is good for full traversal. If you often need full in-order traversal but few searches and insertions/deletions, an ordered linked list might be best, if searching is what you do most you use a tree. If the data is really massive, so that memory overhead may render recursion impossible, you should use a database.

Answer 4

I've written iterative tree-traversal code in the past: it's very ugly, and not fast, unless you know exactly how many children not only each subtree will have, but how many levels there are.

Answer 5

I don't know too much about Python internals of function calls, but I really can't imagine that your code snippet is faster than recursively traversing the tree.

The call stack (used for function calls, including recursive ones) is typically very fast. Going to the next object will only cost you a single function call. But in your snippet - where you use a stack object, going to the next object will cost you a stack.append (possibly allocating memory on heap), a stack.push (possibly freeing memory from heap), and a yield.

The main problem with recursive calls is that you might blow the stack if your tree gets too deep. This isn't likely to happen.

Answer 6

Recursive function calls are not incredibly inefficient, that is an old programming myth. (If they're badly implemented, they may incur a larger overhead than necessary, but calling them "incredibly inefficient" is plain wrong.)

Remember: don't optimize prematurely, and never optimize without benchmarking first.

Answer 7

I can't think of any big algorithmic improvements, but a simple microoptimisation you can make is to bind frequently called methods (such as stack.append / stack.pop) to locals (this saves a dictionary lookup)

def children(self):
    stack = [self.entities]
    push = stack.append
    pop = stack.pop
    while stack: 
        for e in pop():
            yield e
            if e.entities:
                push(e.entities)

This gives a small (~15%) speedup by my tests (using 100 traversals of an 8-deep tree with 4 children at each node gives me the below timings:)

children     :  5.53942348004
children_bind:  4.77636131253

Not huge, but worth doing if speed is important.

Answer 8

Here's a pair of small corrections.

def children(self):
    stack = [self.entities]
    for e in stack:
        yield e
        if e.entities:
            stack.extend(e.entities)

I actually think the generator, using append, isn't visiting all the nodes. I think you mean to extend the stack with all entities, not append a simple list of entities to the stack.

Also, when the for loop terminates, the while loop in your original example will also terminate because there's no change to the empty stack after the for loop.