PEP 255: Simple Generators

David Eppstein eppstein at
Fri Jun 29 12:16:15 EDT 2001

In article <8hgojtgi94l6ldiafvi06mhfd7cnlo1fbp at>,
 Toby Dickenson <tdickenson at> wrote:

> David Eppstein <eppstein at> wrote:
> >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?
> 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

It is not always possible to completely optimize away the overhead of doing 
this loop.  Proof (probably unconvincing to anyone but a theoretician): one 
could use simple generators to implement a union-find data structure 
(probably not the right way of actually implementing UF, but...)

class disjointSet:
        self.parent = None
        self.generator = self.generate()

        while not self.parent:
            yield self
        for x in self.parent.generator:
            yield x


        if self.parent: raise ArgumentException
        self.parent = parent

But there are known superlinear lower bounds on union-find.
Note, this code assumes that it's ok to call next() on gen X at the same 
time as some other gen Y is suspended inside a for loop that's also looking 
at the elements of gen X; I don't see any reason why that shouldn't be 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at

More information about the Python-list mailing list