472,331 Members | 1,575 Online

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

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 1854
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
Stefaan Himpe wrote in news:2m********************@newsfe16.ams2 in
comp.lang.python:
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
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
On Sat, 02 Aug 2008 16:14:11 -0500, Rob Williscroft wrote:
Stefaan Himpe wrote in news:2m********************@newsfe16.ams2 in
comp.lang.python:
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.
I think you are completely misreading the results of the Timeit calls.
That's not correct: you're calling it one million times, not once.

You should apply a "sanity check" to results. At the interactive console,
call the undecorated fib(100) once. Does it take 35 seconds? If so, your
computer is terribly slow -- on mine, it returns instantly.

Note that in your email, you showed only half the output:
[quote]
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
[end quote]

You had two calls to Timer.repeat() methods, and you didn't show the
output. *They* call the Fibonacci functions once. When I do that, I get
output looking like this:
>>t1 = Timer('fib(s)', 'from __main__ import fib, s')
t1.repeat(number=1)
[7.9870223999023438e-05, 5.5074691772460938e-05, 5.4121017456054688e-05]

You then call the Timer.timeit() method, which calls the function one
million times by default. That's the output you show: notice that 35s
divided by one million is 3.5e-05s, around what I get using the repeat()
method. There's no mystery.

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.
You shouldn't give much credence to timing results from calling a
function once (unless the function does a *lot* of work). Your operating
system is doing all sorts of work in the background. It can easily
interrupt your process mid-calculation to do something else, and your
timing code will then include that. You'll then wrongly conclude that the
function is slower than it really is.

Also, keep in mind that time.clock() is likely to be significantly less
accurate if you are using Linux. The timeit module automatically choose
the best function to use (time.clock vs time.time) for you.
So the question is: whats going on with timeit.Timer ?
As far as I can see, nothing. I think you have misunderstood the results
you got.

--
Steven
Aug 3 '08 #5
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
>>>
Aug 3 '08 #6
Steven D'Aprano wrote in news:00**********************@news.astraweb.com in
comp.lang.python:
>So the question is: whats going on with timeit.Timer ?

As far as I can see, nothing. I think you have misunderstood the results
you got.
No, the answer is that is it repeats a million times. It might better be
called repeat_one_million_times().

Or put another way, myself and the OP misinterpreted what the call
t1.repeat( number = 1 ) did.

its a confusing API.

For the OP:

The call t1.timeit() is equivalent to t1.repeat( number = 1000000 ).

So it bennefits from memoization because the call *is* repeated, not
just called once like you intended.

Rob.
--
http://www.victim-prime.dsl.pipex.com/
Aug 3 '08 #7
On Sun, 03 Aug 2008 09:46:45 -0500, Rob Williscroft wrote:
Steven D'Aprano wrote in news:00**********************@news.astraweb.com
in comp.lang.python:
>>So the question is: whats going on with timeit.Timer ?

As far as I can see, nothing. I think you have misunderstood the
results you got.

No, the answer is that is it repeats a million times. It might better
be called repeat_one_million_times().
But that would be seriously broken if you call it like this:

Timer.repeat_one_million_times(5, 1000)

It doesn't repeat one million times. It repeats five times, of 1000 loops
each.

Or put another way, myself and the OP misinterpreted what the call
t1.repeat( number = 1 ) did.

its a confusing API.
There's certainly confusion happening. Perhaps reading the doc strings
might clear up some confusion? help(Timer.repeat) and help(Timer.timeit)
state very clearly that they default to one million iterations.

For the OP:

The call t1.timeit() is equivalent to t1.repeat( number = 1000000 ).
No it isn't. Try running the code and looking at the results it gives.

t1.repeat(number=10**6) returns a list of three numbers. The function is
called *three* million times in total.

t1.timeit() returns a single number.

In fact, t1.timeit() is equivalent to
t1.repeat(repeat=1, number=1000000), (apart from it being in a list).
That can be written more simply as: t1.repeat(1)
--
Steven
Aug 3 '08 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 2 by: 42zeros | last post by: I would like a function to be executed every x often. I was just wondering how to pass the following code correctly. my object t just doesn't know... 2 by: laurenq uantrell | last post by: I have been using the following function to test the speed of various functions, however, quite often the return value is zero. I'm hoping someone... 1 by: martinm69x | last post by: Hey all, I've been working on the code for a kernel timer which will report real time, CPU time, user time and kernel time on the operation of... 1 by: Dongsheng Ruan | last post by: Hi Does anybody know how to pass multiple arguments to the function tested in timeit.timer() in python? I googled and found how to pass one... 3 by: silverburgh.meryl | last post by: Hi, I have a function in my python like this: def callFunc(line, no): # some code And I want to do a performance test like this: for line in... 3 by: rah | last post by: what is code for fibonacci in memoization version and Dynamic programming 19 by: colin | last post by: Hi, Im trying to time some parts of my code using the Stopwatch class, but it is so slow, I tried the QueryPerformanceFrequency() but this seems... 7 by: cnb | last post by: This must be because of implementation right? Shouldn't reduce be faster since it iterates once over the list? doesnt sum first construct the list... 0 by: teenabhardwaj | last post by: How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of... 0 by: CD Tom | last post by: This only shows up in access runtime. When a user select a report from my report menu when they close the report they get a menu I've called Add-ins... 0 by: Naresh1 | last post by: What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge... 0 by: antdb | last post by: Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was... 0 by: Matthew3360 | last post by: Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ... 2 by: Matthew3360 | last post by: Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it... 0 by: AndyPSV | last post by: HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable... 0 by: Arjunsri | last post by: I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and... 0 by: WisdomUfot | last post by: It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific...