Anwendung doppelt verkettete Liste
-
bei einem LRU cache ist eine doppelt verkettete liste recht praktisch, um zu tracken welche elemente am längsten nichtmehr benutzt wurden. dazu hängt man ein gerade benutztes element einfach aus der liste raus, und dann ganz vorne wieder rein. ganz hinten stehen dann die elemente die am längsten nichtmehr verwendet wurden.
parallel zu der liste verwendet man bei grösseren caches dann noch eine map (z.b. hash-map), damit man die elemente schnell finden kann.
-
n wizard mit vor und zurueck koennte man auch damit generischer loesen #gg
-
Die Sachen von Dragon und Mr Evil gehen mit einem dynamischen Array genausogut, fürchte ich. hustbaers MTF-List ist was Feines, so eine benutze ich auch gerade. Aber ob es gut ist, hinter einen LRU-Cache eine hash-map zu legen? Vielleicht wäre ein Spreizbaum für die gesamten Daten übgerlegenswert.
-
Eine dynamische Graphdatenstruktur, zu jedem Knoten wird eine Liste der Nachbarknoten verwaltet. Durch die Verwendung von Listen können Kanten effizient eingefügt und gelöscht werden.
-
Jester schrieb:
Eine dynamische Graphdatenstruktur, zu jedem Knoten wird eine Liste der Nachbarknoten verwaltet. Durch die Verwendung von Listen können Kanten effizient eingefügt und gelöscht werden.
Eine Kante kennt genau zwei Knoten? Dann könnte sich die Kante auch ihre beiden Knoten und die jeweils eigenen Kantenarray-Indizes im Knoten merken. Mir scheint, das Löschen und Einfügen hat asymptotisch keine andere Effizienz. Aber viele Algos genießen es, wenn man effizient Löschen kann, ohne die Reihenfolge zu ändern, ohne daß man umgebende Schleifen beenden müß.
-
Ich arbeite viel mit planaren Graphen, da kodiert die Reihenfolge der Kanten dann die Einbettung, wenn Du die durcheinanderwirbelst ists schlecht.
Außerdem bleiben Pointer auf Kanten gültig.
Wenn ich zwei Knoten miteinander identifizieren möchte kann ich die Kantenlisten in konstanter Zeit zusammenhängen.
-
volkard schrieb:
Aber ob es gut ist, hinter einen LRU-Cache eine hash-map zu legen? Vielleicht wäre ein Spreizbaum für die gesamten Daten übgerlegenswert.
Naja, wenn eine Hash-Map erstmal ihre finale Grösse erreicht hat, dann sind so ziemlich alle Operationen O(1). Was könnte besser sein als das?
-
hustbaer schrieb:
Naja, wenn eine Hash-Map erstmal ihre finale Grösse erreicht hat, dann sind so ziemlich alle Operationen O(1). Was könnte besser sein als das?
Ich hoffe, während des Wachsens hat man auch amortisiert O(1). Wozu dann LRU-Cache davor?
-
Wieso davor?
Die Hash-Map ist ein Teil des LRU Caches.
So ein Cache kann ja gross werden (viele Einträge, nicht grosse Einträge), und man will seine Daten da drinnen schnell finden. Also macht man eine Hash-Map für Lookups, und eine Linked-List um zu tracken was "recently used" ist.
Die beiden Datenstrukturen werden parallel verwendet, und ergeben zusammen - mit etwas Glue-Code - den LRU Cache.
-
hustbaer schrieb:
Also macht man eine Hash-Map für Lookups, und eine Linked-List um zu tracken was "recently used" ist.
Ah! Hab nicht nachgedacht.
