Memorización

Memoization o Memoisierung es una técnica para que los programas de computadora aceleren al devolver valores almacenados en caché por funciones en lugar de ser recalculados. La memorización es similar a la programación dinámica , pero a diferencia de esto, conserva el procedimiento básico del proceso a acelerar.

Las funciones solo se pueden memorizar si son referencialmente transparentes , es decir, En otras palabras, siempre devuelven las mismas salidas para las mismas entradas. Las operaciones que no son referencialmente transparentes, pero para las que se esperan desviaciones en la salida con relativa poca frecuencia, se pueden almacenar en caché utilizando otros métodos (como la caché ). En general, las salidas memorizadas no tienen una fecha de vencimiento y no tienen que ser recalculadas, como suele ser el caso de las memorias caché. En los lenguajes de programación imperativos , la memorización generalmente se implementa en forma de una matriz asociativa .

En un lenguaje de programación funcional , es posible construir una función de orden superior memoize para cada función referencialmente transparente. En lenguajes sin posibilidad de función de orden superior, la memorización debe implementarse por separado en cada función que la utilice.

etimología

La palabra inglesa memorización fue creada en 1968 por Donald Michie a partir de su artículo Funciones de memorización y aprendizaje automático en la revista Nature .

Memoisation se deriva de la palabra latina memorandum , que significa algo así como "lo que debe recordarse". En el lenguaje común, el memorando también se llama memo y el memorando puede entenderse como una función de convertirlo en un memo.

La palabra memorización a menudo se confunde con la palabra inglesa memorización , que tiene un significado similar.

ejemplo

Un programa simple que calcula los números de Fibonacci es 

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

(Este ejemplo no pretende ser una implementación eficiente. Solo se usa para ilustrar la memorización).

Debido a que los fibmismos parámetros se llaman varias veces, el tiempo de ejecución de la función es mayor que O (1,6 n ). Si los valores de se fibmemorizan durante el primer cálculo y la reserva de memoria y la inicialización se pueden realizar en O (n), el tiempo de ejecución cae a 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]

En lugar de una matriz, ahora debería usarse una matriz asociativa. Si el lenguaje de programación ofrece la posibilidad de formular cierres , se puede escribir una función memorizar que abstraiga el principio de memorización fib. 

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

fib = memoize(fib)

Además de la memorización, la recursividad también se produce en este ejemplo. Tenga en cuenta que también debe fibhaber una variable dentro de su propia definición, cuyo contenido se ha sobrescrito con la versión memorizada. Si eso no es posible, la memorización se puede incorporar alternativamente en el combinador de punto fijo . Esto viene dado inicialmente por: 

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

El algoritmo modificado ahora incluye el procedimiento descrito anteriormente: 

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

literatura

enlaces web

  • Memoize : Memoize es una pequeña biblioteca para la memorización en Common Lisp. Fue escrito por Tim Bradshaw.
  • Memoize.pm : un módulo de Perl que contiene subrutinas memorizadas.
  • Memoisation de Java : un ejemplo en Java que utiliza una clase de proxy dinámica.
  • memoize : un módulo Ruby con métodos Memoise.
  • Memorización de Python : un ejemplo de memorización en Python.