464,828 Members | 1,068 Online Need help? Post your question and get tips & solutions from a community of 464,828 IT Pros & Developers. It's quick & easy.

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

 P: n/a 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 >>> Aug 2 '08 #1
7 Replies

 P: n/a Nothing weird about this ... The difference will become larger as your input value becomes larger. You can easily understand why if you try to calculate fib(10) by hand, i.e. work through the algorithm with pencil and paper, then compare the work you have to do to the memoized version which just takes fib(9) and fib(8) from memory and adds them together. Best regards, Stefaan. Aug 2 '08 #2

 P: n/a Stefaan Himpe wrote in news:2m********************@newsfe16.ams2 in comp.lang.python: Nothing weird about this ... The difference will become larger as your input value becomes larger. You can easily understand why if you try to calculate fib(10) by hand, i.e. work through the algorithm with pencil and paper, then compare the work you have to do to the memoized version which just takes fib(9) and fib(8) from memory and adds them together. I think you missed the point. The problem is that the un-decorated, loop only version takes 35 seconds when called by timeit.Timer. However if you apply the decorator it takes less that a second. In *both* cases the function (fib) only gets called once. Note, I timed the call fib(100) with time.clock() and got a value of less than 1 ms, the memozed version takes about 10 times longer. So the question is: whats going on with timeit.Timer ? Rob. -- http://www.victim-prime.dsl.pipex.com/ Aug 2 '08 #3

 P: n/a On Sat, 02 Aug 2008 06:02:02 -0700, ssecorp wrote: 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 [...] 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? Memoization *can be* faster, not *is* -- memoization requires work, and if it is more work to look something up than to calculate it, then it will be a pessimation instead of an optimization. That's probably less of an issue with high-level languages like Python, but in low level languages you would need to start thinking about processor caches and all sorts of complications. But I digress... in Python, yes, I would expect a significant speedup with memoization. That's why people use it. Ok for fun I added memoization to the idiomatic one: [...] didn't think it would make a difference there but it certainly did. 1.59592657726 1.60179436213 Just curious, but why don't you show the results of the call to repeat()? It makes me uncomfortable to see somebody showing only half their output. But yes, with memoization, the lookup to find the Fibonacci number should decrease the time it takes to calculate the Fibonacci number. I'm not sure why you are surprised. Regardless of which Fibonacci algorithm you are using, the Timer object is essentially timing one million lookups, minus 100 calculations of the Fibonacci number. The 999,900 cache lookups will dominate the time, far outweighing the 100 calculations, regardless of which method of calculation you choose. That's why the results are almost identical. -- Steven Aug 3 '08 #4 