¿Cuál es la diferencia entre almacenamiento en caché y memorización?

114

Me gustaría saber cuál es la diferencia real entre cachingy memoization.
Como yo lo veo, ambos implican evitar llamadas de función repetidas para obtener datos almacenándolos .

¿Cuál es la principal diferencia entre los dos?

Juan
fuente
Me pregunto si podría decir "la memorización es almacenar en caché" como "la matriz es una matriz dispersa". En otras palabras, solo almacena cosas "a pedido" en lugar de enumerar todas las combinaciones de entrada posibles.
Sridhar Sarnobat

Respuestas:

110

La memorización es una forma específica de almacenamiento en caché que implica almacenar en caché el valor de retorno de una función en función de sus parámetros .

El almacenamiento en caché es un término más general; por ejemplo, el almacenamiento en caché HTTP es almacenamiento en caché pero no memorización.

Wikipedia dice :

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.

SLaks
fuente
2
pero siempre puede rodear la parte donde se usa el caché con una función y bautizarla como 'memorización'. aunque la diferencia es que usted tiene el control de la política de almacenamiento en caché en su función, mientras que la memorización es de orden superior y ocurre fuera de la función, supongo.
nicolas
¿Por qué HTTP Caching no es una memorización? que también se basa en el parámetro (la URL del recurso solicitado).
topo Reinstate Monica
@topomorto: Por características como If-Matchy vencimientos. La memorización solo tiene sentido para la función pura, lo que HTTP rara vez lo es.
SLaks
@nicolas, no del todo, creo. Creo que en la memorización el término "función" se usa en un sentido matemático puro. La descarga de una página web desde una dirección determinada no puede considerarse una función, porque puede suceder que la página cambie.
Alexey
@Alexey, ¿no se aplica el mismo comentario al almacenamiento en caché? todas esas estrategias se basan en la misma llamada de función que da el mismo resultado, también conocido como ningún efecto secundario ascendente .
nicolas
47

Como los he visto usados, "memorización" es "almacenar en caché el resultado de una función determinista" que se puede reproducir en cualquier momento con la misma función y entradas.

El "almacenamiento en caché" incluye básicamente cualquier estrategia de almacenamiento en búfer de salida, ya sea que el valor de origen sea reproducible o no en un momento dado. De hecho, el almacenamiento en caché también se utiliza para referirse a estrategias de almacenamiento en búfer de entrada , como la caché de escritura en un disco o memoria. Entonces es un término mucho más general.

arpón
fuente
¿Estás seguro de que la función tiene que ser determinista?
Gherman
4
@Alemán, sí, la memorización depende del determinismo. El ejemplo clásico es un algoritmo recursivo, como la secuencia de Fibonacci o factorial. En lugar de volver a calcular hasta el caso base, una función memorizada produciría un cortocircuito al reutilizar resultados anteriores para valores que ya se han calculado. Obviamente, esto depende de que la misma entrada dé siempre la misma salida, que es la definición de determinismo. El almacenamiento en caché, por otro lado, se usa con frecuencia para procesos no deterministas (por ejemplo, aleatorios o con marca de tiempo), en el entendido de que los resultados pueden no coincidir con un valor "actualizado".
harpo
6

Creo que el término almacenamiento en caché se usa generalmente cuando almacena los resultados de las operaciones de E / S, o básicamente cualquier dato que le llega desde el exterior (archivos, red, consultas de base de datos). La memorización de términos generalmente se aplica al almacenamiento de resultados de sus propios cálculos, por ejemplo, en el contexto de la programación dinámica.

MK.
fuente
1

La memorización es una forma especial de almacenar en caché el resultado de una función determinista. Esto significa que almacenar en caché el resultado fuera de la función no es memorización porque la función tendría que mutar la caché al calcular un nuevo resultado (que no esté ya en la caché) para que ya no sea una función (pura). La memorización generalmente implica pasar el caché como un argumento adicional (en una función auxiliar). La memorización optimizará las funciones que necesitan calcular valores varias veces para un solo acceso. El almacenamiento en caché optimizará las funciones que se llaman varias veces con los mismos parámetros. En otras palabras, Memoization optimizará el primer acceso si el almacenamiento en caché solo optimizará los accesos recurrentes.

Pierre-Yves Saumont
fuente
0

Me gustaría agregar a las otras excelentes respuestas que la memorización también se conoce como tabulación . Creo que también es importante conocer ese término para aquellos que aprenden qué son la memorización y el almacenamiento en caché.

VS
fuente