[Python-ideas] Revised**5 PEP on yield-from
Arnaud Delobelle
arnodel at googlemail.com
Sun Mar 1 11:34:59 CET 2009
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
More information about the Python-ideas
mailing list