Lesson 1: Memoization
Memoization is storing the output of a function in order to reuse it again. It's going to come in handy to make our dynamic programming algorithms efficient.
Before you rush to apply memoization to an algorithm, it is important to understand when the technique can be applied and when it can't. In short, memoization can be applied to computer functions which are also mathematical functions. Although we use the same word 'function' to describe both things - a computer procedure and a binary relation over 2 sets .. it is not always the same.
Any computer function that is also a function in a mathematical sense is called a pure function.
To be pure, a function must:
Because of these properties, pure functions are the types of functions that can be memoized.
In the following exercise, think about when two consecutive calls to the same function, with the same input could return different output.
%run quizzes/quiz.py quizzes/01/pure_functions.json
VBox(box_style='info', children=(HBox(children=(HTML(value='<style>p{word-wrap: break-word}</style> <p>Which f…
Examine the following functions. Are they pure? Why or why not?
Program A
import random
g = 0
def foo(x):
g = g + random.random())
return True
foo(5)
Program B
import random
def bar(x):
return x + random.random()
bar(5)
%run quizzes/quiz.py quizzes/01/pure_functions2.json
VBox(box_style='info', children=(HBox(children=(HTML(value='<style>p{word-wrap: break-word}</style> <p>Which o…
So as we have seen, any function that depends on states or has side-effects is probably not a good candidate for memoization.
Suppose you write and debug a function. The function works well, you are very proud of yourself. But it is called way too many times by the calling program and the program is inefficient because of this. You carefully determine that your function is pure, and it can be memoized.
If the function, for example fib() is recursive, you have a problem: the calling function is fib() - and this means that in order to replace fib() with its return value, you'll have to make changes in fib() itself...
The decorator design pattern comes to you rescue: you can keep your function as is, and sort of wrap it up in a memoization function. The nice thing about this, is that you can memoize the function without changing the structure of your recursive algorithm at all!!
Why is this so good? Firstly, you don't have to debug your function again. But secondly, since we are aiming towards dynamic programming, it's important not to lose sight of the subproblems of your original problem. Your original recursive program is where you cleanly defined the sub-problems, and you don't want to mess that up.
I'll show you how this is done in Python and we'll use it in the next section to memoize fibonacci.
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
%%time
#factorial(1000)
Wall time: 0 ns
def fib(n):
if n < 2:
return 1
return fib(n-1) + fib(n-2)
%%time
fib(36)
Wall time: 4.41 s
24157817
Write a memoize function which we will use to 'decorate' factorial.
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
The memoize function takes in the factorial function and returns a helper function. This helper function is a memoized version of factorial.
helper = memoize(factorial)
helper(20)
2432902008176640000
memoized_factorial = memoize(factorial)
memoized_factorial(5)
120
Now we'll decorate factorial with memoize using the Python decorator syntax '@memoize'.
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@memoize
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
Now that we're done, profile factorial before and after memoization. You should see quite a difference when n is large.
%%time
#factorial(1000)
Wall time: 0 ns
Andres, F. (n.d.). functional programming—What do you call a function where the same input will always return the same output, but also has side effects? Software Engineering Stack Exchange. Retrieved July 9, 2020, from https://softwareengineering.stackexchange.com/a/317249
Forišek, M. (2015). Towards a better way to teach dynamic programming. Olympiads in Informatics, 9, 45–55.
Klein, B. (n.d.). Python Tutorial: Memoization and Decorators. Python Course. Retrieved June 17, 2020, from https://www.python-course.eu/python3_memoization.php
# workaround for known ipywidget issue not rendering alert style colours on Jupyter lab
from IPython.core.display import HTML
HTML(open("../styles/custom.css", "r").read())