¿Qué estructuras de datos se usan comúnmente para las memorias caché LRU y la ubicación rápida de objetos?

Question

Tenía la intención de implementar una HashTable para localizar objetos rápidamente, lo que es importante para mi aplicación.

Sin embargo, no me gusta la idea de escanear y posiblemente tener que bloquear toda la tabla para localizar a qué objeto se accedió por última vez. Las tablas pueden ser bastante grandes.

¿Qué estructuras de datos se usan comúnmente para superar eso?

p. Ej. Pensé que podría lanzar objetos en una FIFO así como en la memoria caché para saber qué edad tiene algo. Pero eso no va a ser compatible con un algoritmo LRU.

¿Alguna idea? ¿Cómo lo hace el calamar?

Answer 1

Las listas vinculadas son buenas para las memorias caché LRU. Para las búsquedas indexadas dentro de la lista enlazada (para mover la entrada al final utilizado más recientemente de la lista enlazada), use una HashTable. La entrada utilizada menos recientemente siempre será la última en la lista vinculada.

Answer 2

Puede encontrar esto article en la implementación de la memoria caché LRU usando contenedores STL (o una alternativa basada en boost::bimap) interesante. Con STL, básicamente utiliza una combinación de un mapa (para búsqueda rápida de valores-clave) y una lista separada de claves o iteradores en ese mapa (para un fácil mantenimiento del historial de acceso).