python - Why my using memo didn't raise the efficiency at all? -
i doing exercise in think in python, using memo calculate fibonacci sequence far more efficiency not using one. when implemented , testing time consumed, find running time not reduced @ all. know there wrong program, please tell me went wrong. many thanks.
import time known = {0:0,1:1} def fibonacci_memo(n): """return nth number of fibonacci sequence using memo raise efficiency""" if n in known: return known[n] res = fibonacci(n-1) + fibonacci(n-2) known[n] = res return res def fibonacci(n): """return nth number of fibonacci sequence without using memo""" if n == 0: return 0 if n == 1: return 1 return fibonacci(n-1) + fibonacci(n-2) if __name__ == '__main__': start = time.clock() print fibonacci_memo(32) elaspsed = time.clock() - start print 'using memo time used: ' + str(elaspsed) start = time.clock() print fibonacci(32) elaspsed = time.clock() - start print 'without using memo time used: ' + str(elaspsed)
the output like:
2178309 using memo time used: 1.83040345779 2178309 without using memo time used: 1.792043347
your fibonacci_memo function isn't calling recursively, it's calling original (non-memoized) fibonacci function.
Comments
Post a Comment