En informática , la memorización o memoización es una técnica de optimización utilizada principalmente para acelerar los programas informáticos almacenando los resultados de llamadas de función costosas a funciones puras y devolviendo el resultado en caché cuando se vuelven a producir las mismas entradas. La memorización también se ha utilizado en otros contextos (y para fines distintos a las ganancias de velocidad), como en el análisis sintáctico descendente recursivo mutuo simple. [1] Es un tipo de almacenamiento en caché , distinto de otras formas de almacenamiento en caché, como el almacenamiento en búfer y el reemplazo de página . En el contexto de algunos lenguajes de programación lógica , la memorización también se conoce como tabulación . [2]
El término memoización fue acuñado por Donald Michie en 1968 [3] y se deriva de la palabra latina memorandum ('ser recordado'), generalmente truncada como memo en inglés americano, y por lo tanto conlleva el significado de 'convertir [los resultados de] una función en algo para ser recordado'. Si bien memoización puede confundirse con memorización (porque son cognados etimológicos ), memoización tiene un significado especializado en informática.
Una función memorizada "recuerda" los resultados correspondientes a un conjunto de entradas específicas. Las llamadas posteriores con entradas recordadas devuelven el resultado recordado en lugar de recalcularlo, eliminando así el costo primario de una llamada con parámetros dados de todas las llamadas a la función con esos parámetros, excepto la primera. 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á relacionada con las tablas de búsqueda , dado que la memorización a menudo usa dichas tablas en su implementación, la memorización llena su caché de resultados de manera transparente sobre la marcha, según sea necesario, en lugar de hacerlo por adelantado.
Las funciones memorizadas se optimizan para lograr 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 informática: complejidad computacional . Todas las funciones tienen una complejidad computacional en el tiempo (es decir, tardan en ejecutarse) y en el espacio .
Aunque se produce un equilibrio entre espacio y tiempo (es decir, el espacio utilizado es velocidad ganada), esto difiere de algunas otras optimizaciones que implican un equilibrio entre tiempo y espacio, como la reducción de fuerza , en que la memorización es una optimización en tiempo de ejecución en lugar de tiempo de compilación . Además, la reducción de fuerza potencialmente reemplaza una operación costosa como la multiplicación con una operación menos costosa como la suma, y los resultados en ahorros pueden depender en gran medida de la máquina (no ser portables entre máquinas), mientras que la memorización es una estrategia más independiente de la máquina y multiplataforma .
Considere la siguiente función de pseudocódigo para calcular el factorial de n :
función factorial ( n es un entero no negativo) Si n es 0 entonces devuelve 1 [ por la convención de que 0! = 1 ] demás devuelve factorial( n – 1) veces n [ invoca recursivamente factorial con el parámetro 1 menor que n ] terminar sifunción final
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 a x siempre se le asignará el valor 6. La implementación no memorizada anterior, dada la naturaleza del algoritmo recursivo involucrado, requeriría n + 1 invocaciones de factorialpara llegar a un resultado, y cada una de estas invocaciones, a su vez, tiene un costo asociado en el tiempo que tarda la función en devolver el valor calculado. Dependiendo de la máquina, este costo podría ser la suma de:
factorialpor n .En una implementación no memorizada, cada llamada de nivel superior 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:
función factorial ( n es un entero no negativo) Si n es 0 entonces devuelve 1 [ por la convención de que 0! = 1 ] De lo contrario, si n está en la tabla de búsqueda , entonces devolver valor de tabla de búsqueda para n demás sea x = factorial(n – 1) veces n [ invocar recursivamente factorial con el parámetro 1 menor que n ] Almacene x en la tabla de búsqueda en la ranura n [ ¡recuerde el resultado de n! para más tarde ] devolver x terminar sifunción final
En este ejemplo en particular, si factorialprimero se invoca con 5 y luego con cualquier valor menor o igual a cinco, esos valores de retorno también se habrán memorizado, ya que factorialse habrá llamado recursivamente con los valores 5, 4, 3, 2, 1 y 0, y se habrán almacenado los valores de retorno 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 términos de tiempo cuanto más a menudo se la llama, lo que resulta en una aceleración general eventual.
La memorización se utiliza mucho en compiladores para lenguajes de programación funcional , que suelen utilizar la estrategia de evaluación de llamada por nombre . Para evitar la sobrecarga con el cálculo de valores de argumentos, los compiladores para estos lenguajes utilizan con frecuencia funciones auxiliares llamadas thunks para calcular los valores de los argumentos y memorizan estas funciones para evitar cálculos repetidos.
Si bien un programador informático puede añadir memorización a funciones de forma interna y explícita de la misma forma en que se implementa la versión memorizada de antes, las funciones referencialmente transparentes también pueden memorizarse automáticamente de forma externa . [1] 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 [4] y la inteligencia artificial . [5]factorial
En los lenguajes de programación donde las funciones son objetos de primera clase (como Lua , Python o Perl [6] ), 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 objeto de función puede encapsular de manera genérica cualquier función referencialmente transparente. Considere el siguiente pseudocódigo (donde se supone que las funciones son valores de primera clase):
función llamada memorizada ( F es un parámetro del objeto de función) Si F no tiene valores de matriz adjuntos , entonces asignar una matriz asociativa llamada valores ; asignar valores a F ; fin si; si F . valores[argumentos] está vacío entonces F . valores[argumentos] = F (argumentos); fin si; devuelve F. valores[argumentos] ;función final
Para llamar a una versión memorizada automáticamente de factorialla 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 almacenamiento para almacenar resultados y, si no es así, 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 suministrados. Finalmente, la entrada en la matriz en la posición de la clave se devuelve al llamador.memoized-call(factorial(n))values[arguments]argumentsfactorial
La estrategia anterior requiere un envoltorio explícito en cada llamada a una función que se va a memorizar. En aquellos lenguajes que permiten cierres , la memorización se puede efectuar de manera implícita a través de una fábrica de funciones que devuelve un objeto de función memorizado envuelto en un patrón de decorador . En pseudocódigo, esto se puede expresar de la siguiente manera:
función construct-memoized-functor ( F es un parámetro del objeto de función) asignar un objeto de función llamado memoized-version ; deje que la versión memorizada (argumentos) sea Si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ] asignar una matriz asociativa llamada valores ; atribuye valores a sí mismo ; fin si; Si self.values [arguments] está vacío entonces self.values [argumentos] = F (argumentos); fin si; devuelve self.values [argumentos] ; fin dejar; devolver versión memorizada ;función final
En lugar de llamar , se crea factorialun nuevo objeto de función de la siguiente manera:memfact
memfact = función-memoizada-construcción(factorial)
El ejemplo anterior supone que la función factorialya se ha definido antes de que se realice la llamada a construct-memoized-functor. A partir de este punto, se llama a n siempre que se desee obtener 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 = functor-memorizado-constructo(factorial)
Básicamente, estas técnicas implican adjuntar el objeto de función original al functor creado y reenviar las llamadas a la función original que se está memorizando a través de un alias cuando se requiere una llamada a la función real (para evitar una recursión sin fin ), como se ilustra a continuación:
función construct-memoized-functor ( F es un parámetro del objeto de función) asignar un objeto de función llamado memoized-version ; deje que la versión memorizada (argumentos) sea Si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ] asignar una matriz asociativa llamada valores ; atribuye valores a sí mismo ; asignar un nuevo objeto de función llamado alias ; adjuntar alias a sí mismo ; [ para poder invocar F indirectamente más adelante ]yo mismo.alias = F ; fin si; Si self.values [arguments] está vacío entonces self.values [arguments] = self.alias (arguments); [ no es una llamada directa a F ] fin si; devuelve self.values [argumentos] ; fin dejar; devolver versión memorizada ;función final
(Nota: algunos de los pasos que se muestran arriba pueden ser administrados implícitamente por el lenguaje de implementación y se proporcionan con fines ilustrativos).
Cuando un analizador de arriba hacia abajo intenta analizar una entrada ambigua con respecto a una gramática libre de contexto (CFG) ambigua, puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas de la CFG con el fin de producir todos los árboles de análisis posibles. Esto eventualmente requeriría 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 la memorización automática a un analizador de descenso recursivo simple con seguimiento hacia atrás para resolver el problema de la complejidad temporal exponencial. [1] La idea básica en el enfoque de Norvig es que cuando se aplica un analizador a la entrada, el resultado se almacena en una tabla de memorización para su posterior reutilización si el mismo analizador se vuelve a aplicar a la misma entrada.
Richard Frost y Barbara Szydlowski también utilizaron la memorización para reducir la complejidad temporal exponencial de los combinadores de analizadores sintácticos , describiendo el resultado como un procesador de lenguaje de arriba hacia abajo con seguimiento hacia atrás puramente funcional y memorizador. [7] Frost 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. [8] [9]
La memorización fue explorada nuevamente en el contexto del análisis sintáctico en 1995 por Mark Johnson y Jochen Dörre. [10] [11] En 2002, fue examinada en considerable profundidad por Bryan Ford en la forma llamada análisis sintáctico packrat . [12]
En 2007, Frost, Hafiz y Callaghan [ cita requerida ] describieron un algoritmo de análisis de arriba hacia abajo que utiliza la memorización para evitar 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 por 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 Tomita del análisis de abajo hacia arriba . [13] Su uso de la memorización no solo se limita a recuperar los resultados calculados previamente cuando se aplica un analizador 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:
Frost, Hafiz y Callaghan también describieron la implementación del algoritmo en PADL'08 [ cita requerida ] como un conjunto de funciones de orden superior (llamadas combinadores de analizadores sintácticos ) en Haskell , lo que permite la construcción de especificaciones directamente ejecutables de CFG como procesadores de lenguaje. La importancia de la capacidad 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 X-SAIGA tiene más información sobre el algoritmo y los detalles de implementación.
Si bien Norvig aumentó la potencia del analizador sintáctico mediante la memorización, el analizador sintáctico mejorado seguía siendo tan complejo en términos de 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 [11] demuestran otra aplicación de la memorización no relacionada con la velocidad: el uso de la memorización para retrasar la resolución de restricciones lingüísticas hasta un punto en un análisis sintáctico en el que se haya acumulado suficiente información para resolver esas restricciones. Por el contrario, en la aplicación de la memorización para la optimización de la velocidad, Ford demostró que la memorización podía garantizar que las gramáticas de expresiones analizadas pudieran analizar en tiempo lineal incluso aquellos idiomas que resultaban en un comportamiento de retroceso en el peor de los casos. [12]
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 ) se lee: "Una S es una A seguida de una c o una B seguida de una d ". La producción X → x [X] se lee "Una X es una x seguida de una X opcional ".
Esta gramática genera una de las siguientes tres variaciones de la cadena : xac , xbc o xbd (donde x aquí se entiende que significa una o más x ) . A continuación, considere cómo esta gramática, utilizada como una especificación de análisis, podría efectuar un análisis de arriba hacia abajo, de izquierda a derecha, de la cadena xxxxxbd :
El concepto clave aquí es inherente a la frase " de nuevo desciende a X" . El proceso de mirar hacia adelante, fallar, retroceder y luego volver a intentar la siguiente alternativa se conoce en el análisis sintáctico como retroceso, y es principalmente el retroceso el que presenta oportunidades para la memorización en el análisis sintáctico. Considere una función RuleAcceptsSomeInput(Rule, Position, Input), donde los parámetros son los siguientes:
Rulees el nombre de la regla en consideración.Positiones el desplazamiento que se está considerando actualmente en la entrada.Inputes la entrada bajo consideración.Sea el valor de retorno de la función RuleAcceptsSomeInputla 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 dicha memorización, el proceso de análisis es el siguiente:
En el ejemplo anterior, pueden ocurrir uno o muchos descensos a X , lo que permite cadenas como xxxxxxxxxxxxxxxxbd . De hecho, puede haber cualquier cantidad 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)
Los analizadores que utilizan predicados sintácticos también pueden memorizar los resultados de los análisis de predicados, reduciendo así construcciones como:
S → (A)? AA → /* alguna regla */
a un descenso hacia A.
Si un analizador construye un árbol de análisis durante un análisis, debe memorizar no solo la longitud de la entrada que coincide en algún desplazamiento con una regla dada, sino que también debe almacenar el subárbol generado por esa regla en ese desplazamiento en la entrada, 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 llamados 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 con capacidad de retroceder o de realizar verificaciones de predicados sintácticos, no todas las gramáticas necesitarán retroceder o realizar verificaciones de predicados, la sobrecarga de almacenar los resultados del análisis de cada regla en cada desplazamiento de la entrada (y almacenar el árbol de análisis si el proceso de análisis lo hace implícitamente) puede, en realidad, ralentizar el analizador. Este efecto se puede mitigar mediante la selección explícita de aquellas reglas que el analizador memorizará. [14]
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ){{cite book}}: |journal=ignorado ( ayuda )Mantenimiento de CS1: falta la ubicación del editor ( enlace )