Publicado · en mejora
Algorithm
Una caché LRU expulsa la entrada usada hace más tiempo cuando se llena; un mapa hash y una lista doblemente enlazada hacen get y put O(1).
Una caché LRU (least recently used, menos usada recientemente) es una caché de capacidad fija que, cuando se llena, expulsa la entrada que lleva más tiempo sin usarse. Se basa en la localidad temporal, es decir, en que los datos usados hace poco suelen volver a usarse pronto, y a diferencia de FIFO actualiza la posición de una entrada en cada lectura. La implementación estándar combina un mapa hash, que encuentra el nodo de cada clave, con una lista doblemente enlazada que mantiene el orden de uso, de modo que get y put tardan O(1) en promedio.
LRU aparece, exacto o aproximado, en casi todas las capas de un sistema: cachés de CPU, la caché de páginas del sistema operativo, los buffer pools de las bases de datos, las políticas de expulsión de Redis, las CDN y las cachés de los navegadores. También viene en las bibliotecas estándar, como functools.lru_cache y OrderedDict en Python o LinkedHashMap en Java. Como reúne un mapa hash y una lista enlazada en un solo diseño, es además una pregunta clásica de entrevistas de programación.
Empieza por las diferencias entre políticas de expulsión como FIFO, LRU, LFU y TTL y por el concepto de tasa de aciertos, y luego sigue a mano una secuencia corta de peticiones. Después implementa la caché tú mismo con un diccionario y una lista doblemente enlazada con nodos centinela, y compárala con versiones de biblioteca como OrderedDict y LinkedHashMap. Por último, trabaja problemas prácticos: seguridad entre hilos, invalidación de caché y combinación con tiempos de expiración.
Cada get o put con éxito mueve la entrada al extremo más reciente; cuando falta espacio, se expulsa la del otro extremo.
El mapa encuentra directamente el nodo de una clave y la lista desengancha y reinserta nodos en O(1) para mantener el orden.
get y put solo cambian un número constante de punteros, así que tardan tiempo constante en promedio; el espacio crece con la capacidad.
Los sistemas reales suelen usar CLOCK, pseudo-LRU, LRU por muestreo, 2Q o W-TinyLFU para reducir costes o resistir recorridos grandes.
Un dict asocia claves con nodos y una lista doblemente enlazada entre los centinelas head y tail guarda el orden de uso. get mueve el nodo al frente; put expulsa el nodo justo antes de tail cuando la caché está llena. Al ejecutar python lru_cache.py se expulsa "b" y se imprime None 1 3.
lru_cache.py
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> Node
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key, default=None):
node = self.map.get(key)
if node is None:
return default
self._unlink(node) # touch: move to the front
self._push_front(node)
return node.value
def put(self, key, value):
if self.capacity <= 0:
return
node = self.map.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) >= self.capacity: # evict the least recently used
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the most recent
cache.put("c", 3) # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c")) # None 1 3
python lru_cache.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Caché LRU.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Caché LRU.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.