Memoization Fibonacci Algorithm In Python
Solution 1:
It can be done with functools library in Python 3.2+
import functools
@functools.lru_cache(maxsize=None) #128 by default
def fib(num):
if num < 2:
return num
else:
return fib(num-1) + fib(num-2)
Solution 2:
You should return memo[n]
always, not only on unseccesful look up (last line of fastFib()
):
def fastFib(n, memo):
global numCalls
numCalls += 1
print 'fib1 called with', n
if not n in memo:
memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
#this should be outside of the if clause:
return memo[n] #<<<<<< THIS
The number of calls is reduced this way, because for each value of n
you actually compute and recurse from at most once, limitting the number of recursive calls to O(n)
(upper bound of 2n
invokations), instead of recomputing the same values over and over again, effectively making exponential number of recursive calls.
A small example for fib(5), where each line is a recursive invokation:
Naive approach:
f(5) =
f(4) + f(3) =
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =
1 + f(0) + f(1) + f(2) + f(3) =
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =
3 + f(1) + f(0) + f(3) =
3 + 1 + f(0) + f(3) =
5 + f(3) =
5 + f(2) + f(1) =
5 + f(1) + f(0) + f(1) =
5 + 1 + f(0) + f(1) =
5 + 2 + f(1) =
8
Now, if you use memoization, you don't need to recalculate a lot of things (like f(2)
, which was calculated 3 times) and you get:
f(5) =
f(4) + f(3) =
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) =
1 + f(0) + f(1) + f(2) + f(3) =
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) = {f(2) is already known}
3 + 2 + f(3) = {f(3) is already known}
5 + 3 =
8
As you can see, the second is shorter than the first, and the bigger the number (n
) becomes, the more significant this difference is.
Solution 3:
The following method uses a minimal cache size (2 entries) while also providing O(n) asymptotics:
from itertools import islice
def fibs():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
def fib(n):
return next(islice(fibs(), n-1, None))
This implementation comes from the classic corecursive definition of fibonacci (a la Haskell's https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation).
For a more direct (corecursive) translation see https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce.
Solution 4:
It can be done within a single class or a function as follows
class Solution:
def __init__(self):
# initialize memo
self.memo = {}
def fib(self, n: int) -> int:
# base case
if n < 2:
return n
# check if fib(n) is already in memo - f(n) was calculated before
if n in self.memo:
return self.memo[n]
else:
f = self.fib(n - 1) + self.fib(n - 2)
# store the value of fib(n) when calculated
self.memo[n] = f
return f
Post a Comment for "Memoization Fibonacci Algorithm In Python"