[Python-Dev] Re: Graph exploration with generators
David Eppstein
eppstein at ics.uci.edu
Wed Aug 20 09:13:24 EDT 2003
On 8/20/03 10:53 AM -0400 Kevin Jacobs <jacobs at penguin.theopalgroup.com>
wrote:
> 99% of the "problem" can be taken care of by adding a relatively simple
> optimization to the interpreter. It involves adding the necessary
> book-keeping to propogate values yielded by a generator directly to the
> next expression it is needed in, and conversely to return to the generator
> directly when the next value is requested. Say we have a depth-N tree,
> then for each leaf node, the interpreter must pass a value up to N-1
> levels of generators. If the values yielded are direct generator calls,
> then all N-1 of those yields can be elided. This allows "yield *" to be
> written efficiently as a simple C-function, that is equivalent to this
> Python generator:
>
> def yield_star(iterable):
> for i in iterable:
> yield i
>
> Interestingly enough, this same optimization can also be applied to return
> expressions/values, and is related to tail-call optimizations done by
> traditional compilers and functional-language interpreters. It is also
> very much related to continuation-passing-style (CPS) transformations,
> which for Python generators, have very tractable semantics.
If you are implying (when you say "all N-1 of those yields can be elided"
that recursive chains of "yield *" can be handled in such a way that each
generated item is passed through the whole chain in constant time, then you
are mistaken.
I can prove a nonconstant lower bound via a simulation of union-find, and
the best amortized upper bound I know is logarithmic. Ewing's technique,
that I referred to in a previous message, should do better in practice but
not in the worst case.
The problem is that, if a generator X calls "yield *" on a generator Y, we
can not safely assume that all of Y's output goes to X. X can be suspended
and in the meantime someone else can request values from Y.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
More information about the Python-Dev
mailing list