Veröffentlicht · wird verbessert
Algorithm
Ein LRU-Cache verdrängt bei vollem Speicher den am längsten ungenutzten Eintrag; Hash-Map und doppelt verkettete Liste machen get und put O(1).
Ein LRU-Cache (Least Recently Used) ist ein Cache mit fester Kapazität, der bei vollem Speicher den Eintrag entfernt, der am längsten nicht verwendet wurde. Er stützt sich auf zeitliche Lokalität, also darauf, dass kürzlich genutzte Daten bald wieder gebraucht werden, und anders als FIFO aktualisiert er die Position eines Eintrags bei jedem Lesezugriff. Die Standardimplementierung kombiniert eine Hash-Map, die den Knoten zu einem Schlüssel findet, mit einer doppelt verketteten Liste in Nutzungsreihenfolge; so laufen get und put im Mittel in O(1).
LRU findet sich exakt oder als Näherung auf fast jeder Ebene eines Systems: in CPU-Caches, im Page Cache des Betriebssystems, in Puffer-Pools von Datenbanken, in den Verdrängungsstrategien von Redis, in CDNs und Browser-Caches. Auch Standardbibliotheken bringen es mit, etwa functools.lru_cache und OrderedDict in Python oder LinkedHashMap in Java. Weil es Hash-Map und verkettete Liste in einem Entwurf verbindet, ist es zudem eine klassische Aufgabe in Programmierinterviews.
Beginnen Sie mit den Unterschieden zwischen Verdrängungsstrategien wie FIFO, LRU, LFU und TTL sowie mit dem Begriff der Trefferquote, und verfolgen Sie dann eine kurze Anfragefolge von Hand. Implementieren Sie den Cache anschließend selbst mit einem Dictionary und einer doppelt verketteten Liste mit Wächterknoten, und vergleichen Sie ihn mit Bibliotheksversionen wie OrderedDict und LinkedHashMap. Zum Schluss lohnen praktische Aufgaben zu Thread-Sicherheit, Cache-Invalidierung und der Kombination mit Ablaufzeiten.
Jedes erfolgreiche get oder put schiebt den Eintrag an das Ende der zuletzt genutzten; wird Platz gebraucht, fällt der Eintrag am anderen Ende heraus.
Die Map findet den Knoten eines Schlüssels direkt, die Liste löst Knoten in O(1) heraus und fügt sie vorne wieder ein.
get und put ändern nur eine konstante Zahl von Zeigern und brauchen im Mittel konstante Zeit; der Speicher wächst mit der Kapazität.
Reale Systeme nutzen oft CLOCK, Pseudo-LRU, Stichproben-LRU, 2Q oder W-TinyLFU, um Aufwand zu sparen oder großen Scans standzuhalten.
Ein dict ordnet Schlüssel Knoten zu, und eine doppelt verkettete Liste zwischen den Wächtern head und tail hält die Nutzungsreihenfolge. get schiebt den Knoten nach vorne; put entfernt bei vollem Cache den Knoten direkt vor tail. Mit python lru_cache.py wird "b" verdrängt und None 1 3 ausgegeben.
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.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von LRU-Cache.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu LRU-Cache aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.