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!
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!
Nice, but the point was in measuring the speed of languages, without changing the naive algorithm...
@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.
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.
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.
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.
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
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)
well, this didn't turn out as I'd hoped... for some reason, my python code was mangled :(
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)
the first 2 lines of fib should read:
if n == 0 or n == 1:
return 1
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
If you're generating the sequence in order anyway, there is no point in memoization. You're sacrificing a lot of space to save all these results, when all you really need is the result of the last two calls. Using a function like Bob's is more space-efficient, and should run at least as fast (probably slightly faster because the cache lookups take some small amount of time).
I'd write a generator for this myself:
def gen_fib(n):
a, b = 0, 1
for dummy in range(n):
yield b
a, b = b, a + b
This is probably the fastest way to generate the sequence in order. If you need fast access to random elements from the sequence, the closed-form solution is probably faster since it does not have to generate the entire sequence for each call:
sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
def fib(n):
"""return the nth element from the sequence"""
return round(phi**n / sqrt5)
it pre-computes the phi and sqrt(5) calls. The algorithm is most likely O(n) because I think the ** operation is. But this is done in C and should be very fast. Like I said, generating the sequence in order is probably faster using the generator since it doesn't involve a division and power operation.
Disclaimer: none of this has been timed, I may be wrong in performance assumptions.
Note:I disregarded the article's time since it was proven to be 3 milliseconds in actuality.