Memoization

From Free net encyclopedia

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 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) {
   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 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) {
   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 - 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

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.htmlko:메모이제이션 sv:Memoisation