Memoization
|
|
Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. Memoization is a characteristic of dynamic programming. Memoization literally means "to put in memory" and is derived from the Latin word memorandum, meaning what must be remembered. The word memoization is often confused with memorization, which, although a good description of the process, is not limited to this specific meaning.
Functions can only be memoized if they are referentially transparent -- that is, if they will always return the same result given the same arguments. Operations which are not referentially transparent, but whose results are not likely to change rapidly, can still be cached with methods more complicated than memoization. In general, memoized results are not expired or invalidated later, while caches generally are.
In a functional programming language it is possible to construct a higher-order function memoize which will create a memoized function for any referentially transparent function. In languages without higher-order functions, memoization must be implemented separately in each function that is to benefit from it.
| Contents |
Example
A naive program to compute Fibonacci numbers is
fib(n) {
if n is 1 or 2, return 1;
return fib(n-1) + fib(n-2);
}
Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6n). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Θ(n).
allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;
fib(n) {
if memo[n] is not zero, return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}
In a language with closures and higher-order functions, the memoization of any function can be automatically defined. Here "memoize" constructs and returns another function which serves as the memoization of the argument f.
memoize(f) {
allocate array for memo, setting all entries to zero;
construct a new function called "temp":
temp(*args) {
if args not in memo {
memo[args] = f(*args)
}
return memo[args]
}
return temp
}
The notation *args is meant to represent a rest argument as in Python or Common Lisp. This solution relies on returning a closure over the variable memo, which serves as a cache for the returned function.
This function "memoize" can be used to construct a memoized version of "fib":
memofib = memoize(fib)
Computing Fibonacci numbers can be done in logarithmic time (see Fibonacci numbers); this example illustrates the concept of memoization.
History
The term "memoization" was coined by Donald Michie in his 1968 paper "Memo functions and machine learning" in Nature.
Some uses
- Searching
- Source code generation, including HTML
- Repetitive computations, such as image conversion, encryption, and data compression.
- Pattern recognition such as speech recognition
- Game tree evaluation
External links
- Memoize.pm (http://search.cpan.org/dist/Memoize/Memoize.pm) - a Perl module that implements memoized subroutines
Note: This article contains material taken from a public domain entry within the NIST Dictionary of Algorithms and Data Structures at http://www.nist.gov/dads/HTML/memoize.html