Fun with Fibonacci
Just read an interesting blog post about comparing Python and Haskell code to calculate the Fibonacci sequence. I wrote a faster version, just for the hell of it. I realise that it is not a fair comparison any more, and doesn’t prove anything, but it does demonstrate a useful optimization technique. Here’s the code…
from time import time def memoize(f): f._cache = {} def do_f(n): if n in f._cache: return f._cache[n] r = f(n) f._cache[n] = r return r return do_f @memoize def fib(n): if n == 0 or n == 1: return n else: return fib(n-1) + fib(n-2) if __name__ == "__main__": start_time = time() for i in range(36): print "n=%d => %d" % (i, fib(i)) print "Time elapsed: %f" % (time() - start_time)
When I run it on my machine, it claims to take 0.00000 seconds. Damn, thats fast!
December 12th, 2007 at 2:22 pm
Memoization is indeed a good (time) optimisation technique. It might be worth pointing out that you’ve sacrificed memory for time by doing it though.
Nice use of Python decorators!
December 12th, 2007 at 3:16 pm
Nice, but the point was in measuring the speed of languages, without changing the naive algorithm…
December 12th, 2007 at 7:29 pm
@filox : If you use the naive algorithm, you’re going to see languages win that are written naively. If you want a _real_ language comparison, I think you need to use the best way to do it in either language.
December 12th, 2007 at 8:00 pm
You must be using some form of Windows OS. Python time.time() resolution on Windows XP is around 15 milliseconds. So you have shown that your algorithm runs in less than about 15 ms on your machine. Try it again using time.clock(). Python time.clock() on my Windows XP box has about 2 microsecond resolution.
December 12th, 2007 at 8:06 pm
I just took my own advice that I just gave you. I ran on WIndows XP with time.time() and I also got 0 seconds. When I ran using time.clock() I got about 3 milliseconds.
December 12th, 2007 at 10:00 pm
should be even faster with xrange instead of range (unless you’re using python3000). of course, you probably won’t be able to measure the speedup.
December 13th, 2007 at 4:20 am
For comparison, running the code without the memoize decorator I get
Time elapsed: 43.063779
Running Will’s memoized version knocks it down to
Time elapsed: 0.001341
Using shedskin, http://mark.dufour.googlepages.com/, on the non-memoized version runs in
Time elapsed: 0.782071
(remember, I’m not trading memory for speed)
Making a shared library out of fib with shedskin, then importing it and using it results in:
Time elapsed: 1.242797
You really need to check out shedskin — c++ speeds, python code to maintain
December 13th, 2007 at 7:57 am
First, you have an error in the program - it says fib(2) = 1, which is wrong. Your whole sequence is one step behind. and since we’re making fast algorithms, here’s one even faster (doesn’t spend as much memory either):
from time import clock
temp = []
temp.append(1)
temp.append(1)
def fib(n):
global temp
if n %d” % (i, fib(i))
print “Time elapsed: %f” % (clock() - start)
December 13th, 2007 at 10:11 am
well, this didn’t turn out as I’d hoped… for some reason, my python code was mangled :(
December 13th, 2007 at 11:44 am
You could try something like this.
import time
def fib(n): # write Fibonacci series up to n
“”"Print a Fibonacci series up to n.”"”
a, b = 0, 1
for i in range(n):
#print b
a, b = b, a+b
startTime = time.clock()
fib(36)
print ‘elapsed time: ‘, (time.clock() - startTime)
December 13th, 2007 at 12:22 pm
the first 2 lines of fib should read:
if n == 0 or n == 1:
return 1
December 13th, 2007 at 2:43 pm
Here is a non-recursive version
def fib(n):
prev = -1
result = 1
for i in xrange(n+1):
sum = result + prev
prev = result
result = sum
return result
Time elapsed: 0.000813
July 1st, 2008 at 12:58 pm
coole 50 GB Erotik filme downloaden…
Wo kann ich filme downloaden?…