Memoization

from Wikipedia, the free encyclopedia

Memoisation is a technique to speed up computer programs by temporarily storing return values ​​from functions instead of recalculating them. Memoization is similar to dynamic programming , but in contrast to this, it preserves the basic procedure of the process to be accelerated.

Functions can only be memoized if they are referentially transparent , i.e. In other words, they always return the same outputs for the same inputs. Operations that are not referentially transparent, but for which deviations in the output are to be expected relatively rarely, can be cached using other methods (such as cache ). In general, memoized outputs do not have an expiration date and do not have to be recalculated, as is generally the case with caches. In imperative programming languages , memoization is usually implemented in the form of an associative array .

In a functional programming language , it is possible to construct a higher order function memoize for each referentially transparent function. 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

Memoisation is derived from the Latin word memorandum , which means something like "that which is to be remembered". In common parlance, memorandum is also called memo and memoization can be understood as a function of converting it into 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 

function fib(n)
    if (n <= 2)
        return 1
    return fib(n-1) + fib(n-2)

(This example is not intended to be an efficient implementation. It is only used to illustrate the memoization.)

Because the fibsame parameters are called several times, the runtime of the function is greater than O (1.6 n ). If the values ​​of are fibmemorized during the first calculation and the memory reservation and initialization can be made in O (n), the running time drops to O (n). 

Speicher für Memo-Array memo reservieren und alle Werte darin auf 0 setzen.
Initialisiere memo[1] und memo[2] auf 1.

function fib(n)
    if (memo[n] ≠ 0) return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Instead of an array, an associative array should now be used. If the programming language offers the possibility of formulating closures , a function memoize can be written that fibabstracts the principle of memoization from . 

function memoize(f)
    var memo = { }
    return function(n)
        if (n not in memo) memo[n] = f(n)
        return memo[n]

fib = memoize(fib)

In addition to memoization, recursion also occurs in this example. Please note that there must fibalso be a variable within its own definition, the content of which has been overwritten with the memoized version. If that is not possible, the memoization can alternatively be built into the fixed point combiner . This is initially given by: 

function fix(F)
    return function f(n)
        return F(f,n)

The modified algorithm now includes the procedure described above: 

function fix(F)
    var memo = { }
    return function f(n)
        if (n not in memo) memo[n] = F(f,n)
        return memo[n]

fib = fix(function(f,n))
    return 1 if n <= 2 else f(n-1) + f(n-2))

history

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

literature

Web links

  • Memoize - Memoize is a small library for memoization in Common Lisp. It was written by Tim Bradshaw.
  • Memoize.pm - a Perl module that contains memoized subroutines.
  • Java Memoisation - an example in Java that uses a dynamic proxy class.
  • memoize - a Ruby module with Memoise methods.
  • Python memoization - an example of memoization in Python.