caching - usar - lru cache
Cuál es la diferencia entre LRU y LFU (3)
LRU es un algoritmo de desalojo de caché llamado memoria caché utilizada menos recientemente .
Mira este resource
LFU es un algoritmo de desalojo de caché denominado caché de uso menos frecuente .
Requiere tres estructuras de datos. Una de ellas es una tabla hash que se utiliza para almacenar en caché las claves / valores para que, dada una clave, podamos recuperar la entrada de la memoria caché en O (1). El segundo es una lista de doble enlace para cada frecuencia de acceso. La frecuencia máxima está limitada al tamaño de la memoria caché para evitar la creación de más y más entradas de la lista de frecuencias. Si tenemos un caché de tamaño máximo 4, terminaremos con 4 frecuencias diferentes. Cada frecuencia tendrá una lista de doble enlace para realizar un seguimiento de las entradas de caché que pertenecen a esa frecuencia particular. La tercera estructura de datos sería vincular de algún modo estas listas de frecuencias. Puede ser una matriz u otra lista vinculada para que al acceder a una entrada de la memoria caché pueda promoverse fácilmente a la siguiente lista de frecuencias en el tiempo O (1).
¿Cuál es la diferencia entre las implementaciones de caché LRU y LFU ?
Sé que LRU se puede implementar usando LinkedHashMap . Pero, ¿cómo implementar el caché LFU?
Consideremos un flujo constante de solicitudes de caché con una capacidad de caché de 3, ver a continuación:
A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D
Si solo consideramos un caché Usado Menos Recientemente (LRU) con una implementación de lista doblemente enlazada HashMap + con O (1) tiempo de expulsión y O (1) tiempo de carga, tendremos los siguientes elementos en caché mientras procesamos las solicitudes de caché como se mencionó anteriormente .
[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better!
Cuando observa este ejemplo, puede ver fácilmente que podemos hacerlo mejor, dada la mayor probabilidad esperada de solicitar una A en el futuro, no deberíamos desalojarla aunque se haya utilizado recientemente.
A - 12
B - 2
C - 2
D - 1
La memoria caché de uso menos frecuente (LFU) aprovecha esta información al hacer un seguimiento de cuántas veces se ha utilizado la solicitud de memoria caché en su algoritmo de desalojo.
La principal diferencia es que en LRU solo verificamos qué página es la que se utilizó recientemente en el tiempo anterior a otras páginas, es decir, que solo se verifica en función de las páginas usadas recientemente. PERO en LFU revisamos la página anterior así como la frecuencia de esa página y si la frecuencia de la página es mayor que la página anterior no podemos eliminarla y si todas las páginas antiguas tienen la misma frecuencia, entonces tome el último, es decir, el método FIFO para esa . y eliminar la página ...