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

[ssecorp]

I am not clear about the results here.


from timeit import Timer
import Decorators

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')
t1.repeat(number=1)
t2.repeat(number=1)
print t1.timeit()
print t2.timeit()


>>>
35.3092010297
1.6516613145
>>>


So memoization is 20+ times faster than the idiomatic way?
Or am I missing something here?


Ok for fun I added memoization to the idiomatic one:

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')
t1.repeat(number=1)
t2.repeat(number=1)
print t1.timeit()
print t2.timeit()


didn't think it would make a difference there but it certainly did.


>>>
1.59592657726
1.60179436213
>>> ================================ RESTART ================================
>>>
2.66468922726
3.0870236301
>>> ================================ RESTART ================================
>>>
1.62921684181
1.51585159566
>>> ================================ RESTART ================================
>>>
1.49457319296
1.60948472501
>>> ================================ RESTART ================================
>>>
1.48718203012
1.6645559701
>>>