Schnellste Art LRU Array zu bauen?

Hallo,

ich würde gerne wissen was die einfachste Art ist einen LRU Mechanismus auf ein Array zu implementieren. Ich bin mir unsicher ob eine verkettete Liste nicht zu langsam wäre. Ein ständiges umkopieren der Array-Elemente will ich aber natürlich verhindern sodaß ich wohl mit pointern arbeiten muss...

Habt ihr vorschläge?

Danke

Für dein Vorhaben bietet sich natürlich eine verkettete Liste an, da es damit am einfachsten zu implementieren ist.
Ein schnelles Lookup könntest du über eine zusätzliche Hash-Map erreichen, welche für jeden Index in dein "Array" einen Zeiger auf das passende Element speichert.
So wäre auch das Umhängen noch recht effizient.

Wenn man eine LRU-Struktur benötigt so hat man doch meist den Fall, dass man nur auf sehr wenige Elemente am Anfang oder Ende zugreifen muss und somit eine insgesamt recht effiziente Struktur hat, wenn man eine verkettete Liste verwendet.

Ich habe in einem Cache mal solch eine Liste benutzt um die ältesten Elemente zu finden und diese zu löschen. Jedes Element hatte einen Iterator auf die LRU-Liste und so konnte ich bei jedem Zugriff schnell das Element in der Liste Umhängen und über die Liste nach Zugriff sortiert auf alle gerade aktiven Elemente zugreifen.

Überlege dir zunächst einmal genau was du brauchst, dann kann man dir Datenstruktur bzw. eine Komposition von mehreren Strukturen entwerfen.

erstmal danke für deinen beitrag.

Ich habe in einem Cache mal solch eine Liste benutzt um die ältesten Elemente zu finden und diese zu löschen. Jedes Element hatte einen Iterator auf die LRU-Liste und so konnte ich bei jedem Zugriff schnell das Element in der Liste Umhängen und über die Liste nach Zugriff sortiert auf alle gerade aktiven Elemente zugreifen.

hier komme ich leider nicht mit bzw. ich kann es mir schwer vorstellen.

Ich habe einen cache fixer Grösse und will hier einen LRU bauen. Jedesmal wenn ich auf ein Element zugreife muss es natürlich an den Anfang gehängt werden. Dieses Umhängen aber ist doch teuer oder nicht? Nehmen wir an das gefundene Element ist auf position 3, dann muss ich erst das element auf position 3 löschen und das gleiche am anfang einhängen.
Oder ist das dadurch günstig dass ich einfach nur 2 Pointer vom Element 3 ändere, einer zeigt auf element 1 und der zweite auf Head oder so. Dafür muss ich aber jeden Pointer von jedem Element bis zu dem gelöschten umhängen. D.h. es ergeben sich hier Änderungen aller Vorelemente.
Natürlich wenn das Element nicht da ist wirds einfach vorne eingehängt und das letzte = älteste purzelt raus.

Fellhuhn

Du machst eine normale doppelt verkettete Liste, diese hat also jeweils einen Zeiger auf das davorstehende und das dahinterliegende Element. Und natürlich einen Zeiger auf die eigentlichen Daten.

Dazu hast du noch einen Container in denen du die eigentlichen Daten speicherst. Dann brauchst du da zumindest nichts ändern, wenn du das schon hast. Sonst die Daten mit in die Liste statt Zeiger.

Dann hast du noch, falls benötigt, eine Hashmap die auf die einzelnen Einträge der Liste verweist, falls du die Elemente zB per ID ansprechen willst.

Wird jetzt zum Beispiel das Element mit ID 10 angesprochen, suchst du den Listeneintrag per Hashmap heraus. Biegst die Zeiger der Nachbarn um (prev->next auf next, next->prev auf prev) und stellst das Element an die erste Stelle (prev = auf 0, first->prev auf this, next auf first, first auf this) und bist fertig.

Also als verkettete Liste benutzt du einfach std::list, so habe ich das bei meinem Cache gemacht.
Die Objekte nennen wir ab jetzt mal "Object" und meine std::list sah dann so aus:
std::list< Object* >

Und innerhalb von Object hatte ich ein Attribut "std::list< Object* >::iterator" welches auf das Element der LRU Liste zeigte das auf dieses Object zeigt.
Somit konnte ich über das Objekt direkt auf den Eintrag in der LRU Liste zugreifen und diesen wieder ganz vorne einhängen.
Und wenn ich die ältetesten Elemente löschen wollte habe ich einfach so lange das hinterste Element der LRU Liste entfernt bis wieder genügend Platz vorhanden war.
Auf die eigentlichen Object Objekte konnte ich dann über den Zeiger aus der LRU Liste zugreifen und freigeben.

Ok - vorerst beschäftige ich mich mit euren Ideen :).

Darf ich trotzdem nochwas fragen:

Ich muss/will so performant wie möglich bleiben. Nun weiß ich dass die verwendung der stl mit iteratoren etc. manchmal langsamer sein kann als eine rohe Pointer-basierte C-artige Implementierung. Das habe nicht nur ich bemerkt sondern diverse andere Leute (die was vom Fach verstehen). In diesem Sinne müsste ich dann wohl über structs und dergleichen gehen...

Wie ist eure Meinung dazu?

Itsme2 schrieb:

Ok - vorerst beschäftige ich mich mit euren Ideen :).

Darf ich trotzdem nochwas fragen:

Ich muss/will so performant wie möglich bleiben. Nun weiß ich dass die verwendung der stl mit iteratoren etc. manchmal langsamer sein kann als eine rohe Pointer-basierte C-artige Implementierung. Das habe nicht nur ich bemerkt sondern diverse andere Leute (die was vom Fach verstehen). In diesem Sinne müsste ich dann wohl über structs und dergleichen gehen...

Wie ist eure Meinung dazu?

Die STL-Implementierungen sind halt sehr generell gehalten, es kann also immer mal sein, dass man mit was handgeschriebenem schneller ist.
Die Iteratoren einer std::list sind keine einfachen Zeiger, aber wenn du einen komfortablen Weg zum durchiterieren willst und nicht immer mit cur = cur->next weitergehen willst, dann wirst du so ziemlich 1:1 den gleichen Code schreiben.

Hmm...eine doppelt verkette liste ist ja ein dynamischer speicher. ich will aber einen beschränkten speicher der von anfang an einen gewissen wert nicht überschreiten darf - sobald also die liste maximal groß ist werden elemente rausgelöscht....aber so macht ja eine std::list mit daten wenig sinn oder?

Itsme2 schrieb:

Hmm...eine doppelt verkette liste ist ja ein dynamischer speicher. ich will aber einen beschränkten speicher der von anfang an einen gewissen wert nicht überschreiten darf - sobald also die liste maximal groß ist werden elemente rausgelöscht....aber so macht ja eine std::list mit daten wenig sinn oder?

Das ist der Sinn eines Cache, so lange Platz da ist (eingestellte Obergrenze) werden Daten dort eingelagert, wenn kein Platz mehr vorhanden ist werden Daten verworfen.

@tippgeber - könntest du mal ein snippet von deiner lru-struktur posten?