LRU-Algorithmus verstehen
Ich versuche, LRU zu verstehen, und es ergibt für mich keinen Sinn. Wenn ich es verstehe, wird es einfacher für mich zu programmieren. Kann mich jemand durch die Stufen gehen? Wie,
- Wenn sich die Referenz-Zeichenkette, an der Sie sich gerade befinden, im Array ist, dann Ziehst du zum nächsten Leerzeichen hoch?
- Wenn Sie nachsehen, ob etwas im Puffer ist, müssen wir dann scannen, wo wir sind oder das gesamte Array?
Ich kann einfach nicht mitkommen. Wie hält es sich am wenigsten in letzter Zeit auf dem Laufenden? Sollte das zuletzt verwendete nicht das sein, nach dem der Index bei?
ist 
4 Antworten
Speichern Sie zwei Objekte für jedes "Objekt". Der Wert (natürlich) und die "Zeit", die immer größer wird.
Also, unter Verwendung Ihrer Daten, unter der Annahme, dass 1 bis 4 in der Reihenfolge zugegriffen wurde:
%Vor%Zugriff "1" (sortiert nach Zeit für Klarheit, Zeit = 5)
%Vor%Zugriff "2" (nach Zeit für Klarheit sortiert, Zeit = 6)
%Vor%Zugriff "5", der nicht gefunden wird, verursacht einen Cache-Miss. Um den "Speicherplatz" zu finden, um die "5" zu speichern, müssen wir die zuletzt verwendete (LRU) löschen. Das bedeutet "3" fallen lassen. Beachten Sie, dass Zeit = 7 ist.
%Vor%Zugriff "1" (nach Zeit für Klarheit sortiert, Zeit = 8)
%Vor%Zugriff "2" (nach Zeit für Klarheit sortiert, Zeit = 9)
%Vor%Zugriff "3", der nicht gefunden wird, verursacht einen Cache-Fehler. Um den "Speicherplatz" zu finden, an dem die "3" gespeichert werden soll, müssen wir den Least Recently Used (LRU) leeren. Dies bedeutet, dass "4" fallen gelassen wird. Beachten Sie, dass Zeit = 10 ist.
%Vor%Zugriff "4", der nicht gefunden wird, verursacht einen Cache-Fehler. Um den "Speicherplatz" zu finden, um die "4" zu speichern, müssen wir die zuletzt verwendete (LRU) löschen. Dies bedeutet, dass "5" fallen gelassen wird. Beachten Sie, dass Zeit = 11 ist.
%Vor%Zugriff "5", der nicht gefunden wird, verursacht einen Cache-Miss. Um den "Speicherplatz" zu finden, um die "5" zu speichern, müssen wir die zuletzt verwendete (LRU) löschen. Dies bedeutet, dass "1" fallen gelassen wird. Beachten Sie, dass Zeit = 12 ist.
%Vor%Nachdem Sie nun wissen, wie das zu löschende Element ausgewählt wurde und über ein funktionierendes Beispiel verfügt, können Sie das Element leeren, ohne es im Array zu verschieben.
--- Bearbeitet mit zusätzlicher Erklärung ---
Ok, die Idee, Sachen in Listenform zu zeigen, scheint ein paar Fragen aufgeworfen zu haben, also werde ich es in Array-Form zeigen
Zugriff 1, Cache-Fehltreffer, leerer Platz verfügbar, im ersten verfügbaren Platz speichern
%Vor%Zugriff 2, Cache-Fehltreffer, leerer Steckplatz verfügbar, im ersten verfügbaren Steckplatz speichern
%Vor%Zugriff 3, Cache-Miss, leerer Slot verfügbar, im ersten verfügbaren Slot speichern
%Vor%Zugriff 4, Cache-Fehltreffer, leerer Steckplatz verfügbar, im ersten verfügbaren Steckplatz speichern
%Vor%Zugriff 1, Cache-Treffer, Zugriffszeit aktualisieren
%Vor%Zugriff 2, Cache-Treffer, Zugriffszeit aktualisieren
%Vor%Zugriff 5, Cache-Fehltreffer, kein verfügbares Leergut, verwerfen und ersetzen "zuletzt verwendet"
%Vor%Zugriff 1, Cache-Treffer, Zugriffszeit aktualisieren
%Vor%Zugriff 2, Cache-Treffer, Zugriffszeit aktualisieren
%Vor%Zugriff 3, Cache-Fehltreffer, kein verfügbares Leergut, verwerfen und ersetzen "zuletzt verwendete"
%Vor%Zugriff 4, Cache-Fehltreffer, kein verfügbares Leergut, verwerfen und ersetzen "zuletzt verwendet"
%Vor%Zugriff 5, Cache-Fehltreffer, kein verfügbares Leergut, verwerfen und ersetzen "zuletzt verwendet"
%Vor%Eine LRU wird normalerweise in eine Liste eingefügt. Wenn auf ein Objekt zugegriffen wird, entferne es aus der Liste (wenn es dort ist) und schiebe es nach hinten. Die Rückseite der Liste ist die zuletzt verwendete. Da Sie fortlaufend verwendete Elemente in den hinteren Bereich der Liste verschieben, landen die am wenigsten verwendeten am Ende der Liste. Wenn nicht genug Platz ist, knallst du von vorne.
Dies ist meine einfache Beispiel-C ++ - Implementierung für den LRU-Cache mit der Kombination aus Hash (unordered_map) und Liste. Elemente in der Liste haben einen Schlüssel für den Zugriff auf die Karte, und Elemente auf der Karte haben einen Iterator der Liste, um auf die Liste zuzugreifen. Jede aufrufende Methode ist also die Komplexität O (1).
%Vor%Tags und Links algorithm c c++ page-replacement