Rilasciato · in miglioramento
Algorithm
Una cache LRU, quando è piena, rimuove la voce inutilizzata da più tempo; hash map e lista doppiamente concatenata rendono get e put O(1).
Una cache LRU (least recently used, usata meno di recente) è una cache a capacità fissa che, quando è piena, rimuove la voce rimasta inutilizzata più a lungo. Si basa sulla località temporale, cioè sul fatto che i dati usati da poco tendono a essere riusati presto, e a differenza di FIFO aggiorna la posizione di una voce a ogni lettura. L'implementazione standard affianca una hash map, che trova il nodo di una chiave, a una lista doppiamente concatenata che mantiene l'ordine d'uso, così get e put richiedono in media O(1).
LRU compare, esatto o approssimato, in quasi ogni livello di un sistema: cache della CPU, page cache del sistema operativo, buffer pool dei database, politiche di eviction di Redis, CDN e cache dei browser. Si trova anche nelle librerie standard, come functools.lru_cache e OrderedDict in Python o LinkedHashMap in Java. Poiché unisce hash map e lista concatenata in un unico progetto, è anche una domanda classica nei colloqui di programmazione.
Inizia dalle differenze tra politiche di rimozione come FIFO, LRU, LFU e TTL e dal concetto di hit ratio, poi segui a mano una breve sequenza di richieste. Implementa quindi la cache con un dizionario e una lista doppiamente concatenata con nodi sentinella, e confrontala con le versioni di libreria come OrderedDict e LinkedHashMap. Infine affronta problemi pratici: sicurezza tra thread, invalidazione della cache e combinazione con una scadenza.
Ogni get o put riuscito sposta la voce all'estremità più recente; quando manca spazio, viene rimossa quella all'altra estremità.
La mappa trova subito il nodo di una chiave e la lista stacca e reinserisce i nodi in O(1) per mantenere l'ordine.
get e put modificano solo un numero costante di puntatori, quindi richiedono in media tempo costante; lo spazio cresce con la capacità.
I sistemi reali usano spesso CLOCK, pseudo-LRU, LRU a campionamento, 2Q o W-TinyLFU per ridurre i costi o resistere alle grandi scansioni.
Un dict associa le chiavi ai nodi e una lista doppiamente concatenata tra le sentinelle head e tail mantiene l'ordine d'uso. get sposta il nodo in testa; put rimuove il nodo subito prima di tail quando la cache è piena. Eseguendo python lru_cache.py viene rimosso "b" e si stampa 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.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Cache LRU.
Fai domande, condividi la tua esperienza e scambia opinioni su Cache LRU.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.