Es scheint, dass Ihr Browser von unserer Anwendung nicht unterstützt wird.

Lösungserläuterung

Laufzeitkomplexität

get (hashset): O(1) im durchschnittlichen Fall, O(n) im schlechtesten Fall

set (hashset): Konstant, O(1)

Löschung am Kopf beim Hinzufügen eines neuen Elements (verknüpfte Liste): Konstant, O(1)

Suche zum Löschen und Hinzufügen am Ende (verknüpfte Liste): O(n)

Komplexität: O(n)

Speicherkomplexität

Linear, O(n), wobei n die Größe des Cache ist.

Aufschlüsselung der Lösung

Caching ist eine Technik zur Speicherung von Daten in einem schnelleren Speicher (in der Regel RAM), um künftige Anfragen schneller zu bedienen. Nachfolgend einige gängige Beispiele für die Verwendung von Cache:

• Ein Prozessor-Cache wird verwendet, um Daten schneller aus dem Hauptspeicher (RAM) zu lesen.
• Cache im RAM kann verwendet werden, um einen Teil der Festplattendaten im RAM zu speichern und künftige Anfragen schneller zu bedienen.
• Netzwerkantworten können im RAM zwischengespeichert werden, um zu viele Netzwerkaufrufe zu vermeiden.

Der Cache-Speicher ist jedoch in der Regel nicht groß genug, um den gesamten Datensatz zu speichern. Daher müssen die Daten aus dem Cache-Speicher entfernt werden, wenn er voll ist. Es gibt eine Reihe von Cache-Algorithmen zur Umsetzung einer Cache-Verdrängungspolitik. LRU ist ein sehr einfacher und weit verbreiteter Algorithmus. Das Kernkonzept des LRU-Algorithmus besteht darin, die ältesten Daten aus dem Cache zu entfernen, um Platz für neue Daten zu schaffen.

Um einen LRU-Cache zu implementieren, verwenden wir zwei Datenstrukturen: ein Hashmap und eine doppelt verknüpfte Liste. Eine doppelt verkettete Liste hilft bei der Aufrechterhaltung der Auslagerungsreihenfolge und eine Hashmap hilft bei der O(1)-Suche nach den Cache-Schlüsseln. Hier der Algorithmus für den LRU-Cache.

If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and Return

Die doppelt verkettete Liste wird verwendet, um die Elemente zu verfolgen, auf die zuletzt zugegriffen wurde. Das Element am Ende der doppelt verketteten Liste ist das Element, auf das zuletzt zugegriffen wurde. Alle neu eingefügten Elemente (in put) gehen an das Ende der Liste. In ähnlicher Weise geht jedes Element, auf das zugegriffen wird (bei einer get-Operation), an das Ende der Liste.