Memoization

Memoization is a technique to speed up computer programs by return values ​​instead are cached by functions recalculated. Memoization is similar to dynamic programming, preserved but, in contrast to this is the basic procedure of the process to be accelerated.

Functions can only be " memoisiert " if they are referentially transparent, that is, they give with the same inputs always return the same outputs. Operations that are not referentially transparent, but where deviations in the output are relatively rare to be expected, can be cached by other methods ( such as cache ). Have general " memoisierte " spending no expiration date and do not have to be recalculated, as is the case with caches in general. In imperative programming languages ​​memoization is usually implemented in the form of an associative array.

In a functional programming language, it is possible a higher-order function memoize to construct for each function referentially transparent. In languages ​​without the possibility of a higher-order function, the memoization must be implemented separately in each function that makes use of it.

Etymology

" Memoization " is derived from the Latin word memorandum, which translates as " to the Reminiscent " means. In common parlance memorandum is also called memo and you can understand memoization as " convert a function in a memo ."

The word memoization is often confused with the English word Memorization, which has a similar meaning.

Example

A simple program that calculates the Fibonacci numbers is

(This example is not meant to efficient implementation. It is used solely to illustrate the memoization. )

Because fib () is called with the same parameters several times, the term of the function is greater than O ( 1.6N ). If you " memoisiert " the values ​​of fib ( n ) at the first calculation and the memory allocation and initialization in O (n) can be made, the running time is reduced to O ( n ).

History

The English word " memoization " was created in 1968 by Donald Michie in his article, " Memo functions and machine learning" in the journal Nature.