On 28 Feb 2009, at 20:54, Jacob Holm wrote:
Replying to myself here...
Jacob Holm wrote:
I think I can actually see a way to do it that should be fast enough, but I'd like to work out the details first. If it works it will be O(1) with low constants as long as you don't build trees, and similar to traversing a delegation chain in the worst case.
All this depends on getting it working using delegation chains first though, as most of the StopIteration and Exception handling would be the same.
I have now worked out the details, and it is indeed possible to get O(1) for simple cases and amortized O(logN) in general, all with fairly low constants.
I'm sorry if I'm missing something obvious, but there are two things I can't work out: * What you are measuring the time complexity of. * What N stands for. I suspect that N is the 'delegation depth': the number of yield-from that have to be gone through. I imagine that you are measuring the time it takes to get the next element in the generator. These are guesses - can you correct me?
I have implemented the tree structure as a python module and added a trampoline-based pure-python implementation of "yield-from" to try it out.
It seems that this version beats a normal "for v in it: yield v" when the delegation chains get around 90 generators deep.
Can you give an example? -- Arnaud