[Python-Dev] python generator design bug?

[Tim Peters]

[Neil Schemenauer]
> Eric Kidd thinks so:
>
>     http://www.advogato.org/person/emk/
>
> Here's an excerpt:
>
>     [...] there's a subtle bug in the Python design. Consider tree
>     traversal:
>
>     def inorder(t):
>         if (t.left != None):
>             for (node in inorder(t.left)):
>                 yield node
>         yield t
>         if (t.right != None):
>             for (node in inorder(t.right)):
>                 yield node
>
>     If you study this carefully, you'll see that (unless the optimizer
>     intervenes), Python has turned a perfectly good O(N) tree traversal
>     into an O(N log N) traversal.
>
> Thoughts?

Replied to this before on c.l.py (but to David Eppstein):

    http://aspn.activestate.com/ASPN/Mail/Message/624273

enumerate-a-btree-and-"log(n)"-is-1-ly y'rs  - tim