[Tutor] Nested list comprehensions

[Kent Johnson]

John Fouhy wrote:
> On 15/05/06, Kent Johnson <kent37 at tds.net> wrote:
>> You can come pretty close with generators, though it hurts to think
>> about what is actually going on behind the scenes here:
>>
>> In [1]: import itertools
>>
>> In [2]: def fibs():
>>     ...:     yield 0
>>     ...:     yield 1
>>     ...:     fib1 = fibs()
>>     ...:     fib2 = fibs()
>>     ...:     fib2.next()
>>     ...:     for a, b in itertools.izip(fib1, fib2):
>>     ...:         yield a+b
> 
> Yikes!
> 
> f = fibs()
> for i in range(100):
>     start = time.clock()
>     x = f.next()
>     dur = time.clock() - start
>     print i, x, dur
>     if dur > 10:
>         break
> 
> 0 0 2.03936533833e-005
> 1 1 5.5873022968e-006
> 2 1 1.59238115459e-005
> 3 2 1.25714301678e-005
> 4 3 1.95555580388e-005
> 5 5 2.15111138427e-005
> 6 8 2.93333370582e-005
> 7 13 6.06222299203e-005
> 8 21 7.87809623849e-005
> 9 34 0.000119568269152
> 10 55 0.000383568302675
> 11 89 0.000409269893241
> 12 144 0.000650082622233
> 13 233 0.000979454092629
> 14 377 0.00172200656787
> 15 610 0.00713330884232
> 16 987 0.00450979104886
> 17 1597 0.0128720270314
> 18 2584 0.0150373860365
> 19 4181 0.0283779083654
> 20 6765 0.0490199173359
> 21 10946 0.135228918759
> 22 17711 0.240615497221
> 23 28657 0.365666586116
> 24 46368 0.827867508301
> 25 75025 2.14721368219
> 26 121393 4.08266218193
> 27 196418 20.1769099145
> 
> Hmm, do you know an easy way to check how much memory python is using?
>  My HDD was swapping like crazy by the end of that..

Does the Haskell version do any better? ISTM this formulation is 
fundamentally inefficient; calculating fib(n) is going to create 
something like fib(n-1) fib objects. In the Python case each fib is a 
generator which I imagine means it has some kind of stack frame 
associated with it.

Kent