Memoization

Encyclopedia : M : ME : MEM : 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.

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 imperative languages, both memoization and more general caching are typically implemented using some form of associative array.

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.

Memoization is well-described in Paradigms of Artificial Intelligence Programming, by Peter Norvig, pp269-275.

Contents

1 Etymology
2 Example
3 History
4 Some uses
5 External links

Etymology

"Memoization" is derived from the Latin word memorandum, meaning what must be remembered. In common parlance, a memorandum is abbreviated as memo, and thus "memoization" means "to turn (a function) into a memo".

The word memoization is often confused with memorization, which, although a good description of the process, is not limited to this specific meaning.

Example

A naïve program to compute Fibonacci numbers is

fib(n)

(This is not meant to be an efficient implementation: it is only intended to illustrate the concept of memoization. Fibonacci numbers can be computed in constant time via a closed form expression; see Fibonacci numbers.)

Because fib() is recomputed over and over for the same argument, run time for the above is O(1.6ⁿ). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is O(n).

allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;

fib(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) 
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)

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] - Memoize is a small library for performing memoization in Common Lisp. It was written by Tim Bradshaw.
[Memoize.pm] - a Perl module that implements memoized subroutines
[Java memoization] - an example in Java using dynamic proxy classes to create a generic memoization pattern.
[memoize] - a Ruby module that implements memoized methods.
[Python memoization] - a Python example of memoization.
[OCaml memoization] implemented as a Camlp4 syntax extension.
[a C# 2.0 example] of memoization
[Memoization in Lua] - two example implementations of a general memoize function in Lua

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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.