Memoization

Indices and tables

Overview

  • Memoization is a programming technique used to increase the speed of program execution by storing function results so that they can be used later on.

Factorial Example

  • Consider the following function used to calculate factorials:

    1
2
3
4
5
6
    #!/usr/bin/python3

def factorial(k):
    if k < 2:
        return 1
    return k * factorial(k - 1)

  • Since this is a recursive function, it is easy to see how this function would get expensive for large values of ‘k’. But what if we didn’t have to recompute the results each time?

  • We can ‘memoize’ the function:

    1
2
3
4
5
6
7
8
9
    #!/usr/bin/python3

cache = {}
def factorial(k):
    if k < 2:
        return 1
    if k not in cache:
        cache[k] = k * factorial(k - 1)
    return cache[k]

  • The above example simply adds caching to the function itself. A more elegant solution, however, might be to wrap the function using a special ‘Memoize’ class

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    #!/usr/bin/python3

class Memoize:
   def __init__(self, fn):
       self.fn = fn
       self.memo = {}
   def __call__(self, *args):
       if args not in self.memo:
               self.memo[args] = self.fn(*args)
           return self.memo[args]

@Memoize
def factorial(k):
    if k < 2:
        return 1
    return k * factorial(k - 1)

    Note

    The example above makes use of a decorator. This is equivalent to factorial = Memoize(factorial).

  • Finally, Python actually has a built-in decorator in the functools module, ‘lru_cache’:

    1
2
3
4
5
6
7
8
9
    #!/usr/bin/python3

import functools

@functools.lru_cache
def factorial(k):
    if k < 2:
        return 1
    return k * factorial(k - 1)

  • This director has an optional maxsize argument which allows the programmer to specify the maximum size of the cache

Challenge

  • Try memoizing this fibonacci sequence method in different ways. Compare them using the timeit module.

    1
2
3
4
5
6
7
8
9
    #!/usr/bin/python3

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)