En informática , la memorización o memorización es una técnica de optimización que se utiliza principalmente para acelerar los programas informáticos almacenando los resultados de costosas llamadas a funciones en funciones puras y devolviendo el resultado almacenado en caché cuando se repiten las mismas entradas. La memorización también se ha utilizado en otros contextos (y para fines distintos del aumento de velocidad), como en el análisis de descenso simple y mutuamente recursivo . [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áginas . 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 memorización fue acuñado por Donald Michie en 1968 [3] y se deriva de la palabra latina memorandum ("para ser recordado"), generalmente truncada como memo en inglés americano, y por lo tanto tiene el significado de "convertir [los resultados de] una función en algo para ser recordado". Si bien la memorización puede confundirse con la memorización (porque son cognados etimológicos ), la memorización tiene un significado especializado en informática.
Una función memorizada "recuerda" los resultados correspondientes a algún conjunto de entradas específicas. Las llamadas posteriores 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 las llamadas realizadas 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, dependiendo de la naturaleza de la función y su uso. Una función sólo puede memorizarse si es referencialmente transparente ; es decir, solo si llamar a la función tiene exactamente el mismo efecto que reemplazar esa llamada a la función con su valor de retorno. (Sin embargo, existen casos especiales de excepción a esta restricción). Si bien está relacionado con las tablas de búsqueda , dado que la memorización a menudo utiliza dichas 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.
Las funciones memorizadas se optimizan para la velocidad a cambio de un mayor uso del espacio de la memoria de la computadora . El "coste" 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 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-tiempo, como la reducción de fuerza , en que la memorización es un tiempo de ejecución en lugar de un tiempo de compilación. mejoramiento. Además, la reducción de la fuerza reemplaza potencialmente una operación costosa como la multiplicación por una operación menos costosa como la suma, y los resultados en términos de ahorro pueden depender en gran medida de la máquina (no son portátiles entre máquinas), mientras que la memorización es una operación más independiente de la máquina y cruzada . -Estrategia de plataforma .
Considere la siguiente función de pseudocódigo para calcular el factorial de n :
función factorial ( n es un número entero no negativo) si n es 0 entonces devolver 1 [ por la convención de que 0! = 1 ] demás devolver factorial( n – 1) veces n [ invocar recursivamente factorial con el parámetro 1 menor que n ] terminara sifunción final
Para cada número 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 anterior no memorizada, 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, tienen un coste 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 número entero no negativo) si n es 0 entonces devolver 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) multiplicado por n [ invocar recursivamente factorial con el parámetro 1 menor que n ] almacene x en la tabla de búsqueda en la enésima ranura [ recuerde el resultado de n! Para luego ] volver x terminara sifunción final
En este ejemplo particular, si factorialprimero se invoca con 5, y luego se invoca después con cualquier valor menor o igual a cinco, esos valores de retorno también habrán sido memorizados, ya que factorialse habrán 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 por ejemplo 7, solo se realizarán 2 llamadas recursivas (7 y 6), ¡y el valor de 5! habrán sido almacenados 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.
La memorización se utiliza mucho en compiladores de lenguajes de programación funcionales , que a menudo utilizan una estrategia de evaluación de llamada por nombre . Para evitar gastos generales al calcular los valores de los argumentos, los compiladores de estos lenguajes utilizan en gran medida funciones auxiliares llamadas procesadores para calcular los valores de los argumentos y memorizan estas funciones para evitar cálculos repetidos.
Si bien un programador de computadora puede agregar memorización a funciones interna y explícitamente de la misma manera que se implementa la versión memorizada anterior, las funciones referencialmente transparentes también pueden memorizarse automáticamente externamente . [1] Las técnicas empleadas por Peter Norvig tienen aplicación no sólo 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 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 objeto de valor por función puede encapsular genéricamente cualquier función referencialmente transparente. Considere el siguiente pseudocódigo (donde se supone que las funciones son valores de primera clase):
función de llamada memorizada ( F es un parámetro de objeto de función) si F no tiene valores de matriz adjuntos , entonces asignar una matriz asociativa llamada valores ; adjuntar valores a F ; terminara si; si F. valores[argumentos] está vacío, entonces F . valores[argumentos] = F (argumentos); terminara si; devolver F. valores[argumentos] ;función final
Para llamar a una versión memorizada automáticamente del factorialuso de 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, de no ser 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 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 lenguajes que permiten cierres , la memorización se puede efectuar implícitamente a través de una fábrica de functores que devuelve un objeto de función memorizado envuelto en un patrón decorador . En pseudocódigo, esto se puede expresar de la siguiente manera:
función construct-memoized-functor ( F es un parámetro de objeto de función) asignar un objeto de función llamado versión memorizada ; dejar 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 ; atribuir valores a uno mismo ; terminara si; si yo. valores [argumentos] está vacío entonces ser. valores[argumentos] = F (argumentos); terminara si; regresar a uno mismo. valores[argumentos] ; terminar dejar; devolver la versión memorizada ;función final
En lugar de llamar , se crea factorialun nuevo objeto de función de la siguiente manera:memfact
memfact = construcción-functor-memorizado (factorial)
El ejemplo anterior supone que la función factorialya se ha definido antes deconstruct-memoized-functor realizar la llamada . A partir de este momento, se llama siempre que se desee el factorial de n . En lenguajes como Lua existen técnicas más sofisticadas que permiten sustituir una función por una nueva función con el mismo nombre, lo que permitiría:memfact(n)
factorial = constructo-functor-memorizado(factorial)
Esencialmente, dichas técnicas implican adjuntar el objeto de función original al funtor creado y reenviar 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 una recursividad interminable ), como se ilustra a continuación:
función construct-memoized-functor ( F es un parámetro de objeto de función) asignar un objeto de función llamado versión memorizada ; dejar 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 ; atribuir valores a uno mismo ; asignar un nuevo objeto de función llamado alias ; adjuntar alias a uno mismo ; [ para la capacidad posterior de invocar F indirectamente ] ser. alias = F ; terminara si; si yo. valores [argumentos] está vacío entonces ser. valores[argumentos] = yo. alias (argumentos); [ no es una llamada directa a F ] terminara si; regresar a uno mismo. valores[argumentos] ; terminar dejar; devolver la versión memorizada ;función final
(Nota: algunos de los pasos mostrados anteriormente pueden ser administrados implícitamente por el lenguaje de implementación y se proporcionan a modo de ilustración).
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. para producir todos los árboles de análisis posibles. Esto eventualmente requeriría un espacio de memoria exponencial. La memorización fue explorada como 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 se generará introduciendo la memorización automática en un analizador de descenso recursivo de retroceso simple para resolver el problema de la complejidad del tiempo 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 notas para su posterior reutilización si alguna vez se vuelve a aplicar el mismo analizador 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 , describiendo el resultado como un procesador de lenguaje de retroceso de arriba hacia abajo puramente funcional de memorización. [7] Frost demostró que los combinadores de analizadores memorizados básicos se pueden utilizar como bloques de construcción para construir analizadores complejos como especificaciones ejecutables de CFG. [8] [9]
La memorización fue nuevamente explorada en el contexto del análisis sintáctico en 1995 por Mark Johnson y Jochen Dörre. [10] [11] En 2002, Bryan Ford lo examinó en profundidad considerable en la forma llamada análisis packrat . [12]
En 2007, Frost, Hafiz y Callaghan [ cita necesaria ] 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 polinómico ( Θ (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 del análisis ascendente de Tomita . [13] Su uso de la memorización no solo se limita a recuperar los resultados calculados previamente cuando un analizador se aplica repetidamente a una misma posición de entrada (lo cual es esencial para el requisito de tiempo polinómico); está especializado para realizar las siguientes tareas adicionales:
Frost, Hafiz y Callaghan también describieron la implementación del algoritmo en PADL'08 [ cita necesaria ] como un conjunto de funciones de orden superior (llamadas combinadores de analizadores ) 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 X-SAIGA tiene más información sobre el algoritmo y los detalles de implementación.
Si bien Norvig aumentó el poder del analizador mediante la memorización, el analizador aumentado todavía era 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 [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 en el que se ha acumulado suficiente información para resolver esas restricciones. Por el contrario, en la aplicación de memorización de optimización de velocidad, Ford demostró que la memorización podía garantizar que las gramáticas de expresión de análisis pudieran analizar en tiempo lineal incluso aquellos lenguajes que resultaban en el peor comportamiento de retroceso. [12]
Considere la siguiente gramática :
S → (A c ) | ( Bd )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 una de las siguientes tres variaciones de cadena : xac , xbc o xbd (donde aquí se entiende que x significa una o más x ) . A continuación, considere cómo esta gramática, utilizada como 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 nuevamente 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 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:
Rulees el nombre de la regla bajo consideración.Positiones la compensación actualmente bajo consideración 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 varios descensos a X , lo que permite 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 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 sólo 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 entrada, ya que las llamadas posteriores a la regla por parte del analizador en realidad no descenderán ni reconstruirán ese árbol. Por la misma razón, los algoritmos de análisis 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 con capacidad de predicado sintáctico o retroceso, no todas las gramáticas necesitarán seguimiento o verificación de predicados, la sobrecarga de almacenar los resultados del análisis de cada regla contra cada desplazamiento en la entrada (y almacenar el árbol de análisis si el proceso de análisis lo hace implícitamente) puede en realidad ralentizar un analizador. Este efecto puede mitigarse mediante la selección explícita de aquellas reglas que el analizador memorizará. [14]
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ){{cite book}}: |journal=ignorado ( ayuda )Mantenimiento CS1: falta la ubicación del editor ( enlace )