Memoization fibonacci algorithm in python

Memoization fibonacci algorithm in python

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 dont 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.

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)

Memoization fibonacci algorithm in python

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 Haskells https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation).

For a more direct (corecursive) translation see https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce.

Leave a Reply

Your email address will not be published.