Kent Johnson wrote: > John Fouhy wrote: > >>On 15/05/06, Kent Johnson <[EMAIL PROTECTED]> 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 > fib is the standard use-case for the memoize decorator: http://wiki.python.org/moin/PythonDecoratorLibrary#head-11870a08b0fa59a8622201abfac735ea47ffade5
HTH, Wolfram _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor