PEP 255: Simple Generators

[David Eppstein]

In article <8hgojtgi94l6ldiafvi06mhfd7cnlo1fbp at 4ax.com>,
 Toby Dickenson <tdickenson at devmail.geminidataloggers.co.uk> wrote:

> David Eppstein <eppstein at ics.uci.edu> 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:
    __init__(self):
        self.parent = None
        self.generator = self.generate()

    generate(self):
        while not self.parent:
            yield self
        for x in self.parent.generator:
            yield x

    find(self):
        return self.generator.next()

    union(self,parent):
        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 
allowed.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/