Is it an inherent issue in the use of recursive generator? Is there any
compiler optimization possible?
Hi, I could be misunderstanding it myself, but I think the short answer to
your question is that its an inherent limitation.
def inorder(t):
if t:
for x in
aurora wrote:
generator example
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)!
recursive function
There will be 4 calls to inorder() and 4 call to foo(), give a
reasonable O(n) performance.
Is it an
aurora [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]
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.
When the stacked yields become a measureable
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
You seem to be assuming that a yield statement and a function call are
equivalent. I'm not sure that's a valid assumption.
I don't know. I was hoping the compiler can optimize away the chain of
yields.
Anyway, here's some data to consider:
test.py
aurora wrote:
This test somehow water down the n^2 issue. The problem is in the depth
of recursion, in this case it is only log(n). It is probably more
interesting to test:
def gen(n):
if n:
yield n
for i in gen(n-1):
yield i
You should be able to
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):