Memoization |
Memoization is a technique used to speed up computer 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 referential transparency -- 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.
= 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 Big O notation(1.6n). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Big O notation(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 closure (computer science)s 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 programming language 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.
=Sample Implementations=
== Python ==
A naive memoization example in Python, using nested Scope (programming):
def memoize(f): cache = {} def g(*args): if args not in cache: cache[args] = f(*args) return cache[args] return g
def fib(n): if n in [0, 1]: return n return fib(n-1)+fib(n-2)
fib = memoize(fib)
This naive memoizer will use ever-increasing amounts of memory, since old items are never removed from the cache. Memory usage can be improved by using a cache eviction scheme such as Least_recently_used, caching results only for a prespecified time [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/325905], or by clearing the cache when the last call to f returns [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440678].
= Maple =
The Maple computer algebra system has built-in memoization though the use of so-called remember tables . For example, define a procedure square as follows:
square := proc(x) option remember; x^2; end proc:
Then any calls to square will cause an entry to be written to square s remember table for later use. This table can be extracted:
> square(4), square(7); # cause two entries to be written to remember table 16, 49
> op(4, eval(square)); # view the remember table and its entries table([4 = 16, 7 = 49])
=History=
The term memoization was coined by Donald Michie in his 1968 paper Memo functions and machine learning in Nature (journal) .
=Some uses=
*Search engine *Source code generation, including HTML *Repetitive Computations, such as Digital image conversion, Encryption, and data compression.
=External links=
*[http://search.cpan.org/dist/Memoize/Memoize.pm Memoize.pm] - a Perl Perl module that implements memoized subroutines
*[http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html Java memoization] - an example in Java using dynamic proxy classes to create a generic memoization pattern.
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|
|