LRU-Cache steht für Least Recently Used Cache, der den am wenigsten genutzten Eintrag entfernt. Da der Zweck des Cache darin besteht, Daten schnell und effizient abzurufen, muss er bestimmte Anforderungen erfüllen.
Einige der Anforderungen sind
- Feste Größe: Der Cache muss bestimmte Grenzen haben, um den Speicherverbrauch zu begrenzen.
- Schneller Zugriff: Cache Einfüge- und Nachschlageoperationen sollten schnell sein, vorzugsweise O(1)-Zeit.
- Ersetzung von Einträgen, wenn die Speichergrenze erreicht ist: Ein Cache sollte einen effizienten Algorithmus haben, um den Eintrag zu entfernen, wenn der Speicher voll ist.
Im Falle eines LRU-Caches entfernen wir den am wenigsten benutzten Eintrag, also müssen wir die kürzlich benutzten Einträge im Auge behalten, die Einträge, die seit langer Zeit nicht mehr benutzt wurden und die kürzlich benutzt wurden, sowie die Nachschlage- und Einfügeoperationen sollten schnell genug sein.
Wenn wir über O(1) Nachschlageoperationen nachdenken, kommt uns die HashMap als offensichtliche Datenstruktur in den Sinn. HashMap bietet O(1) Einfügung und Nachschlagen. aber HashMap hat keinen Mechanismus, um zu verfolgen, welcher Eintrag kürzlich abgefragt wurde und welcher nicht.
Um dies zu verfolgen, benötigen wir eine andere Datenstruktur, die schnelles Einfügen, Löschen und Aktualisieren bietet, im Fall von LRU verwenden wir Doubly Linkedlist. Der Grund für die Wahl von Doubly LinkList ist O(1) Löschung, Aktualisierung und Einfügung, wenn wir die Adresse des Knotens haben, auf dem diese Operation durchgeführt werden muss.
So wird unsere Implementierung von LRU-Cache HashMap und Doubly LinkedList haben. In der HashMap werden die Schlüssel und Adressen der Knoten der Doubly LinkedList gespeichert. Und Doubly LinkedList enthält die Werte der Schlüssel.
Da wir die zuletzt verwendeten Einträge im Auge behalten müssen, werden wir einen cleveren Ansatz verwenden. Wir entfernen ein Element von unten und fügen ein Element am Anfang der LinkedList hinzu, und wenn auf einen Eintrag zugegriffen wird, wird er nach oben verschoben, so dass die zuletzt verwendeten Einträge oben und die am wenigsten verwendeten unten stehen.
Lassen Sie uns den LRU Cache implementieren.
Ich hoffe der Code und das Tutorial sind selbsterklärend.