performance of recursive generator

[Steven Bethard]

aurora wrote:
> I love generator and I use it a lot. Lately I've been writing some  
> recursive generator to traverse tree structures. After taking closer 
> look  I have some concern on its performance.
> 
> Let's take the inorder traversal from  
> http://www.python.org/peps/pep-0255.html as an example.
> 
> def inorder(t):
>     if t:
>         for x in inorder(t.left):
>             yield x
>         yield t.label
>         for x in inorder(t.right):
>             yield x
> 
> Consider a 4 level deep tree that has only a right child:
> 
> 1
>  \
>   2
>    \
>     3
>      \
>       4
> 
> 
> Using the recursive generator, the flow would go like this:
> 
> main    gen1        gen2        gen3        gen4
> ----------------------------------------------------
> 
> inorder(1..4)
> 
>         yield 1
>         inorder(2..4)
>                     yield 2
>         yield 2
>                     inorder(3..4)
>                                 yield 3
>                     yield3
>         yield 3
>                                 inorder(4)
>                                             yield 4
>                                 yield 4
>                     yield 4
>         yield 4
> 
> 
> Note that there are 4 calls to inorder() and 10 yield. Indeed the  
> complexity of traversing this kind of tree would be O(n^2)!

You seem to be assuming that a yield statement and a function call are 
equivalent.  I'm not sure that's a valid assumption.

Anyway, here's some data to consider:

-------------------- test.py --------------------
def gen(n):
     if n:
         for i in gen(n/2):
             yield i
         yield n
         for i in gen(n/2):
         	yield i

def gen_wrapper(n):
     return list(gen(n))

def nongen(n, func):
	if n:
	    nongen(n/2, func)
	    func(n)
	    nongen(n/2, func)

def nongen_wrapper(n):
	result = []
	nongen(n, result.append)
	return result
-------------------------------------------------

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(100)"
1000 loops, best of 3: 395 usec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(100)"
1000 loops, best of 3: 216 usec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(1000)"
100 loops, best of 3: 3.58 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(1000)"
1000 loops, best of 3: 1.59 msec per loop

D:\steve>python -m timeit -s "import test" "test.gen_wrapper(10000)"
10 loops, best of 3: 70.5 msec per loop

D:\steve>python -m timeit -s "import test" "test.nongen_wrapper(10000)"
10 loops, best of 3: 26.6 msec per loop

The non-generator version is consistently faster, somewhere around twice 
as fast.

Of course, I'll still be writing generator-based solutions util I'm 
certain the recursion's the speed bottleneck in my application.

STeVe