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 . [1] 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 las 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 . [2]
Etimología
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 lleva el significado de " convertir [los resultados de] una función en algo para recordar ". Mientras que "memorización" puede confundirse con " memorización " (porque son cognados etimológicos ), "memorización" tiene un significado especializado en informática.
Descripción general
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 excepto la primera 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 entre el espacio y el tiempo (es decir, el espacio utilizado es la velocidad ganada), esto difiere de algunas otras optimizaciones que implican una compensación entre el tiempo y el espacio, 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 :
función factorial ( n es un número entero no negativo) si n es 0 entonces devuelve 1 [ por la convención de que 0! = 1 ] demás devuelve factorial ( n - 1) multiplicado por n [ invocar recursivamente factorial con el parámetro 1 menor que n ] terminara sifunción final
Para todo entero n tal que n ≥0 , el resultado final de la función factorial
es 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 factorial
llegar 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:
- El costo de configurar el marco de pila de llamadas funcional.
- El costo de comparar n con 0.
- El costo de restar 1 de n .
- El costo de configurar el marco de pila de llamadas recursivas. (Como anteriormente.)
- El costo de multiplicar el resultado de la llamada recursiva a
factorial
por n . - 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 factorial
incluye 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 factorial
función:
función factorial ( n es un número 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 el valor de la tabla de búsqueda para n demás sea x = factorial (n - 1) multiplicado por n [ invocar factorial de forma recursiva con el parámetro 1 menor que n ] almacenar x en la tabla de búsqueda en el n- ésimo espacio [ recuerde el resultado de n! para mas tarde ] volver x terminara sifunción final
En este ejemplo en particular, si factorial
primero 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 factorial
se 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
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 factorial
se implementa, referencialmente funciones transparentes también se pueden memoized automáticamente externamente . [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ó 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]
En lenguajes de programación donde las funciones son objetos de primera clase (como Lua , Python o Perl [1] ), 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 supone que las funciones son valores de primera clase):
función memoized-call ( 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ía, entonces F . valores [argumentos] = F (argumentos); terminara si;
devuelve F. valores [argumentos] ;función final
Para llamar a una versión memorizada automáticamente de factorial
usar la estrategia anterior, en lugar de llamar factorial
directamente, 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]
arguments
factorial
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 es un parámetro de objeto de función) asignar un objeto de función llamado memoized-version ;
deja que la versión memoizada (argumentos) sea si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ] asignar una matriz asociativa llamada valores ; adjuntar valores a uno mismo ; terminara si; si yo. los valores [argumentos] están vacíos entonces uno mismo. valores [argumentos] = F (argumentos); terminara si; volver a sí mismo. valores [argumentos] ; fin dejar;
devolver la versión memorizada ;función final
En lugar de llamar factorial
, memfact
se crea un nuevo objeto de función de la siguiente manera:
memfact = construct-memoized-functor (factorial)
El ejemplo anterior asume que la función factorial
ya se ha definido antes de que construct-memoized-functor
se 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 = constructo-functor-memorizado (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 es un parámetro de objeto de función) asignar un objeto de función llamado memoized-version ;
deja que la versión memoizada (argumentos) sea si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ] asignar una matriz asociativa llamada valores ; adjuntar valores a uno mismo ; asignar un nuevo objeto de función llamado alias ; adjuntar alias a sí mismo ; [ para la capacidad posterior de invocar a F indirectamente ] uno mismo. alias = F ; terminara si; si yo. los valores [argumentos] están vacíos entonces uno mismo. valores [argumentos] = uno mismo. alias (argumentos); [ no es una llamada directa a F ] terminara si; volver a sí mismo. valores [argumentos] ; fin dejar;
devolver la 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 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), puede necesitar 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. [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 un dispositivo de memoria para su posterior reutilización si el mismo analizador se vuelve a aplicar 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 ver como una técnica de análisis sintáctico de " retroceso descendente puramente funcional". [6] Demostró que los combinadores de analizadores sintácticos básicos memorizados se pueden utilizar como bloques de construcción para construir analizadores sintácticos complejos como especificaciones ejecutables de CFG. [7] [8] Johnson y Dörre lo exploraron nuevamente en el contexto del análisis sintáctico en 1995. [9] [10] En 2002, fue examinado en profundidad por Ford en la forma denominada parsing packrat . [11]
En 2007, Frost, Hafiz y Callaghan [ cita requerida ] 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 . [12] Su uso de memorización no solo se limita a recuperar los resultados previamente calculados 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 [ cita requerida ] como un conjunto de funciones de orden superior (llamadas combinadores de analizador ) 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 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 [10] 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. [11]
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 RuleAcceptsSomeInput
sea 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 le devuelve una longitud de 5, lo que ahorra 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)? AA → / * alguna regla * /
a un descenso a una .
Si un analizador crea 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 que genera esa regla en ese desplazamiento en el 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 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 verificaciones 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) en realidad ralentiza un analizador. Este efecto se puede mitigar mediante la selección explícita de aquellas reglas que el analizador memorizará. [13]
Ver también
- Computación aproximada : categoría de técnicas para mejorar la eficiencia
- Teoría de la complejidad computacional : más información sobre la complejidad del algoritmo
- Cadena de director : localizar rápidamente variables libres en expresiones
- Patrón de peso mosca : un patrón de diseño de programación de objetos , que también utiliza una especie de memorización
- Hashlife : una técnica de memorización para acelerar el cálculo de autómatas celulares
- Evaluación perezosa : comparte algunos conceptos con la memorización.
- Vista materializada : almacenamiento en caché análogo en consultas de base de datos
- Evaluación parcial : una técnica relacionada para la optimización automática del programa.
Referencias
- ↑ a b c Norvig, Peter (1991). "Técnicas para la memorización automática con aplicaciones para el análisis sin contexto" . Lingüística computacional . 17 (1): 91–98.
- ^ Warren, David. "Programación de Tablas y Registro de Datos" . Consultado el 29 de mayo de 2009 .
- ^ Michie, Donald (1968). " Funciones de ' Memo' y aprendizaje automático" (PDF) . Naturaleza . 218 (5136): 19-22. Código Bibliográfico : 1968Natur.218 ... 19M . doi : 10.1038 / 218019a0 . S2CID 4265138 .
- ^ Hoffman, Berthold (1992). "Término de reescritura con compartir y memoïzation". En Kirchner, H .; Levi, G. (eds.). Programación algebraica y lógica: Tercera Conferencia Internacional, Actas, Volterra, Italia, 2-4 de septiembre de 1992 . Apuntes de conferencias en informática. 632 . Berlín: Springer. págs. 128-142. doi : 10.1007 / BFb0013824 . ISBN 978-3-540-55873-6.
- ^ Mayfield, James; et al. (1995). "Uso de la memorización automática como herramienta de ingeniería de software en sistemas de IA del mundo real" (PDF) . Actas de la XI Conferencia IEEE sobre Inteligencia Artificial para Aplicaciones (CAIA '95) . págs. 87–93. doi : 10.1109 / CAIA.1995.378786 . hdl : 11603/12722 . ISBN 0-8186-7070-3. S2CID 8963326 .
- ^ Frost, Richard; Szydlowski, Barbara (1996). "Memorización de procesadores de lenguaje de retroceso de arriba hacia abajo puramente funcionales" . Sci. Computación. Programa . 27 (3): 263–288. doi : 10.1016 / 0167-6423 (96) 00014-7 .
- ^ Frost, Richard (1994). "Uso de la memorización para lograr la complejidad polinomial de las especificaciones ejecutables puramente funcionales de analizadores descendentes no deterministas". Avisos SIGPLAN . 29 (4): 23–30. doi : 10.1145 / 181761.181764 . S2CID 10616505 .
- ^ Frost, Richard (2003). "Memoización monádica hacia la reducción de la búsqueda de preservación de la corrección". Conferencia canadiense sobre IA 2003 . Apuntes de conferencias en informática. 2671 . págs. 66–80. doi : 10.1007 / 3-540-44886-1_8 . ISBN 978-3-540-40300-5.
- ^ Johnson, Mark (1995). "Memorización del análisis de arriba hacia abajo". Lingüística computacional . 21 (3): 405–417. arXiv : cmp-lg / 9504016 . Código bibliográfico : 1995cmp.lg .... 4016J .
- ^ a b Johnson, Mark y Dörre, Jochen (1995). "Memoización de restricciones de Coroutined". Actas de la 33ª Reunión Anual de la Asociación de Lingüística Computacional . Cambridge, Massachusetts. arXiv : cmp-lg / 9504028 .
- ^ a b Ford, Bryan (2002). Packrat Parsing: un algoritmo práctico de tiempo lineal con retroceso (tesis de maestría). Instituto de Tecnología de Massachusetts. hdl : 1721,1 / 87310 .
- ^ Tomita, Masaru (1985). Análisis eficiente del lenguaje natural . Boston: Kluwer. ISBN 0-89838-202-5.
- ^ Acar, Umut A .; et al. (2003). "Memorización selectiva". Actas del 30º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación, 15-17 de enero de 2003 . Avisos ACM SIGPLAN . 38 . Nueva Orleans, Louisiana. págs. 14-25. arXiv : 1106.0447 . doi : 10.1145 / 640128.604133 .
enlaces externos
- Ejemplos de memorización en varios lenguajes de programación
- groovy.lang.Closure # memoize () - Memoize es una característica del lenguaje Apache Groovy 1.8.
- Memoize : Memoize es una pequeña biblioteca, escrita por Tim Bradshaw, para realizar la memorización en Common Lisp .
- IncPy : un intérprete de Python personalizado que realiza la memorización automática (sin anotaciones de usuario necesarias)
- Macros de Dave Herman para definir procedimientos memorizados en Racket .
- Memoize.pm : un módulo de Perl que implementa funciones memorizadas.
- Memorización de Java : un ejemplo en Java que utiliza clases de proxy dinámicas para crear un patrón de memorización genérico.
- memoization.java : una biblioteca de memorización de Java.
- C ++ Memo [ enlace muerto permanente ] : un marco de trabajo de memorización de C ++ .
- C-Memo : biblioteca de memorización genérica para C, implementada utilizando macros de envoltura de funciones de preprocesador.
- Tek271 Memoizer : Memoizador de Java de código abierto que utiliza anotaciones e implementaciones de caché conectables.
- memoizable : una joya de Ruby que implementa métodos memorizados.
- Python memoization - Un pitón ejemplo de memoization.
- Memorización de OCaml : implementada como una extensión de sintaxis de Camlp4 .
- Memorización en Lua : dos implementaciones de ejemplo de una función de memorización general en Lua .
- Memorización en Mathematica - Memorización y memorización limitada en Mathematica .
- Memorización en Javascript : ampliación del prototipo de función en JavaScript (versión archivada de http://talideon.com/weblog/2005/07/javascript-memoization.cfm ).
- Memorización en Javascript : ejemplos de memorización en javascript utilizando su propio mecanismo de almacenamiento en caché y utilizando la biblioteca YUI
- X-SAIGA - ACCIONES ESPECÍFICAS EJECTABLES DE GRAMAS. Contiene publicaciones relacionadas con el algoritmo de análisis de arriba hacia abajo que admite la recursividad por la izquierda y la ambigüedad en el tiempo y el espacio polinomiales.
- Memorización en esquema : un ejemplo de esquema de memorización en la página web de una clase.
- Memorización en lógica combinatoria : un servicio web para reducir la lógica combinatoria mientras memoriza cada paso en una base de datos.
- MbCache : el método de caché da como resultado .NET .