En informática , la memoización o memorización es una técnica de optimización que se utiliza principalmente para acelerar los programas informáticos mediante el almacenamiento de los resultados de llamadas a funciones costosas y la devolución del 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 de las ganancias de velocidad), como en el análisis de descenso recursivo mutuo simple. [1] Aunque está relacionado con el almacenamiento en caché , la memoización se refiere a un caso específico de esta optimización, distinguiéndola de formas de almacenamiento en caché como el almacenamiento en búfer o el reemplazo de página.. En el contexto de algunos lenguajes de programación lógicos , 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 " ("para ser recordado"), generalmente truncado como "memo" en inglés estadounidense, y por lo tanto tiene 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 algún conjunto de entradas específicas. Las llamadas posteriores con entradas recordadas devuelven el resultado recordado en lugar de volver a calcularlo, eliminando así el costo principal de una llamada con parámetros dados de todas menos la primera llamada realizada a la función con esos parámetros. El conjunto de asociaciones recordadas puede ser un conjunto de tamaño fijo controlado por un algoritmo de reemplazo o un conjunto fijo, según la naturaleza de la función y su uso. Una función sólo 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 memoization a menudo usa tales tablas en su implementación, memoization 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 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 de espacio-tiempo (es decir, el espacio utilizado es velocidad ganada), esto difiere de algunas otras optimizaciones que implican una compensación de 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 con una operación menos costosa como la suma, y los resultados en ahorros pueden depender en gran medida de la máquina (no portátiles entre máquinas), mientras que la memorización es una operación cruzada más independiente de la máquina . -estrategia de plataforma .
Para todo 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 uno 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 puede ser la suma de: