Memorización - Memoization

No confundir con la memorización .
"Tabulación" vuelve a dirigir aquí. Para conocer el procedimiento parlamentario, consulte la Tabla (procedimiento parlamentario) .

En computación , memoization o memoisation es una optimización técnica que se utiliza principalmente para acelerar los programas de ordenador mediante el almacenamiento de los resultados de costosas llamadas de función y devolver el resultado en caché cuando se producen las mismas entradas de nuevo. La memorización también se ha utilizado en otros contextos (y con fines distintos a las ganancias de velocidad), como en el análisis sintáctico simple de descenso recursivo mutuo . Aunque se relaciona con el almacenamiento en caché , la memorización se refiere a un caso específico de esta optimización, distinguiéndola de formas de almacenamiento en caché como el almacenamiento en búfer o el reemplazo de páginas . En el contexto de algunos lenguajes de programación lógica , la memorización también se conoce como tabulación .

Etimología

El término "memorización" fue acuñado por Donald Michie en 1968 y se deriva de la palabra latina " memorandum " ("para ser recordado"), generalmente truncado como "memo" en inglés americano, y por lo tanto tiene el significado de "girar [el resultados de] una función en algo para ser recordado ". Mientras que "memorización" puede confundirse con " memorización " (porque son cognados etimológicos ), "memorización" tiene un significado especializado en informática.

Visión general

Una función memorizada "recuerda" los resultados correspondientes a algún conjunto de entradas específicas. Las llamadas subsiguientes con entradas recordadas devuelven el resultado recordado en lugar de recalcularlo, eliminando así el costo principal de una llamada con parámetros dados de todas menos la primera llamada realizada a la función con esos parámetros. El conjunto de asociaciones recordadas puede ser un conjunto de tamaño fijo controlado por un algoritmo de reemplazo o un conjunto fijo, según la naturaleza de la función y su uso. Una función solo se puede memorizar si es referencialmente transparente ; es decir, solo si llamar a la función tiene exactamente el mismo efecto que reemplazar esa llamada de función con su valor de retorno. (Sin embargo, existen excepciones de casos especiales a esta restricción). Si bien está relacionado con las tablas de búsqueda , dado que la memorización a menudo usa tales tablas en su implementación, la memorización llena su caché de resultados de forma transparente sobre la marcha, según sea necesario, en lugar de hacerlo por adelantado.

La memorización es una forma de reducir el costo de tiempo de una función a cambio del costo de espacio ; es decir, las funciones memorizadas se optimizan para la velocidad a cambio de un mayor uso del espacio de memoria de la computadora . El "costo" de tiempo / espacio de los algoritmos tiene un nombre específico en computación: complejidad computacional . Todas las funciones tienen una complejidad computacional en el tiempo (es decir, requieren tiempo para ejecutarse) y en el espacio .

Aunque se produce una compensación espacio-tiempo (es decir, el espacio utilizado es la velocidad ganada), esto difiere de algunas otras optimizaciones que implican una compensación espacio-temporal, como la reducción de la fuerza , en que la memorización es un tiempo de ejecución en lugar de un tiempo de compilación. mejoramiento. Por otra parte, la reducción de la fuerza potencialmente reemplaza una operación costosa como la multiplicación con una operación menos costoso tal como adición, y los resultados en ahorro puede ser altamente dependiente de la máquina (no portátil a través de máquinas), mientras que memoization es un más independiente de la máquina, transversal -Estrategia de plataforma .

Considere la siguiente función de pseudocódigo para calcular el factorial de n : 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Para cada entero n tal que n ≥ 0, el resultado final de la función factoriales invariante ; Si se invoca como x = factorial(3), el resultado es tal que x será siempre se le asigna el valor 6. La aplicación no memoized anteriormente, dada la naturaleza de la recursivo algoritmo implicado, requeriría n + 1 invocaciones de factorialllegar a un resultado de ello, y cada uno de estas invocaciones, a su vez, tienen un costo asociado en el tiempo que tarda la función en devolver el valor calculado. Dependiendo de la máquina, este costo puede ser la suma de:

  1. El costo de configurar el marco de pila de llamadas funcional.
  2. El costo de comparar n con 0.
  3. El costo de restar 1 de n .
  4. El costo de configurar el marco de pila de llamadas recursivas. (Como anteriormente.)
  5. El costo de multiplicar el resultado de la llamada recursiva a factorialpor n .
  6. El costo de almacenar el resultado de la devolución para que pueda ser utilizado por el contexto de llamada.

En una implementación no memorizada, cada llamada de nivel superior a factorialincluye el costo acumulativo de los pasos 2 a 6 proporcional al valor inicial de n .

A continuación, se muestra una versión memorizada de la factorialfunción: 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

En este ejemplo en particular, si factorialprimero se invoca con 5 y luego se invoca más tarde con cualquier valor menor o igual a cinco, esos valores de retorno también se habrán memorizado, ya que factorialse habrán llamado de forma recursiva con los valores 5, 4, 3, 2, 1 y 0, y se habrán almacenado los valores devueltos para cada uno de ellos. Si luego se llama con un número mayor que 5, como 7, solo se realizarán 2 llamadas recursivas (7 y 6), ¡y el valor de 5! se habrá almacenado de la llamada anterior. De esta manera, la memorización permite que una función sea más eficiente en el tiempo cuanto más a menudo se llama, lo que resulta en una eventual aceleración general.

Algunas otras consideraciones

Programación funcional

Artículo principal: Thunk § Programación funcional

La memorización se utiliza mucho en compiladores de lenguajes de programación funcionales , que a menudo utilizan la estrategia de evaluación de llamada por nombre . Para evitar la sobrecarga con el cálculo de los valores de los argumentos, los compiladores de estos lenguajes utilizan en gran medida funciones auxiliares llamadas thunks para calcular los valores de los argumentos y memorizar estas funciones para evitar cálculos repetidos.

Memoización automática

Mientras memoization se puede añadir a las funciones internamente y explícitamente por un programador de ordenadores de la misma forma en que la versión anterior memoized de factorialse implementa, referencialmente funciones transparentes también se pueden memoized automáticamente externamente . Las técnicas empleadas por Peter Norvig tienen aplicación no solo en Common Lisp (el lenguaje en el que su artículo demostró la memorización automática), sino también en varios otros lenguajes de programación . Las aplicaciones de la memorización automática también se han explorado formalmente en el estudio de la reescritura de términos y la inteligencia artificial .

En lenguajes de programación donde las funciones son objetos de primera clase (como Lua , Python o Perl ), la memorización automática se puede implementar reemplazando (en tiempo de ejecución) una función con su valor calculado una vez que se ha calculado un valor para un conjunto dado. de parámetros. La función que realiza este reemplazo de valor por función-objeto puede envolver genéricamente cualquier función referencialmente transparente. Considere el siguiente pseudocódigo (donde se asume que las funciones son valores de primera clase): 

function memoized-call (F is a function object parameter)
    if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
    end if;

    if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;

    return F.values[arguments];
end function

Para llamar a una versión memorizada automáticamente de factorialusar la estrategia anterior, en lugar de llamar factorialdirectamente, el código invoca . Cada una de estas llamadas primero verifica si se ha asignado una matriz de soporte para almacenar los resultados y, si no, adjunta esa matriz. Si no existe ninguna entrada en la posición (donde se utilizan como clave de la matriz asociativa), se realiza una llamada real a con los argumentos proporcionados. Finalmente, la entrada en la matriz en la posición clave se devuelve a la persona que llama. memoized-call(factorial(n))values[arguments]argumentsfactorial

La estrategia anterior requiere un ajuste explícito en cada llamada a una función que se va a memorizar. En aquellos idiomas que permiten cierres , memoization puede efectuarse implícitamente a través de un funtor fábrica que devuelve un objeto función memoized envuelta en un patrón decorador . En pseudocódigo, esto se puede expresar de la siguiente manera: 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

En lugar de llamar factorial, memfactse crea un nuevo objeto de función de la siguiente manera: 

 memfact = construct-memoized-functor(factorial)

El ejemplo anterior asume que la función factorialya se ha definido antes de que construct-memoized-functorse realice la llamada a . A partir de este punto, se llama siempre que se desee el factorial de n . En lenguajes como Lua existen técnicas más sofisticadas que permiten reemplazar una función por una nueva función con el mismo nombre, lo que permitiría: memfact(n)

 factorial = construct-memoized-functor(factorial)

Esencialmente, tales técnicas implican adjuntar el objeto de función original al functor creado y reenviar las llamadas a la función original que se memoriza a través de un alias cuando se requiere una llamada a la función real (para evitar la recursividad sin fin ), como se ilustra a continuación: 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

(Nota: algunos de los pasos que se muestran arriba pueden ser administrados implícitamente por el lenguaje de implementación y se proporcionan a modo de ilustración).

Analizadores

Cuando un analizador de arriba hacia abajo intenta analizar una entrada ambigua con respecto a una gramática libre de contexto ambigua (CFG), es posible que necesite un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas de CFG para producir todos los árboles de análisis sintáctico posibles. Esto eventualmente requeriría un espacio de memoria exponencial. La memorización fue explorada como una estrategia de análisis en 1991 por Peter Norvig, quien demostró que un algoritmo similar al uso de programación dinámica y conjuntos de estados en el algoritmo de Earley (1970), y tablas en el algoritmo CYK de Cocke, Younger y Kasami, podría generarse mediante la introducción de memorización automática en un analizador sintáctico descendente recursivo con retroceso simple para resolver el problema de la complejidad del tiempo exponencial. La idea básica del enfoque de Norvig es que cuando se aplica un analizador a la entrada, el resultado se almacena en un dispositivo de memoria para su posterior reutilización si el mismo analizador se vuelve a aplicar alguna vez a la misma entrada. Richard Frost también utilizó la memorización para reducir la complejidad de tiempo exponencial de los combinadores de analizadores sintácticos , que se pueden considerar como una técnica de análisis sintáctico de " retroceso descendente puramente funcional". Demostró que los combinadores de analizadores sintácticos memorizados básicos se pueden utilizar como bloques de construcción para construir analizadores sintácticos complejos como especificaciones ejecutables de CFG. Johnson y Dörre lo exploraron nuevamente en el contexto del análisis sintáctico en 1995. En 2002, Ford lo examinó en profundidad en la forma denominada análisis sintáctico packrat .

En 2007, Frost, Hafiz y Callaghan describieron un algoritmo de análisis de arriba hacia abajo que utiliza la memorización para abstenerse de cálculos redundantes para acomodar cualquier forma de CFG ambiguo en tiempo polinomial ( Θ (n 4 ) para gramáticas recursivas por la izquierda y Θ (n 3 ) para gramáticas no recursivas a la izquierda). Su algoritmo de análisis de arriba hacia abajo también requiere espacio polinomial para árboles de análisis ambiguos potencialmente exponenciales mediante 'representación compacta' y 'agrupación de ambigüedades locales'. Su representación compacta es comparable con la representación compacta de análisis de abajo hacia arriba de Tomita . Su uso de memorización no solo se limita a recuperar los resultados calculados previamente cuando un analizador se aplica a una misma posición de entrada repetidamente (lo cual es esencial para el requisito de tiempo polinomial); está especializado para realizar las siguientes tareas adicionales:

  • El proceso de memorización (que podría verse como un 'envoltorio' alrededor de cualquier ejecución del analizador) acomoda un análisis directo recursivo a la izquierda en constante crecimiento al imponer restricciones de profundidad con respecto a la longitud de entrada y la posición de entrada actual.
  • El procedimiento de 'búsqueda' de la tabla de notas del algoritmo también determina la reutilización de un resultado guardado comparando el contexto computacional del resultado guardado con el contexto actual del analizador. Esta comparación contextual es la clave para acomodar la recursividad por la izquierda indirecta (u oculta) .
  • Cuando se realiza una búsqueda exitosa en un dispositivo de memoria, en lugar de devolver el conjunto de resultados completo, el proceso solo devuelve las referencias del resultado real y, finalmente, acelera el cálculo general.
  • Durante la actualización de memotable, el proceso de memorización agrupa los resultados ambiguos (potencialmente exponenciales) y asegura el requisito de espacio polinómico.

Frost, Hafiz y Callaghan también describieron la implementación del algoritmo en PADL'08 como un conjunto de funciones de orden superior (llamadas combinadores de analizadores sintácticos ) en Haskell , que permite la construcción de especificaciones directamente ejecutables de CFG como procesadores de lenguaje. La importancia del poder de su algoritmo polinomial para acomodar 'cualquier forma de CFG ambiguo' con análisis de arriba hacia abajo es vital con respecto al análisis de sintaxis y semántica durante el procesamiento del lenguaje natural . El sitio de X-SAIGA tiene más información sobre el algoritmo y los detalles de implementación.

Si bien Norvig aumentó el poder del analizador a través de la memorización, el analizador aumentado seguía siendo tan complejo en el tiempo como el algoritmo de Earley, lo que demuestra un caso del uso de la memorización para algo más que la optimización de la velocidad. Johnson y Dörre demuestran otra aplicación de memorización no relacionada con la velocidad: el uso de memorización para retrasar la resolución de restricciones lingüísticas hasta un punto en un análisis en el que se ha acumulado suficiente información para resolver esas restricciones. Por el contrario, en la aplicación de optimización de velocidad de la memorización, Ford demostró que la memorización podía garantizar que el análisis sintáctico de las gramáticas de expresión pudiera analizar en tiempo lineal incluso aquellos lenguajes que daban como resultado un comportamiento de retroceso en el peor de los casos.

Considere la siguiente gramática : 

S → (A c) | (B d)
A → X (a|b)
B → X b
X → x [X]

(Nota de notación: En el ejemplo anterior, la producción S → (A c ) | (B d ) dice: "Una S es una A seguida de una c o una B seguida de una d ". La producción X → x [ X] dice "Una X es una x seguida de una X opcional ").

Esta gramática genera uno de los siguientes tres variantes de secuencia : XAC , XBC o XBD (donde x aquí se entiende que significa uno o más x 's .) A continuación, considerar cómo esta gramática, que se utiliza como una especificación de análisis, el efecto de la fuerza de una análisis de arriba hacia abajo, de izquierda a derecha de la cadena xxxxxbd :

La regla A reconocerá xxxxxb (al descender primero a X para reconocer una x , y nuevamente descender a X hasta que se consuman todas las x , y luego reconocer la b ), y luego volver a S , y no reconocer una c . La siguiente cláusula de S descenderá luego a B, que a su vez desciende nuevamente a X y reconoce las x por medio de muchas llamadas recursivas a X , y luego a b , y regresa a S y finalmente reconoce una d .

El concepto clave aquí es inherente a la frase desciende de nuevo en X . El proceso de mirar hacia adelante, fallar, hacer una copia de seguridad y luego volver a intentar la siguiente alternativa se conoce en el análisis como retroceso, y es principalmente el retroceso lo que presenta oportunidades para la memorización en el análisis. Considere una función RuleAcceptsSomeInput(Rule, Position, Input), donde los parámetros son los siguientes:

  • Rule es el nombre de la regla en cuestión.
  • Position es el desplazamiento que se está considerando actualmente en la entrada.
  • Input es la entrada bajo consideración.

Deje que el valor de retorno de la función RuleAcceptsSomeInputsea ​​la longitud de la entrada aceptada por Rule, o 0 si esa regla no acepta ninguna entrada en ese desplazamiento en la cadena. En un escenario de retroceso con tal memorización, el proceso de análisis es el siguiente:

Cuando la regla A desciende en X en la posición 0, se memoizes la longitud 5 contra esa posición y la regla X . Después de haber fallado en d , B entonces, en lugar de descender nuevamente a X , consulta la posición 0 contra la regla X en el motor de memorización, y se devuelve una longitud de 5, lo que evita tener que descender nuevamente a X , y continúa como si hubiera descendido a X tantas veces como antes.

En el ejemplo anterior, pueden ocurrir uno o varios descensos a X , permitiendo cadenas como xxxxxxxxxxxxxxxxbd . De hecho, puede haber cualquier número de x antes de b . Si bien la llamada a S debe descender recursivamente a X tantas veces como x haya , B nunca tendrá que descender a X en absoluto, ya que el valor de retorno de será 16 (en este caso particular). RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

Aquellos analizadores que hacen uso de predicados sintácticos también pueden memorizar los resultados de los análisis de predicados, reduciendo así construcciones como: 

S → (A)? A
A → /* some rule */

a un descenso a una .

Si un analizador genera un árbol de análisis sintáctico durante un análisis, debe memorizar no solo la longitud de la entrada que coincide en algún desplazamiento con una regla determinada, sino que también debe almacenar el subárbol generado por esa regla en ese desplazamiento en el input, ya que las llamadas posteriores a la regla por parte del analizador no descenderán y reconstruirán ese árbol. Por la misma razón, los algoritmos de analizador memorizados que generan llamadas a código externo (a veces llamado rutina de acción semántica ) cuando una regla coincide, deben usar algún esquema para garantizar que dichas reglas se invoquen en un orden predecible.

Dado que, para cualquier analizador sintáctico capaz de realizar un backtracking o predicado sintáctico, no todas las gramática necesitarán un backtracking o comprobaciones de predicado, la sobrecarga de almacenar los resultados del análisis sintáctico de cada regla contra cada desplazamiento en la entrada (y almacenar el árbol de análisis sintáctico si el proceso de análisis lo hace implícitamente) puede en realidad ralentiza un analizador. Este efecto se puede mitigar mediante la selección explícita de aquellas reglas que el analizador memorizará.

Ver también

Referencias

enlaces externos

Ejemplos de memorización en varios lenguajes de programación