PEP 255: Simple Generators

[Toby Dickenson]

David Eppstein <eppstein at ics.uci.edu> wrote:

>In article <mailman.993373609.20265.python-list at python.org>,
> "Tim Peters" <tim.one at home.com> wrote:
>
>> Tail-recursion is pretty much insane for that in Python, as
>> processing list[0] then recursing on list[1:] turns a speedy task into a
>> quadratic-time mess.
>
>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, and that it seems 
>difficult to use simple generators to yield a tree's nodes in inorder in 
>linear time?

As implemented today, yes it is quadratic.

If that quadratic term is actually dominant for sensibly deep trees,
then I suspect it would not be too hard to optimise away this very
common case at C level:

    for x in <generator>:
        yield x


Toby Dickenson
tdickenson at geminidataloggers.com