Die Implementierung einer LRU-Cache-Ersatzrichtlinie hilft, die Speichernutzung zu optimieren, indem die zuletzt aufgerufenen Elemente entfernt werden, wenn der Cache seine Kapazität erreicht.

LRU Cache verstehen

Ein LRU-Cache (Least Last Last Used) verfolgt die Artikelverwendung, um zu bestimmen, welche Daten bei Platzbedarf vertreiben werden. Er priorisiert kürzlich aufgerufene Elemente und stellt sicher, dass häufig verwendete Daten verfügbar bleiben.

Kernkomponenten eines LRU-Cache

Ein effektiver LRU-Cache kombiniert typischerweise zwei Datenstrukturen:

  • Hash Map: Bietet schnellen Zugriff auf Cache-Elemente.
  • Doppelverknüpfte Liste: Behält die Reihenfolge der Artikelverwendung bei, wobei die neueste an der Vorderseite ist.

Umsetzungsschritte

Befolgen Sie diese Schritte, um einen LRU-Cache zu implementieren:

  • Initialisieren Sie die Hash-Karte und doppelt verknüpfte Liste.
  • Beim Datenzugriff verschieben Sie das Element an die Spitze der Liste.
  • Wenn der Cache die Kapazität übersteigt, entfernen Sie das Element am Ende der Liste.
  • Aktualisieren Sie die Hash-Karte entsprechend bei Einfügungen und Löschungen.

Beispielimplementierung in Python

Hier ist ein einfaches Beispiel für einen LRU-Cache in Python:

Hinweis: Dieser Code verwendet das Collections-Modul für OrderedDict, das die Implementierung vereinfacht.

„Python

aus Sammlungen importieren OrderedDict

Klasse LRUCache:

def init (selbst, Kapazität):

self.cache = OrderedDict()

Eigenleistung = Kapazität

def get(selbst, Schlüssel):

falls nicht in self.cache:

Rückgabe -1

self.cache.move to end(key)

return self.cache[key]

def put(self, key, value):

self.cache[key] = Wert

self.cache.move to end(key)

Wenn len(self.cache) > self.capacity:

self.cache.popitem(last=False)

„``