Memoization

From CS 61A Wiki
Revision as of 09:01, 5 July 2014 by Axis (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to: navigation, search

Memoization is a technique for improving the efficiency of tree recursive processes that repeat computations. Memoized functions store the results of expensive calculations and return the cached result when the same inputs occur again, rather than recalculating it.

In terms of order of growth, memoization trades memory for time.

Structure

Memoization is implemented through higher-order functions or can also be integrated directly into a function. The dictionary is commonly used as a data structure to store items by mapping immutable arguments to their return values.

With an HOF

The following memo function is a wrapper for a function to be memoized.

def memo(f):
    cache = {}
    def memoized(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return memoized

The wrapper can be used by adding a decorator to the function to be memoized:

@memo
def count_partitions(n, m):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    return count_partitions(n - m, m) + count_partitions(n, m - 1)

or by explicitly creating a memoized version of the function:

memoized_partitions = memo(count_partitions)

Integrated

Memoization can be integrated directly in a function. Example:

cache = {}
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n not in cache:
        cache[n] = fib(n - 2) + fib(n - 1)
    return cache[n]

Sources