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
> 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 -
On Thu, 11 Aug 2005 01:18:11 -0700, Matt Hammond
<[EMAIL PROTECTED]> wrote:
>
>> 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 i
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
"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 measurea
aurora wrote:
> 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)!
>
> 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 recur
> 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 inorder(
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):
