[Python-ideas] Revised**5 PEP on yield-from

[Arnaud Delobelle]

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