✢ Memoization

Learning Objectives

At the end of this sub-unit, students should

appreciate the similarity between data and computation.

Pure Function as Data

In the previous sub-unit, we encountered a curious fact that a mapping table can be represented as either one of the following.

A function with a sequence of if-statements.
A dictionary which is a mapping from key to value.

Since the table is finite in this case, we have a complete mapping.

As Function

def ingredient_price(ingredient):
  if ingredient == 'Bread':
    return 1
  if ingredient == 'Beef':
    return 7
  # other code omitted

As Dictionary

PRICE = {
  'Bread': 1, 'Beef': 7, 'Chicken': 4,
  'Vegetable': 2, 'Mushroom': 3, 'Cheese': 1,
  'Onions': 1, 'Hash Brown': 2
}
def ingredient_price(ingredient):
  return PRICE[ingredient]

Can this be generalized further? At some point, the dictionary may be very large so it may not be worth it. In fact, for some operation such as add 1, the table is theoretically infinite but the code is rather trivial.

As Function
1 2
def add1(val): return val + 1

As Dictionary

ADD1 = { 0: 1, 1: 2, 2: 3, 3: 4, ... }
def add1(val):
  return ADD1[val]

Ok, so there is a similarity between data and computation, but what is the use of this? We can speed up a computation by storing the result of a repeated computation. To do this, we first represent a function f(param1, param2) as a mapping from (param1, param2) to some value. This only works for pure function where the result is purely dependent in the input parameter.

So to represent this as a dictionary, we set the key as the tuple (param1, param2). If we have more parameters, we simply add more values. To avoid pre-computing all the possible mappings, we will add the result only after we compute at least once. So the next time we invoke the function f with the same parameter, we do not need to perform the computation. We can simply retrieve the result from the dictionary.

Let us illustrate this with the factorial function. The original recursive factorial function is reproduced below.

def factorial(n):
  if n == 0:
    return 1
  else:
    return n * factorial(n - 1)

The conversion to the memoized version will be done as follows.

Before we perform the computation, we check if the parameter has already been computed before.
- We check this by looking at the key in the dictionary.
If it has been computed, we simply return the corresponding value from the dictionary.
Otherwise, we perform the computation.
- At the end of the computation, we update the dictionary by adding the mapping from the current parameter to the corresponding result.

Memoized Factorial

MEMO = {}
def factorial(n):
  # Value in memo: retrieve
  if n in MEMO:
    print("Retrieve")
    return MEMO[n]

  # Value not in memo: compute
  print("Compute:", n)
  if n == 0: # no need to store base case
    return 1
  else:
    res = n * factorial(n - 1)
    MEMO[n] = res  # store
    return res

>>> factorial(10)
Compute: 10
Compute: 9
Compute: 8
Compute: 7
Compute: 6
Compute: 5
Compute: 4
Compute: 3
Compute: 2
Compute: 1
Compute: 0
3628800
>>> MEMO
{1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040, 8: 40320, 9: 362880, 10: 3628800}
>>> factorial(9)  # no need to compute!
Retrieve
362880

Fibonacci

This idea of memoization is useful for non-linear recursion especially non-linear recursion where there can be repeated computation. Take for instance the Fibonacci series represented by the following recursive formula.

\[ \begin{align} \text{Fib}(0) & = 0 \\ \text{Fib}(1) & = 1 \\ \text{Fib}(n) & = \text{Fib}(n - 1) + \text{Fib}(n - 2) \end{align} \]

We can write the code as follows.

Fibonacci

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

We can see here that fib(n - 2) will be computed at least twice because when we compute fib(n - 1), we will continue with the following: fib(n - 1) ⇝ fib(n - 2) + fib(n - 3). So it will be very very useful if we can memoize the value of fib(n - 2). This way, we do not have to recompute it the next time we encounter it.

Memoized Fibonacci

MEMO = {}
def fib(n):
  if n in MEMO:
    return MEMO[n]

  if n <= 1:
    MEMO[n] = n
    return n
  else:
    res = fib(n - 1) + fib(n - 2)
    MEMO[n] = res
    return res

Memo as List

Our current memo uses a dictionary. But our parameter for Fibonacci is actually an integer. So do we really need a dictionary? Can we use a list? In this case, yes. The function is as followed.

List Fibonacci

MEMO = []
def fib(n):
  if n < len(MEMO):
    return MEMO[n]

  if n <= 1:
    while len(MEMO) <= n:
      MEMO.append(0)
    MEMO[n] = n
    return n
  else:
    res = fib(n - 1) + fib(n - 2)
    while len(MEMO) <= n:
      MEMO.append(0)
    MEMO[n] = res
    return res

Now that we write our Fibonacci this way, we can see that fib(n) will eventually create a list of size n + 1 where the value at index n is exactly the solution to fib(n). Notice that fib(n) requires results from fib(n - 1) and fib(n - 2). These results will eventually be stored in index n - 1 and n - 2. Hence, if we fill in the list from the smallest value to the largest value, we can fill in the memo from left to right.

This gives us the following code. In the following code, we put the memo inside the function.

Dynamic Fibonacci

def fib(n):
  MEMO = [0, 1]
  while len(MEMO) <= n:
    MEMO.append(MEMO[-1] + MEMO[-2])
  return MEMO[n]

Now we can see that we only see need the previous two values at each iteration (i.e., MEMO[-1] and MEMO[-2]). So we do not need the entire list. In fact, we only need two variables. This gives us the following iterative solution for Fibonacci.

Iterative Fibonacci

def fib(n):
  n2, n1 = 0, 1
  for i in range(n):
    n2, n1 = n1, n1 + n2
  return n2