def fib(n):
if n == 1:
return 0
if n == 2:
return 1
return fib(n-2) + fib(n-1)
def memo(f):
cache = {}
def memoized(n):
if n not in cache:
cache[n] = f(n)
return cache[n]
return memoized
fib1 = memo(fib)
This code runs really slow on my laptop, but if I change the name fib1 to fib, then everything works fine...anyone know the reason ? Thanks!
fib recurses into fib, not fib1. If the memoized version has a different name it won't get used.
In that code fib is the name of the non-memoized function. fib1 is the name you've given to the memoized function. But if you see your code, you'll see that it recursively calls fib the non-memoized version. Hence why you aren't getting a speed advantage.
I agree that adding some prints you would probably see the issue. You're very close to actually getting it.
What you have right now only stores n where n is the argument given to fib1. Inside fib, you're calling fib which won't memoize any previously computed values. So by adding a print statement to fib print "fib ", n and calling fib1(4), you will get the following output:
fib 4
fib 2
fib 3
fib 1
fib 2
So you see it calls fib with n=2 twice. The reason why fib = memo(fib) is faster is because then it's actually momoizing because you're redefining fib to be the memoized function.
In python 3 you can achieve your goal by using nonlocal as pointed out here.
def memo(f):
cache = {}
def memoized(n):
nonlocal cache
if n not in cache:
cache[n] = f(n)
return cache[n]
return memoized
Python's functools module provides decorators that accomplish caching. There is a limit to these approaches in that they add cost to the total recursion depth. An alternate approach using closures allows for deeper recursion.
def fibonacci(n):
cache = {0:0,1:1}
def fib(n):
if n in cache:
return cache[n]
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib(n)
