Welche cache-strategie wäre am sinnvollsten? LRU?
-
Du schreibst, du hast eine große Anzahl von Daten (> 100000), die Berechnung der einzelnen Daten ist sehr aufwändig und daher benutzt du einen Cache, aber du hast keine Speicherprobleme.
Warum speicherst du dann nicht einfach ALLE berechneten Daten ab und fügst die in eine Hash-Map (bzw. zumindestens eine normale Map mit logaritmischem Zugriff) ein (den Key dafür hast du ja schon berechnet).
Oder wenn dir dann irgendwann der Speicher dafür zu knapp wird, dann mußt du halt die an wenigsten benutzen Daten wieder löschen (d.h. du mußt dir noch merken, wie oft jedes Datenelement benutzt wurde).
-
Danke für die Beiträge.
Du schreibst, du hast eine große Anzahl von Daten (> 100000), die Berechnung der einzelnen Daten ist sehr aufwändig und daher benutzt du einen Cache, aber du hast keine Speicherprobleme.
Warum speicherst du dann nicht einfach ALLE berechneten Daten ab und fügst die in eine Hash-Map (bzw. zumindestens eine normale Map mit logaritmischem Zugriff) ein (den Key dafür hast du ja schon berechnet).
Oder wenn dir dann irgendwann der Speicher dafür zu knapp wird, dann mußt du halt die an wenigsten benutzen Daten wieder löschen (d.h. du mußt dir noch merken, wie oft jedes Datenelement benutzt wurde).völlig korrekt der Vorschlag ja. Ich könnte ja die Hash-map von der Grösse her auch beschränken oder?
Ich bin im Moment noch am messen wieviel Overhead die Suche meiner Daten braucht.
SOweit ich aber weiß gibt es eine Hash-Map als fertige Datenstruktur unter C++ nicht oder? Lediglich die von Dir vorgeschlagene map.
In diesem Sinne müsste ich mir auch keine Gedanken über die Cache-Strategie (also LRU) machen - die fiele durch die map weg ja.Für weiter Anregungen bin ich gerne offen - Danke
-
thordk schrieb:
LRU heisst least recently used und genau das soll es auch bedeuten. die strategie ist, die daten aus dem cache zu kicken, auf die am seltensten zugegriffen wird. das ganze als warteschlange zu betrachten ist nur eine mögliche implementierung.
Falsch.
Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten". Das ist ein grosser Unterschied.Die Implementierung über eine Warteschlange ist nur eine Möglichkeit es zu implementieren, aber jede LRU Implementierung muss das gleiche Verhalten zeigen (was das "welches Element fliegt wann raus" angeht) wie die Version mit der Warteschlange, sonst ist es kein LRU mehr.
-
Hat das das von mir überhaupt einen Namen?
Ich schmeiße zwar das älteste raus, reihe es aber vorne nicht ein....sollte ich dann doch eine warteschlange bauen anstatt eines normalen arrays um die verschiebung der elemente zu realisieren sozusagen?
-
hustbaer schrieb:
Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten".
du solltest den fokus auf least setzen, nicht recently. daten, auf die "am wenigsten" zugegriffen wird, nicht "zuletzt".
-
thordk schrieb:
hustbaer schrieb:
Last Recently Used (aka. Least Recently Used) bedeutet "am längsten nicht benützt" und nicht "am seltensten".
du solltest den fokus auf least setzen, nicht recently. daten, auf die "am wenigsten" zugegriffen wird, nicht "zuletzt".
Und du solltest deine Englisch- und/oder Fachkenntnisse vertiefen.
-
@thordk:
Lies es doch nach wenn du mir nicht glaubst.Was du meinst ist LFU: Least Frequently Used.
-
afaiko schrieb:
Hat das das von mir überhaupt einen Namen?
Ich schmeiße zwar das älteste raus, reihe es aber vorne nicht ein....sollte ich dann doch eine warteschlange bauen anstatt eines normalen arrays um die verschiebung der elemente zu realisieren sozusagen?
Äh.
Wie findest du denn das älteste Element?
Wenn du keine Queue verwendest müsstest du ja zu jedem Element irgendwie ein "Alter" mitspeichern. Und jedesmal wenn du ein Element rauswirfst das "älteste" suchen.Wenn du das so machst dann ist es LRU. Wie es implementiert ist ist ja wie gesagt egal, wichtig ist nur wann welches Element rausgeworfen wird, also das "beobachtbare Verhalten" wenn man es so nennen will.
-
h.
Wie findest du denn das älteste Element?
Wenn du keine Queue verwendest müsstest du ja zu jedem Element irgendwie ein "Alter" mitspeichern. Und jedesmal wenn du ein Element rauswirfst das "älteste" suchen.Jo so ist es. Ich habe ein zusätzliches array wo ich prioritäten habe. Bei jedem insert an der stelle wird die priorität auf 0 gesetzt. Bei jeder suche nach dem ältesten element , wird jede priorität gleichzeitig um 1 erhöht.
Das ist natürlich linearer aufwand ja. Aber so kann ich zumindest die ältesten bestimmen.Ich glaube ich probiere mal ein hash-table. Weiß jemand zufällig wie ich an ein vordefiniertes rankomme? Weil unter C++ gibts so was ja net in der std oder?
Danke
-
ich sehe gerade dass es sowas wie ne <ext/hash_map> gibt.
Kann ich das hash-table von der grösse her beschränken? Ginge das?
