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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4