performance of recursive generator
Steven Bethard
steven.bethard at gmail.com
Thu Aug 11 22:01:54 CEST 2005
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
More information about the Python-list
mailing list