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

Speedy Fib

December 13, 2007 at 2:53 am

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.

Leave a Comment

IME Status : En

Tag Cloud