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

Django v1.0

September 4, 2008 at 9:48 am

Django v1.0

Productivity for today is down the drain… -_-

Tags: , ,

Comments (2)

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: , ,

Comments (2)

Tag Cloud