# Difference between revisions of "Memoization"

[checked revision] | [checked revision] |

m (reword) |
(add) |
||

Line 1: | Line 1: | ||

{{Sufficient-class}} | {{Sufficient-class}} | ||

'''Memoization''' is a technique for improving the efficiency of [[recursion#Tree_recursion|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. | '''Memoization''' is a technique for improving the efficiency of [[recursion#Tree_recursion|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== | ==Structure== |

## Latest revision as of 09:01, 5 July 2014

**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]