PEP 255: Simple Generators
David Eppstein
eppstein at ics.uci.edu
Fri Jun 29 12:16:15 EDT 2001
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/
More information about the Python-list
mailing list