Memoization

From CS 61A Wiki
Revision as of 00:10, 24 June 2014 by Alc (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 computation. Memoized functions store previous return values and return the stored results when calls with the same arguments are repeated as opposed to constantly recalculating them.

Structure

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

Example 1

>>> def memo(f):
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized
>>> def count_partitions(n, m):
        """Count the ways to partition n using parts up to m."""
        if n == 0:
            return 1
        elif n < 0:
            return 0
        elif m == 0:
            return 0
        else:
            return count_partitions(n-m, m) + count_partitions(n, m-1)
>>> memoized_partitions = memo(count_partitions)

Example 2

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

Sources