This blog is no longer updated and is kept for archival reasons only. Please visit timothylive.net for the latest blog.

Timothy Kim::Blog - my life in words, verses and rhymes
twitter archive

Speedy Fib

I just read a blog entry about how slow python is compared to Haskell. His code was running at about 33 seconds on my machine. Then he went talking about using psyco to improve his speed. So, I tried running his psyco code and the time came out to be about 1.6 seconds.

And I thought this is just too slow. So here’s my speedy fib. It’s nothing fancy, just uses hash table to increase the speed.

  1. from time import time
  2.  
  3. fib_hash = {}
  4.  
  5. def record(n,v):
  6.     fib_hash[n] = v
  7.     return v
  8.  
  9. def fib(n):
  10.     if n == 0 or n == 1:
  11.         return record(n, n)
  12.     elif fib_hash.has_key(n):
  13.         return fib_hash[n]
  14.     else:
  15.         return record(n, fib(n-1) + fib(n-2))
  16.  
  17. if __name__ == "__main__":
  18.     start_time = time()
  19.     for i in range(36):
  20.         print "n=%d => %d" % (i, fib(i))
  21.     print "Time elapsed: %f" % (time() - start_time)

The average time for my code was 0.0014~ Woohoo~

[post script]
I tried running my code with psyco, but that made it worse. -_-;; So much for JIT.

Tags: , ,

eungyu said,

December 13, 2007 @ 5:10 pm

of course, dynamic programming is linear
as to recursive fibonacci is exponential

Timothy Kim said,

December 13, 2007 @ 6:17 pm

The blogger wasn’t complaining about programming paradigm, he was just complaining that the language itself is slow. -_-;;

I though that was just annoying, so I wrote this up.

Danyel Lawson said,

July 8, 2010 @ 1:39 pm

I read that same article and I’m sure the Haskell version is much slower as the number of items in the sequence increases. Here is an optimized reduced caching non-recursive Fibonacci sequence generator:


#!/usr/bin/env python
""" Non-recursive caching Fibonacci function """

fib_cache = [0, 1]

def fib(n):
“”" Fibonacci sum with results caching “”"

global fib_cache
for i in xrange(len(fib_cache), n + 1):
fib_cache.append(fib_cache[-2] + fib_cache[-1])
return fib_cache[n]

if __name__ == “__main__”:

fib(1000)
for t in enumerate(fib_cache):
print “n=%d => %d” % t