Most Recently Used Cache
-
Hi, wie implementiert man einen Most Recently Used Cache in c++?
unordered_map + std::list?was ist der unterschied zu einem LRU (least recently used cache), the most recently used element wird ans ende der list verschoben und wenn der cache voll wird remove ich element vom ende der liste?
-
Most Recently Used: Das Element, auf das Du zuletzt zugegriffen hast, wird aus dem cache geworfen.
Wozu soll das gut sein? Damit wird ein Element ja nur einmal aus dem Cache geladen. Was ist da der Anwendungsfall?
-
adfasdff schrieb:
Most Recently Used: Das Element, auf das Du zuletzt zugegriffen hast, wird aus dem cache geworfen.
Nö, wird´s nicht. Ein MRU Cache enthält die letzten N Elemente, die benutzt worden sind. Alle anderen werden rausgeworfen.
-
@OP
Da gibt´s in C++ mehrere Möglichkeiten, die Wahl des richtigen Containers hängt wohl von der Größe des Cache ab und ob die Reihenfolge der Elemente wichtig ist. Wenn die Anzahl der Elemente klein und die Reihenfolge wichtig ist, ist std::list intuitiv der richtige Container, wobei std::vector vermutlich keine nennenswerte Nachteile hat.Vorgehen bei MRU mit Beachtung der Reihenfolge:
- einzufügendes Element aus dem Container löschen (um Duplikate zu vermeiden)
- einzufügendes Element vorn in den Container einfügen
- evtl. überflüssige Elemente hinten aus dem Container entfernen
-
adfasdff schrieb:
Most Recently Used: Das Element, auf das Du zuletzt zugegriffen hast, wird aus dem cache geworfen.DocShoe schrieb:
Nö, wird´s nicht. Ein MRU Cache enthält die letzten N Elemente, die benutzt worden sind. Alle anderen werden rausgeworfen.
Das erste ist ganz falsch, das zweite ist die Definition eines beliebigen Caches. MRU ist die Verdraengungsstrategie. Sobald im Cache kein Platz mehr ist wird das Element raus geworfen, das von allen N Elementen am haeufigsten benutzt wurde.
LRU und MRU lassen sich beide ganz gut mit unordered_map (fuer die Inhalte) und list (fuer das finden des MRU/LRU) realisieren.
-
adfasdff schrieb:
Wozu soll das gut sein? Damit wird ein Element ja nur einmal aus dem Cache geladen. Was ist da der Anwendungsfall?
Es wird potentiell öfter geladen - nur sobald der cache voll ist, fliegen die neuesten Items raus.
Das ist zB dann relevant wenn du Daten scannst - wo Daten die du jetzt gerade gesehen hast, lange nicht mehr verwendet werden. Ist natürlich nur für speziale Fälle brauchbar.
LRU oder LFU sind gängiger.
-
adfasdff schrieb:
Damit wird ein Element ja nur einmal aus dem Cache geladen.
Nicht ganz. Ein neues Element kann durchaus im Cache verbleiben (auch wenn dieser bereits voll ist), wenn unmittelbar nach dem neuen Element ein anderes Element angesprochen wird das bereits im Cache ist. Dann wird dieses nämlich zum "most recently used", und dann beim darauffolgenden Zugriff verworfen - wenn nicht wieder ein Element aus dem Cache angefordert wird. Usw.
adfasdff schrieb:
Was ist da der Anwendungsfall?
Guggsdu Wikipedia.
http://en.wikipedia.org/wiki/Cache_algorithms#Examples
