Memoization For Beginners

Elliot Forbes ⏰ 3 Minutes 📅 Nov 18, 2017

In this tutorial we are going to look at a concept in computer science called memoization. This is a really cool concept that allows us to optimize the runtime performance of some of our recursive algorithms by effectively caching the results of previous computations so that they don’t have to be continuously re-computed.

The Fibonacci Example

Calculating Fibonacci in a recursive manner is quite possibly the best example I’ve come across when it comes to showing the power of memoization.

Imagine we had a function that computed the fibonacci number n like so:

## Basic fibonacci function
## 1 + 1 + 2 + 3 + 5 + 8 + 13
def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

When we then tried to run our fib(7) function it would then compute the following answer.

>>> import fibonacci
>>> fibonacci.fib(7)
13

Now the runtime complexity of this relatively simple function above would be O(2^n) which is incredibly inefficient as we start to compute larger and larger fibonacci numbers.

The Memoization Optimization

Through the use of memoization we could effectively store the results of previous computations. In order to store our results we will use a dict in Python.

def fib_with_memo(n, memo):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n not in memo:
        print("Memo Computed")
        memo[n] = fib_with_memo(n-1, memo) + fib_with_memo(n-2, memo)

    return memo[n]

memo = {}

print(fib_with_memo(9, memo))
print(memo)

When you run this you should get the following output. As you can see from the number of times Memo Computed is printed out, we have been able to effectively optimize the number of times we have to recursively call fib().

 $ python3.6 fibonacci.py
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
Memo Computed
34
{2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34}

We have been able to modify our program and change is runtime performance from O(2^N) to O(N) which is a huge saving.

Entire Program

The entire Python file can be found below.

import time

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

def fib_with_memo(n, memo):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n not in memo:
        memo[n] = fib_with_memo(n-1, memo) + fib_with_memo(n-2, memo)

    return memo[n]

memo = {}

start_time = time.time()
print(fib(35))
end_time = time.time()
print("Total Time: {}".format(end_time - start_time))

start_time = time.time()
print(fib_with_memo(35, memo))
end_time = time.time()
print("Total Time: {}".format(end_time - start_time))

print(memo)

The outputs of this are:

 $ python3.6 fibonacci.py
9227465
Total Time: 7.323758840560913
9227465
Total Time: 0.00010204315185546875
{2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025,26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040, 31: 1346269, 32: 2178309, 33: 3524578, 34: 5702887, 35: 9227465}

As you can see the memoized version of the fibonacci function returns in a fraction of the time.

Conclusion

If you found this tutorial useful or need further explanation then please feel free to let me know in the comments section below!