performance of recursive generator
aurora
aurora00 at gmail.com
Thu Aug 11 06:06:22 CEST 2005
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)!
Compare that with a similar recursive function using callback instead of
generator.
def inorder(t, foo):
if t:
inorder(t.left, foo):
foo(t.label)
inorder(t.right, foo):
The flow would go like this:
main stack1 stack2 stack3 stack4
----------------------------------------------------
inorder(1..4)
foo(1)
inorder(2..4)
foo(2)
inorder(3..4)
foo(3)
inorder(4)
foo(4)
There will be 4 calls to inorder() and 4 call to foo(), give a reasonable
O(n) performance.
Is it an inherent issue in the use of recursive generator? Is there any
compiler optimization possible?
More information about the Python-list
mailing list