Profiling weirdness: Timer.timeit(), fibonacci and memoization

ssecorp circularfunc at gmail.com
Sun Aug 3 14:02:17 CEST 2008


I think you are confusing 2 people in this thread but that doesn't
really matter.
What surprised me was that I didn't think fib would benefit from
memoization because it didn't repeat the same calculations. fibmem
without memoization is the classic naive implementation that grows
exponentially and obv that would benefit from memoization.


from timeit import Timer
import Decorators

@Decorators.memoize
def fib(n):
    a, b = 1, 0
    while n:
        a, b, n = b, a+b, n-1
    return b

@Decorators.memoize
def fibmem(nbr):
    if nbr > 1:
        return fibmem(nbr-1) + fibmem(nbr-2)
    if nbr == 1:
        return 1
    if nbr == 0:
        return 0

s = 100
t1 = Timer('fib(s)', 'from __main__ import fib, s')
t2 = Timer('fibmem(s)', 'from __main__ import fibmem, s')
print t1.repeat(number=1)
print t2.repeat(number=1)
print t1.timeit()
print t2.timeit()


>>>
[4.8888895097002557e-005, 3.6317464929201785e-006,
3.0730162632401604e-006]
[0.0014432001832635141, 5.5873022968000452e-006,
3.0730162632417596e-006]
1.4421612244
1.34121264015
>>>



More information about the Python-list mailing list