Was ist der Unterschied zwischen LRU- und LFU-Algorithmen?

Unterschied: LRU ist der am längsten verwendete Seitenersetzungsalgorithmus, der die Seiten eliminiert, die am längsten nicht verwendet wurden, während LFU der am längsten verwendete Seitenersetzungsalgorithmus ist, der die Seiten eliminiert, die am seltensten besucht wurden in einem bestimmten Zeitraum. Der Schlüssel zu LRU besteht darin, die Zeitspanne von der letzten Nutzung der Seite bis zur Planung zu betrachten, während der Schlüssel zu LFU darin besteht, die Häufigkeit der Seitennutzung innerhalb eines bestimmten Zeitraums zu betrachten.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Für die Webentwicklung ist Caching unerlässlich und auch die häufigste Methode zur Leistungssteigerung. Sei es der Browser-Cache (wenn es sich um einen Chrome-Browser handelt, können Sie ihn über chrome:://cache anzeigen) oder der serverseitige Cache (über eine In-Memory-Datenbank wie memcached oder redis). Caching kann nicht nur den Benutzerzugriff beschleunigen, sondern auch die Serverlast und den Serverdruck reduzieren. Dann ist es besonders wichtig, die Strategien und Prinzipien gängiger Cache-Eliminierungsalgorithmen zu verstehen.

Gemeinsame Caching-Algorithmen

• LRU (zuletzt verwendet): Zuletzt verwendet. Wenn auf die Daten kürzlich zugegriffen wurde, ist die Wahrscheinlichkeit, dass in Zukunft darauf zugegriffen wird, ebenfalls höher.
• LFU (Am wenigsten häufig verwendet) Wenn ein Datenelement in der letzten Zeit selten verwendet wurde, ist es auch sehr unwahrscheinlich, dass es in Zukunft verwendet wird.
• FIFO (Fist in first out). Wenn ein Datenelement zuerst in den Cache gelangt, sollte es frühestens gelöscht werden.

LRU-Cache

Wie Browser-Caching-Strategien und Memcached-Caching-Strategien wird der LRU-Algorithmus verwendet. Der LRU-Algorithmus wird Daten eliminieren, auf die in naher Zukunft am wenigsten zugegriffen wird. Der Grund, warum LRU so beliebt ist, liegt darin, dass es relativ einfach zu implementieren ist und auch für praktische Probleme sehr praktisch ist, mit guter Laufzeitleistung und hoher Trefferquote. Lassen Sie uns darüber sprechen, wie der LRU-Cache implementiert wird:

• Neue Daten werden in den Kopf der verknüpften Liste eingefügt.
• Immer wenn der Cache zutrifft (d. h. auf die zwischengespeicherten Daten zugegriffen wird), werden die Daten in den Kopf verschoben der verknüpften Liste
• Wenn die verknüpfte Liste voll ist, verwerfen Sie die Daten am Ende der verknüpften Liste

Der LRU-Cache hat die folgenden Vorgänge:

• set(key, value): Wenn der Schlüssel in der Hashmap vorhanden ist Setzen Sie zuerst den entsprechenden Wert zurück, rufen Sie dann den entsprechenden Knoten cur ab und legen Sie ihn fest. Der aktuelle Knoten wird aus der verknüpften Liste gelöscht und an den Kopf der verknüpften Liste verschoben. Wenn der Schlüssel nicht in der Hashmap vorhanden ist, wird ein neuer Knoten erstellt und am Anfang der verknüpften Liste platziert. Wenn der Cache voll ist, löschen Sie einfach den letzten Knoten der verknüpften Liste.
• get(key): Wenn der Schlüssel in der Hashmap vorhanden ist, platzieren Sie den entsprechenden Knoten an der Spitze der verknüpften Liste und geben Sie den entsprechenden Wert zurück, wenn er nicht vorhanden ist.

Der Unterschied zwischen LRU und LFU:

LRU ist der zuletzt verwendete Seitenersetzungsalgorithmus (Least Recent Used), d. h. die Seiten, die am längsten nicht verwendet wurden, werden zuerst gelöscht!

LFU ist der am seltensten verwendete Seitenersetzungsalgorithmus (Least Frequently Used), was bedeutet, dass die Seiten eliminiert werden, die in einem bestimmten Zeitraum am seltensten besucht wurden!

Zum Beispiel beträgt die Periode T der zweiten Methode 10 Minuten. Wenn das Paging jede Minute durchgeführt wird, ist der Hauptspeicherblock 3. Wenn die erforderliche Seitenrichtung 2 1 2 1 2 3 4 ist

Hinweis: Beim Paging beträgt 4 Es kommt zu einem Interrupt wegen fehlender Seite

Wenn der LRU-Algorithmus verwendet wird, sollte Seite 1 geändert werden (Seite 1 wurde die längste Zeit nicht verwendet), Seite 3 sollte jedoch gemäß dem LFU-Algorithmus geändert werden (Seite 3 wurde nur verwendet). einmal innerhalb von zehn Minuten verwendet)

Zusammenfassung

Es ist ersichtlich, dass der Schlüssel zu LRU darin besteht, die Zeitspanne zwischen der letzten Verwendung der Seite und der Planung zu betrachten Schauen Sie sich die Häufigkeit der Seitennutzung innerhalb eines bestimmten Zeitraums an!

Weitere Informationen zu diesem Thema finden Sie in der Spalte „FAQ

Das obige ist der detaillierte Inhalt vonWas ist der Unterschied zwischen LRU- und LFU-Algorithmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!