PEP 255: Simple Generators

[Tim Peters]

[David Eppstein]
> So, back to the topic of PEP255: am I the only one bothered by the fact
> that the inorder example in the PEP is quadratic time,

Well, sum of the path lengths, and "quadratic time" is a worst case.  If
someone has a binary tree that's degenerated into a linear list, they've
likely got worse problems than the time it takes to enumerate the leaves.

> and that it seems difficult to use simple generators to yield a
> tree's nodes in inorder in linear time?

I'm not bothered -- this comes with the territory.  If/when full-fledged
coroutines make it in too, people worried about that can use them instead.
Curious fact:  I *was* worried about the worst-case time aspects of "simple
generators" in Icon years ago, but in practice never ever got burned by it.
And rewriting stuff to use Icon co-expressions instead invariably resulted
in messier code that ran significantly slower in virtually all cases, except
for the ones I *contrived* to prove the O() difference.

BTW, Python almost never worries about worst-case behavior, and people using
Python dicts instead of, e.g., balanced trees, get to carry their shame home
with them hours earlier each day <wink>.

"simple"-means-"simple"-ly y'rs  - tim