Hispanopedia Wiki
Articulo de referencia

Memorización

En informática , la memorización es una técnica de optimización que se utiliza principalmente para acelerar los programas . Funciona almacenando los resultados de llamadas costo...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , la memorización es una técnica de optimización que se utiliza principalmente para acelerar los programas . Funciona almacenando los resultados de llamadas costosas a funciones puras , de modo que estos resultados puedan devolverse rápidamente si se repiten las mismas entradas. Es un tipo de almacenamiento en caché , normalmente implementado mediante una tabla hash , y un ejemplo típico de compensación espacio-tiempo , donde el tiempo de ejecución de un programa se reduce aumentando su uso de memoria. La memorización puede implementarse en cualquier lenguaje de programación, aunque algunos lenguajes tienen soporte integrado que facilita al programador memorizar una función, y otros memorizan ciertas funciones por defecto.

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 simple . [ 1 ] 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 memoización fue acuñado por Donald Michie en 1968 [ 3 ] y deriva de la palabra latina memorandum ('para ser recordado'), generalmente abreviada 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 la memoización puede confundirse con la memorización (porque son cognados etimológicos ), la memoización tiene un significado especializado en informática.

Descripción general

Una función memorizada, al ser llamada por primera vez con un conjunto dado de entradas, almacena las entradas junto con los resultados calculados. En llamadas posteriores con entradas recordadas, la función devuelve los resultados recordados en lugar de recalcularlos, eliminando así el costo de un recálculo. 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 solo 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 excepciones especiales a esta restricción). Si bien está relacionada 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, en lugar de necesitar que se proporcionen por adelantado.

Las funciones memorizadas están optimizadas para la velocidad a cambio de un mayor uso del espacio de memoria del ordenador . El "coste" 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 tiempo en ejecutarse) y en el espacio .

Aunque se produce una compensación espacio-tiempo (es decir, el espacio utilizado se traduce en una mayor velocidad), esto difiere de otras optimizaciones que implican dicha compensación, como la reducción de la fuerza , ya que la memorización es una optimización en tiempo de ejecución, no en tiempo de compilación . Además, la reducción de la fuerza puede reemplazar una operación costosa, como la multiplicación, por una menos costosa, como la suma, y ​​los resultados en ahorro pueden depender en gran medida de la máquina (no son 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 en 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 Devuelve factorial( n – 1) veces n [ invoca recursivamente factorial con el parámetro 1 menor que n ] fin si funció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 sin memorización 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:

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

En una implementación sin memorización, 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 presenta 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) veces n [ invocar recursivamente factorial con el parámetro 1 menor que n ] Almacenar x en la tabla de búsqueda en la posición n [ recordar el resultado de n! para más adelante ]. devolver x fin si función final

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

Un ejemplo extremo de memorización es el patrón Singleton , específicamente la implementación de su función getter: una función que crea un objeto en la primera invocación, almacena en caché la instancia y devuelve el mismo objeto en todas las invocaciones posteriores.

Otras consideraciones

Programación funcional

La memorización se utiliza ampliamente en los compiladores de lenguajes de programación funcional , que suelen emplear la estrategia de evaluación por nombre . Para evitar la sobrecarga que supone el cálculo de los valores de los argumentos, los compiladores de estos lenguajes utilizan intensivamente funciones auxiliares llamadas thunks para calcular dichos valores, y memorizan estas funciones para evitar cálculos repetidos.

Memorización automática

Si bien la memorización puede agregarse a las funciones de forma interna y explícita por un programador informático de manera muy similar a como factorialse implementa la versión memorizada anterior, 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 ]

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 de parámetros dado. La función que realiza este reemplazo de valor por objeto 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 llamada memorizada ( F es un parámetro de objeto de función) Si F no tiene valores de matriz adjuntos, entonces asignar un array asociativo llamado valores ; asignar valores a F ; fin si; Si F.values [arguments] está vacío , entonces F.values [ arguments] = F (arguments); fin si; devolver F. valores[argumentos] ; función final

Para llamar a una versión memorizada automáticamente factorialusando la estrategia anterior, en lugar de llamar factorialdirectamente, el código invoca . Cada llamada de este tipo primero verifica si se ha asignado un array contenedor para almacenar los resultados y, si no, adjunta ese array. Si no existe ninguna entrada en la posición (donde se usan como clave del array asociativo), se realiza una llamada real a con los argumentos proporcionados. Finalmente, la entrada en el array en la posición de la clave se devuelve a quien realizó la llamada.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 implícitamente mediante una fábrica de functores que devuelve un objeto de función memorizada envuelto en un patrón decorador . En pseudocódigo, esto se puede expresar de la siguiente manera:

función constructor-memoizado-functor ( F es un parámetro de objeto de función) asignar un objeto de función llamado versión memorizada ; sea ​​la versión memorizada(argumentos) Si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ]. asignar un array asociativo llamado valores ; adjuntar valores a sí mismo ; fin si; Si self.values [arguments] está vacío, entonces self.values [argumentos] = F (argumentos); fin si; devolver self.valores [argumentos] ; fin de dejar; devolver versión memorizada ; función final

En lugar de llamar a , se crea factorialun nuevo objeto de función de la siguiente manera:memfact

memfact = constructor-functor-memoizado(factorial)

El ejemplo anterior asume que la función factorialya ha sido definida antes de que se realice la llamada construct-memoized-functor. A partir de este momento, se llama a siempre que se desee calcular 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 = constructor-functor-memoizado(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 la recursión infinita ), como se ilustra a continuación:

función constructor-memoizado-functor ( F es un parámetro de objeto de función) asignar un objeto de función llamado versión memorizada ; sea ​​la versión memorizada (argumentos) Si self no tiene valores de matriz adjuntos, entonces [ self es una referencia a este objeto ]. asignar un array asociativo llamado valores ; adjuntar 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 ]alias propio = 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; devolver self.valores [argumentos] ; fin de dejar; devolver versión memorizada ; función final

(Nota: Algunos de los pasos mostrados anteriormente pueden ser gestionados implícitamente por el lenguaje de implementación y se proporcionan a modo de ilustración).

analizadores sintácticos

Cuando un analizador descendente intenta analizar una entrada ambigua con respecto a una gramática libre de contexto (GLC) ambigua, puede necesitar un número exponencial de pasos (con respecto a la longitud de la entrada) para probar todas las alternativas de la GLC y 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 generarse introduciendo la memorización automática en un analizador descendente recursivo simple con retroceso 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 , describiendo el resultado como un procesador de lenguaje de retroceso descendente puramente funcional basado en memorización. [ 7 ] Frost demostró que los combinadores de analizadores memorizados básicos pueden usarse como bloques de construcción para construir analizadores 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 con considerable profundidad por Bryan Ford en la forma denominada análisis sintáctico packrat . [ 12 ]

En 2007, Frost, Hafiz y Callaghan describieron un algoritmo de análisis sintáctico descendente que utiliza memorización para evitar cálculos redundantes y así acomodar cualquier forma de CFG ambigua en tiempo polinomial ( Θ (n 4 ) para gramáticas recursivas izquierdas y Θ(n 3 ) para gramáticas no recursivas izquierdas). Su algoritmo de análisis sintáctico descendente también requiere espacio polinomial para árboles de análisis sintáctico potencialmente exponenciales ambiguos mediante la "representación compacta" y la "agrupación de ambigüedades locales". Su representación compacta es comparable con la representación compacta de análisis sintáctico ascendente de Tomita . [ 13 ] Su uso de memorización no se limita solo a recuperar los resultados calculados previamente cuando se aplica un analizador sintáctico a la 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 considerarse como una "envoltura" alrededor de cualquier ejecución del analizador sintáctico) permite un análisis sintáctico recursivo izquierdo directo cada vez mayor al imponer restricciones de profundidad con respecto a la longitud de la entrada y la posición actual de la entrada.
  • El procedimiento de búsqueda en la tabla de notas del algoritmo también determina la reutilización de un resultado guardado comparando el contexto computacional de dicho resultado con el contexto actual del analizador. Esta comparación contextual es clave para admitir la recursión izquierda indirecta (u oculta) .
  • Al realizar una búsqueda exitosa en una tabla en memoria, en lugar de devolver el conjunto completo de resultados, el proceso solo devuelve las referencias del resultado real y, en consecuencia, acelera el cálculo general.
  • Durante la actualización de la tabla de memorización, el proceso de memorización agrupa los resultados ambiguos (potencialmente exponenciales) y garantiza el cumplimiento del requisito de espacio polinomial.

Frost, Hafiz y Callaghan también describieron la implementación del algoritmo en PADL'08 como un conjunto de funciones de orden superior (denominadas combinadores de analizadores ) en Haskell , lo que permite la construcción de especificaciones directamente ejecutables de gramáticas libres de contexto (GLC) como procesadores de lenguaje. La importancia de la capacidad de su algoritmo polinomial para adaptarse a "cualquier forma de GLC ambigua" con análisis descendente es vital para el análisis sintáctico y semántico durante el procesamiento del lenguaje natural . El sitio web de X-SAIGA ofrece más información sobre el algoritmo y los detalles de su implementación.

Si bien Norvig aumentó la potencia del analizador sintáctico mediante la memorización, el analizador aumentado seguía siendo tan complejo en tiempo como el algoritmo de Earley, lo que demuestra un caso del uso de la memorización para algo distinto a la optimización de la velocidad. Johnson y Dörre [ 11 ] demuestran otra aplicación de la memorización no relacionada con la velocidad: su uso para retrasar la resolución de restricciones lingüísticas hasta un punto en el análisis sintáctico donde se ha acumulado suficiente información para resolver dichas 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 de análisis sintáctico pudieran analizar en tiempo lineal incluso aquellos lenguajes 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 cadena : xac , xbc o xbd (donde x aquí se entiende que significa una o más x 's ). A continuación, consideremos cómo esta gramática, utilizada como especificación de análisis sintáctico, podría afectar un análisis sintáctico de arriba hacia abajo y de izquierda a derecha de la cadena xxxxxbd :

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

El concepto clave aquí es inherente a la frase « vuelve a descender 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 lo que presenta oportunidades para la memorización en el análisis sintáctico. Consideremos una función RuleAcceptsSomeInput(Rule, Position, Input), cuyos parámetros son los siguientes:

  • Rulees el nombre de la regla que se está considerando.
  • Positiones el desplazamiento que se está considerando actualmente en la entrada.
  • Inputes el dato de entrada que se está considerando.

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 de la cadena. En un escenario de retroceso con dicha memorización, el proceso de análisis es el siguiente:

Cuando la regla A desciende a X en el desplazamiento 0, memoriza la longitud 5 contra esa posición y la regla X. Después de haber fallado en d , B , en lugar de descender de nuevo 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, evitando así tener que descender realmente de nuevo 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 , lo que permite cadenas como xxxxxxxxxxxxxxxxbd . De hecho , puede haber cualquier número de x antes de la b . Mientras que la llamada a S debe descender recursivamente a X tantas veces como x haya , B nunca tendrá que descender a X, ya que el valor de retorno será 16 (en este caso particular) .RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

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

S → (A)? A A → /* alguna regla */

a un descenso en A.

Si un analizador sintáctico construye un árbol de análisis durante el proceso, debe memorizar no solo la longitud de la entrada que coincide con una regla determinada en una posición específica, sino también el subárbol generado por dicha regla en esa posición. Esto se debe a que las llamadas posteriores del analizador a la regla no reconstruirán el árbol. Por la misma razón, los algoritmos de análisis sintáctico con memorización que generan llamadas a código externo (a veces denominado rutina de acción semántica ) cuando se encuentra una coincidencia con una regla deben utilizar algún mecanismo para garantizar que dichas reglas se invoquen en un orden predecible.

Dado que, para cualquier analizador sintáctico con capacidad de retroceso o de predicado sintáctico, no todas las gramáticas requerirán retroceso o comprobaciones de predicados, la sobrecarga de almacenar los resultados del análisis de cada regla en relación con cada desplazamiento en la entrada (y almacenar el árbol de análisis si el proceso de análisis lo hace implícitamente) puede ralentizar el analizador. Este efecto puede mitigarse mediante la selección explícita de las reglas que el analizador memorizará. [ 14 ]

Véase también

Referencias

  1. 1 2 3 Norvig, Peter (1991). "Técnicas para la memorización automática con aplicaciones al análisis sintáctico libre de contexto" . Lingüística Computacional . 17 (1): 91– 98.
  2. ↑ Warren, David S. (1992-03-01). "Memoing para programas lógicos" . Communications of the ACM . 35 (3): 93– 111. doi : 10.1145/131295.131299 . ISSN 0001-0782 . 
  3. ↑ Michie, Donald (1968) .Funciones de 'memoria' y aprendizaje automático" (PDF) . Nature . 218 (5136): 19– 22. Bibcode : 1968Natur.218...19M . doi : 10.1038/218019a0 . S2CID 4265138 . 
  4. ↑ Hoffman, Berthold (1992). «Reescritura de términos con compartición y memorización». En Kirchner, H.; Levi, G. (eds.). Programación algebraica y lógica: Tercera Conferencia Internacional, Actas, Volterra, Italia, 2-4 de septiembre de 1992. Lecture Notes in Computer Science. Vol. 632. Berlín: Springer. pp. 128-142 . doi : 10.1007/BFb0013824 . ISBN   978-3-540-55873-6.
  5. ↑ 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 undécima 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 . 
  6. ↑ «Bricolage: Memorización» .
  7. ↑ Frost, Richard; Szydlowski, Barbara (1996). "Memoización de procesadores de lenguaje puramente funcionales de retroceso descendente" . Sci. Comput. Program . 27 (3): 263– 288. doi : 10.1016/0167-6423(96)00014-7 .
  8. ↑ Frost, Richard (1994). "Uso de la memorización para lograr una complejidad polinomial de las especificaciones ejecutables puramente funcionales de analizadores sintácticos descendentes no deterministas". SIGPLAN Notices . 29 (4): 23– 30. doi : 10.1145/181761.181764 . S2CID 10616505 . 
  9. ↑ Frost, Richard (2003). "Memorización monádica hacia la reducción de búsqueda que preserva la corrección". Conferencia canadiense sobre IA 2003. Notas de clase en ciencias de la computación. Vol. 2671. págs. 66–80 . doi : 10.1007/3-540-44886-1_8 . ISBN   978-3-540-40300-5.
  10. ↑ Johnson, Mark (1995). "Memoización del análisis sintáctico descendente". Lingüística computacional . 21 (3): 405– 417. arXiv : cmp-lg/9504016 . Bibcode : 1995cmp.lg....4016J .
  11. 1 2 Johnson, Mark y Dörre, Jochen (1995). "Memoización de restricciones corrutinadas". Actas de la 33.ª Reunión Anual de la Asociación de Lingüística Computacional . Cambridge, Massachusetts. arXiv : cmp-lg/9504028 .{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  12. 1 2 Ford, Bryan (2002). Packrat Parsing: un algoritmo práctico de tiempo lineal con retroceso (tesis de maestría). Instituto Tecnológico de Massachusetts. hdl : 1721.1/87310 .
  13. ↑ Tomita, Masaru (1985). Análisis sintáctico eficiente para el lenguaje natural . Boston: Kluwer. ISBN 0-89838-202-5.
  14. ↑ Acar, Umut A.; et al. (2003). "Selective Memoization". Actas del 30.º Simposio ACM SIGPLAN-SIGACT sobre Principios de Lenguajes de Programación, 15-17 de enero de 2003. Vol. 38. Nueva Orleans, Luisiana. pp. 14-25 . arXiv : 1106.0447 . doi : 10.1145/640128.604133 .   {{cite book}}: |journal=ignorado ( ayuda ) CS1 mantenimiento: falta el editor de ubicación ( enlace )
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 memorización en Common Lisp .
  • IncPy : un intérprete de Python personalizado que realiza la memorización automática (sin necesidad de anotaciones por parte del usuario).
  • Macros de Dave Herman para definir procedimientos memorizados en Racket .
  • Memoize.pm : un módulo de Perl que implementa funciones memorizadas.
  • Memorización en Java : un ejemplo en Java que utiliza clases proxy dinámicas para crear un patrón de memorización genérico. (Versión archivada de http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html ).
  • memoization.java - Una biblioteca de memorización para Java.
  • C++Memo – Un marco de trabajo para la memorización en C++ .
  • C-Memo : biblioteca genérica de memorización para C, implementada mediante macros de envoltura de funciones del preprocesador.
  • Tek271 Memoizer : un memorizador Java de código abierto que utiliza anotaciones e implementaciones de caché conectables.
  • memoizable : una gema de Ruby que implementa métodos memorizados.
  • Memorización en Python : un ejemplo de memorización en Python .
  • Memorización de OCaml : implementada como una extensión de sintaxis de Camlp4 .
  • Memorización en Lua : dos ejemplos de implementación 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 : extendiendo el 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 un mecanismo de almacenamiento en caché propio y la biblioteca YUI.
  • X-SAIGA – Especificaciones ejecutables de gramáticas. Contiene publicaciones relacionadas con el algoritmo de análisis sintáctico descendente que admite recursión izquierda y ambigüedad en tiempo y espacio polinomiales.
  • Memorización en Scheme : un ejemplo de memorización en Scheme aplicado a la página web de una clase.
  • Memorización en lógica combinatoria : un servicio web para reducir la lógica combinatoria memorizando cada paso en una base de datos.
  • MbCache – Resultados del método de caché en .NET .