That’s really shocking, I even tried several ways to optimize performance without touching the code and still performance sucks!
Fibonacci simple recursion solution takes 3 seconds to execute with C code and about 2 minutes in python!
Here is the code I used for the python version
def fib(x):
if x == 0 or x == 1: return x
return fib(x-1) + fib(x-2)
if you called fib(40) it will take about 2 minutes! the C code is exactly the same and it’s compiled with normal optmizations (-O0)
I compiled the python to pyc and used the pyc and still around 2 minutes (slightly less)
the impressive thing is that the dynamic programming solution works perfectly in no time, try this
def fib(x):
t = [0, 1]
for i in xrange(x):
t.append(t[-1] + t[-2])
return t[-2]
call it for fib(40) and see the performance gain.
the bottomline is that you shouldn’t use recursion in python.
If you have any suggestions to make this goes faster (I thought about trying stackless python here) I’m really happy to discuss them.
