PEP 255: Simple Generators

[Tim Peters]

[Toby Dickenson]
> 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, this is Python:  we're not optimizing anything.  WYSIWYG!  Even the
possibility for "optimimizing" that is off limits here:  it crosses stack
frames, with all the difficulties that entails.

[David Eppstein]
> ... one could use simple generators to implement a union-find data
> structure (probably not the right way of actually implementing UF,
> but...)

Cute!  The code snippet wasn't quite Python, so I'll attach a working light
rewrite below.

> ...
> 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.

It's allowed.  What isn't allowed is for an *active* (non-suspended)
generator to reinvoke itself (whether directly or indirectly) while still
active; e.g.,

>>> def g():
...     i = me.next()
...     yield i
>>> me = g()
>>> me.next()
Traceback (most recent call last):
 ...
  File "<string>", line 2, in g
ValueError: generator already executing

Here's your union-find algorithm w/ a little test driver:

class disjointSet:
    def __init__(self, name):
        self.name = name
        self.parent = None
        self.generator = self.generate()

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

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

    def union(self, parent):
        if self.parent:
            raise ValueError("Sorry, I'm not a root!")
        self.parent = parent

    def __str__(self):
        return self.name

names = "ABCDEFGHIJKLM"
sets = [disjointSet(name) for name in names]
roots = sets[:]

from random import choice
while 1:
    for s in sets:
        print "%s->%s" % (s, s.find()),
    print
    if len(roots) > 1:
        s1 = choice(roots)
        roots.remove(s1)
        s2 = choice(roots)
        s1.union(s2)
        print "merged", s1, "into", s2
    else:
        break

Here's "typical" output:

A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
merged A into M
A->M B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
merged B into K
A->M B->K C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
merged I into J
A->M B->K C->C D->D E->E F->F G->G H->H I->J J->J K->K L->L M->M
merged C into G
A->M B->K C->G D->D E->E F->F G->G H->H I->J J->J K->K L->L M->M
merged G into J
A->M B->K C->J D->D E->E F->F G->J H->H I->J J->J K->K L->L M->M
merged J into M
A->M B->K C->M D->D E->E F->F G->M H->H I->M J->M K->K L->L M->M
merged K into H
A->M B->H C->M D->D E->E F->F G->M H->H I->M J->M K->H L->L M->M
merged D into F
A->M B->H C->M D->F E->E F->F G->M H->H I->M J->M K->H L->L M->M
merged H into M
A->M B->M C->M D->F E->E F->F G->M H->M I->M J->M K->M L->L M->M
merged E into L
A->M B->M C->M D->F E->L F->F G->M H->M I->M J->M K->M L->L M->M
merged M into L
A->L B->L C->L D->F E->L F->F G->L H->L I->L J->L K->L L->L M->L
merged F into L
A->L B->L C->L D->L E->L F->L G->L H->L I->L J->L K->L L->L M->L

It seems a very clever way to avoid chasing up to the root each time.