Servus
Ich bin derzeit dabei einen Cache zusammenzufrickeln. Meine Idee war
hier eine verkette Liste zu benutzen. Jedes der Items bekommt dabei
einen Namen (item.name), den Zeiger aufs nächste und aufs vorherige Item
sowie ein Alter.
Nun frage ich mich folgendes: Ich möchte auf Item25 zugreifen. Nun
könnte ich entweder nach dem Namen suchen (strcmp) (direkt in der Liste
oder in einem Array das Name | Adresse beinhaltet). Oder ich berechne
die Adresse des Items aus dem Namen. Geht das überhaupt - beliebiger
Name auf spez. Adresse? Heißt sowas nicht Hash Code?
Und: Macht eine verkettete Liste überhaupt Sinn oder wäre ein normales
Array sinnvoller?
Vielleicht kann mir jemand weiter helfen.
Hallo,
wenn du schnell in Bäumen suchen willst, dann implementiere z.B. einen
B-Baum. Wikipedia liefert Links zu Beispielen. Auch im altehrwürdigen N.
Wirth findet man Beispiele.
Einfacher ist, für die Strings einen eindeutigen Hash zu berechnen. Bei
nicht zu vielen Daten braucht man keinen MD5! Diesen als Index einer
Tabelle benutzen, welche dann einen Pointer auf die gesuchte
Datenstruktur enthält.
Hier erkauft man sich Rechenzeit durch Einsatz von Speicher.
MfG,
Andreas
Verkettete Listen machen dort Sinn wo man schnell einfügen oder löschen
können muss und ansonsten sequentiell über die Liste iteriert.
Wenn du einen schnellen wahlfreien Zugriff auf eine eine Menge von
Objekten haben willst, macht entweder ein sortiertes Array mit binärer
Suche oder binäre Bäume oder eben eine Hashtabelle Sinn.
Was du jetzt implementierst hängt davon ab wie groß die Datenmenge ist,
wieviel Aufwand du treiben willst, wie dein Kenntnisstand ist und welche
Plattform (Speicher) du benutzt.
Bei konkreteren Fragen kann dir hier bestimmt jemand weiterhelfen.
Geht um Cache auf einem Mikroprozessor. Große Daten, unterschiedlich oft
benutzt, Rechenzeit wichtig, Zugriffszeit auf Speicher begrenzt.
Nun passt es mit dem Use Case gut zusammen (soweit der Plan, das möchte
ich Untersuchen) die Daten in einem LRU Cache zu speichern.
Für Cache gibt es, soweit habe ich das glaueb ich verstanden, zwei
Ansätze:
- Verkettete Liste
- Array
Der Gag: Immer wieder wenn ein neues Item kommt rutscht die Liste eins
nach unten und das neueste kommt oben drauf. Damit sortiert sichs
automatisch nach dem am wenigsten häufig benutzten/ältesten item.
Nun bleibt die Frage ob eine Liste oder ein Array mehr Sinn machen. Und
egal welches davon, wie ich schnell auf das Datum zugreife ohne lange
suchen zu müssen. Wieviele Daten es schlussendlich sind weiß ich nicht
...
An Hash hab ich auch gedacht. Nur irgenwdie bekomme ich da gerade einen
Knoten ins hirn ... die Application kennt nur den Namen und sagt
"readFromCache(item25)" und bekommt dann von der Adresse xy das Datum.
Da bekomm ich bisschen einen Knoten ins HIrn wie das verwurstet werden
muss ...
Ah, Idee:
Array Cache
cache[1] --pointed to--> item1
cache[2] --pointed to--> item2
...
Hashe Cache
hache[1] > if accessed hash == hash in hache[1] => cache[index aktuell
hache[] ist gesuchtes datum
usw
Und wenn ich ein Datum aus dem Cache lösche und alles nachfolgende eins
nach oben rücke muss ich das selbe mit der hache tabelle machen richtig?
Nur wie komm ich von cache[] auf hache[] :D
Edit: Im Falle meines Caches kann ichs auch so machen
1
structsCacheItem{
2
data;
3
NAND_memAdress;// Physikalisch echte Adresse, gleichzeitig Key
4
}
5
6
structsCacheItem*aCache[MAXCACHEITEMS];
Zugriff aufs Item erfolgt dann mit suche nach er physikalisch echten
Adresse die gleichzeitig als Key/Name dient. Bin die ganze Zeit auf dem
Trip rumgerannt die Items nach dem als realen String zu bennnen wie sie
auch benutzt werden - is ja ganz nett aber funktioniert nicht so
richtig. Und da ich irgendwo die phys. echte Adresse ablegen muss kann
ich die auch gleichzeitig als Name benutzen. Der Cache soll auf
Applikationsebene ja eh "unsichtbar" sein und das ist er dann ja auf
jeden fall.
Naja, für einen Software-Cache brauchst du zweierlei:
Eine Datenstruktur die es dir erlaubt, entsprechend deiner
Verdrängungsstrategie (du schriebst LRU) schnell Aktualisierungen
vorzunehmen, und andererseits eine Suchstruktur mit der du die
betreffenden Cache-Einträge schnell auffinden kannst.
Vorschlag, da du ja mit expliziten Cache-Zugriffen (readFromCache)
arbeitest, verwende doch einfach ein Handle, das intern nur ein Pointer
auf eine Struktur mit Adresse des Listenelements + Ursprungsadresse der
Daten ist. Umgekehrt speichert jedes Cache-Element auch Ursprungsadresse
+ Daten.
Wenn das Element verdrängt wurde, stimmt die Adresse des Handles mit der
des referenzierten Cache-Elementes nicht mehr überein, das Handle ist
ungültig.
Beispiel:
Anstelle dem Programmierer die Handles aufzudrücken könntest du auch
intern ein Mapping Adresse->Cache-Element aufbauen, das wäre dann die
Variante mit der schon erwähnten Hashtabelle (oder einer anderen
assoziativen Struktur).
mfG
Markus
Ah, sodass ich also faktisch als Anwender von vorneherein meine Items
anlege - roh - und denen dann wenn sie in den Cache geladen werden auf
den Eintrag im Cache zeigen lasse. Ich steh nur irgendwie noch
gedanklich mit dem Mapping auf dem Schlauch. Das wäre die mir liebste
Variante - also das der geneigte Anwender nur sagen muss
"readFromCache(item25)" oder eben nur "read(item25)".
Wie sähe dann das Mapping aus? Ein array[][] mit Name vorne und Cache
Entry in der zweiten Spalte? Andererseits isse auch egal da das alles
irgendwie doppelt und dreifach ist. Ich weiß ja von vorne herein welche
Items ich habe, ergo brauch die ja nur dynamisch auf den Cache zu mappen
un gut is.
Besteht die möglichkeit Daten in einem struct "private" zu gestalten? So
wie Funktionen in einer .c nur für die .c zugänglich gemacht werden
indem man sie static macht.
Hallo,
wenn alle Deine Items sowieso schon bekannt sind, dann kannst Du ja die
Hashfunktion auf Kollisionsfreiheit und Tabellengrösse trimmen.
Nimm z.B. mal die klassischen Hashfunktionen (z.B.
http://www.ntecs.de/projects/guugelhupf/doc/html/x435.html) und lasse
sie über Deine Items laufen. Hast du z.B. 100 Items, wähle eine maximale
Tabellengröße von z.B. 256 und überprüfe, wie viele Kollisionen Du bei
den verschieden Algorithmen hast.
Laut Fazit des Artikels schneidet NEW [Bob Jenkins] für kleine Tabellen
(hier n=8) am besten ab. Ist auch relativ leicht zu implementieren.
Falls Du 0 Kollisionen hast, ists sowieso geschenkt, dann gibt der
berechnete Hash den Index auf die Tabelle (im einfachsten Fall Pointer
Array auf struct { type_enum eUsed, void *pData, void wasauchimmer }.
Über Diesen Pointer greifst Du dann kollisionsfrei auf Deinen Cache zu.
Bei Kollisionen kann man ggf, die Tabellengröße erhöhen, die
Hashfunktion optimieren, die Kollisionen verwalten oder zu dreckigen
Tricks greifen.
>Besteht die möglichkeit Daten in einem struct "private" zu gestalten?
Private gibts ohne Speicherschutz sowieso nicht, sondern nur obfuscate.
Das erreicht man schon, indem die Daten nicht im Header deklariert
werden.
Private ansich gibts nicht, aber man kann machen das die Daten nicht
mehr sichtbar sind von außen ;) so wie static Funktionen.
Ich schau mir die Links mal an. Danke. Die Seite zu den Hash Funktionen
hab ich schon gesehen. Denk mir aber im Moment: Ich habe eine Adresse
die Eindeutig einem Item, einem Eintrag und einer Position im phys.
realen Speicher vorhanden ist. Nehm ich doch einfach die un spare mir
die Hash Tabelle.
Heißt ich implementiere jetzt zwei structs
1
typedefstruct
2
{
3
#if LinkedList
4
Uint8*pNext;/*! \var *pNext \brief Pointer to next list entry */
5
Uint8*pPrev;/*! \var *pPrev \brief Pointer to previous list entry */
6
#endif
7
8
MEM_ADDR_SIZEmem_addr;/*! \var mem_addr \brief Physically real memory adress */
9
DATA_SIZEdata;/*! \var data \brief Data stored at entry */
10
}s_hCacheEntry;
und
1
typedefstruct
2
{
3
MEM_ADDR_SIZEmem_addr;/*! mem_addr \brief Physically real memory adress */
4
s_hCacheItem*cache_entry;/*! cache_entry \brief Pointer to the according cache_entry */
5
}s_hObject;
Das erste sind die Einträge im Cache selbst, das zweite sind die Objekte
die der Anwender in die Finger nimmt.
Lesen vom Cache geht dann über
1
Uint32readData(s_hObject*,s_hCacheEntry*);
Das intern alles mit LRU und dem Cache selbst verwurstet (Daten vom
Cache Entry werden als return übergeben, damit hat der Anwender mit dem
Cache nicht mehr so viel zu tun).
Ich pers. finde das jetzt nicht so ungeschickt, kann mich da aber auch
täuschen
Ano Nym schrieb:> Denk mir aber im Moment: Ich habe eine Adresse> die Eindeutig einem Item, einem Eintrag und einer Position im phys.> realen Speicher vorhanden ist. Nehm ich doch einfach die un spare mir> die Hash Tabelle.
Entweder das ist jetzt unklar ausgedrückt oder Du verstehst den Sinn des
Hashens nicht.
Falls mit Hashen gearbeitet wird, brauchst Du keine verkettete Liste,
außer Du verwendest einen kollisonsfreien(!) Hash als Eingang zu binären
oder B-Bäumen oder Skip-Lists.
Ansonsten brauchst Du eine Hash-Tabelle, Da dir der Hash ja das Bucket
aus der Tabelle liefert, welches Deine Daten bzw. einen Zeiger auf Deine
Daten liefert, d.h. über den Hash wird ja SCHNELL gesucht.
Bei Dir seh ich bis jetzt nur eine verkettete Liste ?!!
1. Schritt: Berechnen der Hashes
Item 0..x -> Hash 0..y mit x=y wenn Kollisionsfrei
2. Schritt: Initialisieren der Hashtabelle, z.B. Bucket = NULL
3. Schritt: Schreiben in die Tabelle (n Zellen) mit n>=x beim Cache
Write
bzw. Bucket(Hash(x)) = Pointer auf Cache von x
3.a.Verdrängungsstrategie: Ältesten Eintrag ggf. löschen und zugehörigen
Hashtabelleneintrag auf NULL setzen
4. Schritt: CacheRead
Hash des gesuchten Elements berechnen, Lookup in Hashtabelle, Wenn
Bucket <> Null, dann (*Pointer) lesen, ansonsen return Fail.
MfG,
Andreas
Eine verkettete Liste ist nur sinnvoll, wenn die Einträge immer der
Reihe nach benutzt und ausgetragen werden.
Z.B. man hat einen Scheduler und die Einträge sind nach ihrer
Ausführungszeit sortiert. Der Scheduler schnappt sich also immer den
ersten Eintrag, führt ihn aus und löscht ihn. Er muß nichts mehr
umständlich vergleichen. Das wurde schon beim Einfügen des Eintrags in
die Liste getan.
Ansonsten ist es nur unnötiger zusätzlicher Verwaltungsaufwand, da man
sich immer von Eintrag zu Eintrag hangeln muß.
Müssen Einträge sortiert werden, nimmt man eine einfache Liste. Diese
enthält nur die Nummern der Einträge. Bei längeren Daten ist es
schneller nur die Nummer des Datensatzes zu sortieren, anstatt immer die
kompletten Datensätze umzukopieren.
Peter
Hallo Peter und Andreas,
wenn es bei mir nicht gerade genauso ist, habt ihr etwas zu schnell
geantwortet. Die verkettete Liste implementiert die LRU-Strategie des
Caches, eine Navigationsstruktur existiert nur implizit durch die
Mapping-"Objekte", die beim Laden eines Cache-Eintrages aufgesetzt
werden müssen.
Ano Nym schrieb:> Ich pers. finde das jetzt nicht so ungeschickt, kann mich da aber auch> täuschen
Richtig, aber es gibt eine Einschränkung der du dir bewusst sein musst:
Diese Variante erkennt es nicht(!), wenn an zwei stellen die selbe
Adresse in den Cache geladen wird. Es existieren dann zwei unabhängige
Kopien und mit hoher Wahrscheinlichkeit kriegst du dann sehr hässliche
Seiteneffekte.
mfG
Markus
PS: Bei kleineren Caches kann es effektiver sein, auf aufwändige
Navigationsstrukturen zu verzichten und einen sequentiellen Scan
durchzuführen. Solche Randfälle sollte man aber bei Verdacht vorab
überprüfen und nicht einfach darauf spekulieren.
Peter Dannegger schrieb:> Eine verkettete Liste ist nur sinnvoll, wenn die Einträge immer der> Reihe nach benutzt und ausgetragen werden.>> Z.B. man hat einen Scheduler und die Einträge sind nach ihrer> Ausführungszeit sortiert. Der Scheduler schnappt sich also immer den> ersten Eintrag, führt ihn aus und löscht ihn. Er muß nichts mehr> umständlich vergleichen. Das wurde schon beim Einfügen des Eintrags in> die Liste getan.>> Ansonsten ist es nur unnötiger zusätzlicher Verwaltungsaufwand, da man> sich immer von Eintrag zu Eintrag hangeln muß.>> Müssen Einträge sortiert werden, nimmt man eine einfache Liste. Diese> enthält nur die Nummern der Einträge. Bei längeren Daten ist es> schneller nur die Nummer des Datensatzes zu sortieren, anstatt immer die> kompletten Datensätze umzukopieren.>>> Peter
Wie gesagt, das #if LinkedList #endif is nur prophylaktisch drin falls
ichs mit Ketter lösen wollte. Hab dann im späteren Verlauf noch ein
weiteres Strukt
1
typedefstruct
2
{/* Vereinfacht */
3
numEntries
4
s_hCacheEntries*CacheTable[MAX_NUM_OF_ENTRIES]
5
}s_hChecksum
machs also mit nem Array. Als Key für die Daten nutz ich die Adresse für
den realen speicher. Heißt:
Und damit vergleich ich wieder nur Zahlen und hab keine extra Tabelle
für das Mapping. Im grunde müsste das doch jetzt so tun wie mit Hashin
nur ohne Hashing oder?
Ano Nym schrieb:> Und damit vergleich ich wieder nur Zahlen und hab keine extra Tabelle> für das Mapping. Im grunde müsste das doch jetzt so tun wie mit Hashin> nur ohne Hashing oder?
Nicht wirklich.
Der Trick beim Hashen besteht ja darin, dass man nicht lange suchen
muss, sondern errechnen kann, wo ein Eintrag ist, wenn er denn in der
Liste ist.
Das ganze ist allerdings immer auch davon abhängig, wie gross denn dein
Sucharray ist. Bei wenigen Einträgen kann lineares Suchen, so wie du es
betreibst, schneller sein als alles andere. Ganz einfach deshalb, weil
deine Schleife extrem eng ist und es de facto innerhalb der Schleife
nichts zu tun gibt ausser zu vergleichen. Wenn du erst mal vom
Suchbegriff einen Hash-Code ausrechnen musst, dann kostet das Ausrechnen
ja auch Zeit und in der Zeit kann die enge Suchschleife schon einige
Einträge abklappern.
Wie überhaupt die Kunst beim Cachen darin besteht einen Kompromiss zu
finden zwischen dem Aufwand den man treiben will (und der natürlich Zeit
kostet) und der Zeit die man durchs cachen einspart. Ist der Aufwand
höher als die eingesparte Zeit, dann hat man es übertrieben.
> Und damit vergleich ich wieder nur Zahlen und hab keine extra> Tabelle für das Mapping.
Dann überleg dir mal, was du alles tu musst um in deinem Array eine LRU
Strategie zu implementieren. Was muss alles passieren wenn ein Eintrag
aus dem Cache rausfliegt.
Stimmt beim Hashen muss ich nicht linear suchen. Zur Zeit weiß ich noch
nicht wieviel Elemente unser Use Case vorsieht - ich denke aber mal
<=100.
EIn erster Entwurf meiner implementierung schaut wiefolgt aus:
Ist recht straight forward. Mein Gedanke: Wenn ich immer das unterste
rauszieh, lösch, die Tabelle eins nach unten rück und das benutzte nach
ganz oben einfüge ist das älteste/am wenigsten Benutzt immer unten -> es
sortiert sich von selbst.
Was noch fehlt ist bei einem Cache hit die Tabelle ebenfalls
umzusortieren sodass das benutzt wieder ganz oben ist. Ansonsten ist es
wirklich als erster Draft zu sehen, REchtschreibfehler dürfen behalten
werden
>Autor: Ano Nym (oorim)>Datum: 22.02.2011 11:37>Geht um Cache auf einem Mikroprozessor. Große Daten, unterschiedlich oft>benutzt, Rechenzeit wichtig, Zugriffszeit auf Speicher begrenzt.
Hmmm, irgendwie passen linear suchen und Rechenzeit wichtig, nicht gut
zusammen.
Außerdem seh ich die Verdrängungsstrategie nicht in Deinem Code oder
soll das das hier sein:
>Ist recht straight forward. Mein Gedanke: Wenn ich immer das unterste>rauszieh, lösch, die Tabelle eins nach unten rück und das benutzte nach>ganz oben einfüge ist das älteste/am wenigsten Benutzt immer unten -> es>sortiert sich von selbst.>Was noch fehlt ist bei einem Cache hit die Tabelle ebenfalls>umzusortieren sodass das benutzt wieder ganz oben ist. Ansonsten ist es>wirklich als erster Draft zu sehen, REchtschreibfehler dürfen behalten>werden
D.h. Du willst die Tabelle bei jedem Hit umsortieren ??
>Rechenzeit wichtig
Rechenzeit eher unwichtig, oder?
Vorschlag meinerseits: Nachdem Du ja mit einer Use Case Analyse schon
sehr gut angefangen hast, springe nicht vom Start zum Ziel.
Auch wenn manche Leute das im Kopf machen können, ist doch in jedem
ernstzunehmenden Entwicklungsprozess ein Designschritt zwischen Analyse
und Programmierung (z.B. OOA->OOD->OOP), so rapid prototyping kann das
ja gar nicht sein.
Bevor Du also ans Coden denkst, überlege Dir mal ein Design KOMPLETT
durch, welches zu den Anforderungen passt. C-Strukturen und Codes kommen
am Schluss.
Grundsätzliche Fragestellungen im Design sind z.B. auch, müssen die
gecacheten Items wirklich über einen Namen gesucht werden
>entweder nach dem Namen suchen (strcmp).... Oder ich berechne
die Adresse des Items aus dem Namen
... oder kann man den Items vielleicht ein eindeutiges Token zuordnen ?
Dann kann man sich das ganze hashen bzw. die Implementierung der
assoziativen Arrays sparen.
Viel Spaß noch
Jup im moment sortier ich nach jedem hit um. Das ist Rechenaufwändiger
als wenn ich die einzelnen Elemente mit einer Variable altern lassen
würde und einfach immer das älteste weg werf. Ist halt als erstes
Gedankenmodell zu sehen.
Ansonsten, zum eindeutigen Token: Warum nicht einfach die Adresse die
zum Platz im Speicher gehört her nehmen? Man könnte damit ja auch auf
das Objekt Struct verzichten, das beinhaltet ja im Grunde nur die
Adresse.
Ansonsten wäre ein Optimierungsschritt: Hash statt linearer suche. Das
hab ich allerdings noch nicht völlig Verstanden und damit auch nicht
integriert.
Ansonsten hab ich zu ziemlich jedem Algo bis auf die Page basierten was
raus geschrieben. Ich hab mir zu dem obigen GEdanken gemacht welche
Schnittstellen ich brauche und wie das Programm abläuft. Ist zwar immer
noch mehr oder weniger rapid prototyping aber so what :)
Aber bis auf die ineffizienten Stellen, so schwachsinnig ist das was ich
gezaubert habe erstmal nicht oder?
Ano Nym schrieb:> Ansonsten, zum eindeutigen Token: Warum nicht einfach die Adresse die> zum Platz im Speicher gehört her nehmen? Man könnte damit ja auch auf> das Objekt Struct verzichten, das beinhaltet ja im Grunde nur die> Adresse.
Das mit der Adresse klingt gut und entspräche wohl einem eindeutigem
Token, aber Du hast ja in Deinem ersten Post gleich mit
>strcmp
angefangen, so daß man annehmen konnte, Dein Suchschlüssel wäre ein
String bzw. eine Kombination aus String+Adresse.
Wenn Du jetzt aus Deiner Adresse einen eindeutigen Platz in einer
Cachetabelle (enspricht im Grunde einem simplen Hashen und einer
Hashtabelle) berechnen kannst, dann brauchst Du keine verketteten Listen
und keine lineare Suche und kannst Dich voll auf Verdrängungsstrategie,
Fragmentierung, etc. konzentrieren.
>Aber bis auf die ineffizienten Stellen, so schwachsinnig ist das was ich
gezaubert habe erstmal nicht oder?
Das ergibt sich leider nur aus einen Vergleich der optimalen Lösung des
Problems zu Deinem Ansatz.
P.S. Ist das eine Semesterarbeit ?
Nein, istk eine Semesterarbeit. Bin durch mit studieren.
Ich habe oben strcmp geschrieben, richtig. Das war noch aus der Idee
geboren zu sagen "readCache("Item25")". Ist aber revidiert da Käse: Man
erstelle Objekte des Typs Object item25 und übergebe die an readCache.
Resultat: Man hantiert mit Objekten die nicht so abstrakt sind wie die
bloße Adresse und man kann in dieses Objekt ein eindeutiges Token
werfen.
Ansonsten: Verkettete Liste benutz ich im moment nicht. Ich hab zwar ein
#if LinkedList drin aber das ist, wie gesagt, nur prophylaktisch als
"falls". Im moment ist es ein einfaches Array aus Pointern zu den Entrys
1
typedefstruct
2
{
3
uint8numEntries;/*! \var numEntries \brief Actual number of used entries inside the cache */
4
s_hCacheEntry*CacheTable[MAX_NUM_CACHE_ENTRIES];/*! \var CacheTable[] \brief The cache itself */
5
}s_hCache;
Punkte die man def. optimieren könnte:
- Berechnung der Position eines Items im Cache anhand eines eindeutigen
Tokens (in dem Fall die phys. reale Adresse im Speicher).
- Ggf. wegfall des Objektstructs - optional, kommt drauf an ob man ads
eine oder das andere hübscher findet ;)
- Nicht den Cache ständig umsortieren: Einsatz von einer "age-variable"
um das älteste zu identifizieren. Kann im struct CacheEntry eingeführt
werden. Um herauszufinden welches das älteste ist entweder einen
schnellen Sortieralgo einführen
Ano Nym schrieb:> - Nicht den Cache ständig umsortieren: Einsatz von einer "age-variable"> um das älteste zu identifizieren. Kann im struct CacheEntry eingeführt> werden. Um herauszufinden welches das älteste ist entweder einen> schnellen Sortieralgo einführen
Wenn du eine Age-Variable benutzt, dann hast Du zwar keinen echten LRU
Algorithmus mehr, sondern nur noch einen NFU (Not frequently used), aber
Du sparst dir das Umsortieren bzw. die verketteten Listen, die Du bei
einem LRU gebraucht hättest.
So hast Du im Fall des Schreibens in einen vollen Caches eine lineare
Suche nach dem ältesten Element.
Den Aufwand eines klassischen LRU hätte ich sowieso nie getrieben, aber
das entscheidet sich schon vor der Designphase in der Analysephase
deiner Architektur.
Warum ist die Geschichte mit dem Altern nicht mehr LRU? Recently =
jüngst. Heißt, je länger ein Eintrag nicht benutzt wird, desto "least
recently" ist er benutzt und desto älter ist er.
Was du meinst wäre das Gegenteil von Least FREQUENTLY used, dann müste
ich mir merken wie häufig ein Eintrag in Abhängigkeit der Zeit benutzt
wird --> Aufwändiger.
Ansonsten ist der Use Case im moment so, dass es Einträge die häufiger
benutzt werden und welche die weniger häufig benutzt werden, bzw. es
länger dauert bis sie wieder in Kraft treten. Ich weiß noch nicht wie
groß der Cache sein muss und wie häufig "häufig" ist. Aber vom
Grundverständnis aus der Dikussion her klingt LRU in Kombination mit
einem zeitlichen Trigger der das älteste wegwirft um Leichen zu
vermeiden Sinnvoll.
Ansonsten schien mir meine Lösung als eine gängige (man findet am
meisten dazu) und als eine weniger komplexe...
Ano Nym schrieb:> Warum ist die Geschichte mit dem Altern nicht mehr LRU? Recently => jüngst. Heißt, je länger ein Eintrag nicht benutzt wird, desto "least> recently" ist er benutzt und desto älter ist er.
Die Bedingung ist zwar notwendig für LRU aber nicht hinreichend.
Beispiel:
Bei einer Age-Variable wird z.B im Timer-Interrupt hochgezählt, wie alt
ein Eintrag ist oder man merkt sich in der Cache-Tabelle dazu einen
groben Timertick (Deshalb Age).
Aufgrund der groben ungenauen Werte, kann es vorkommen, dass zwei oder
mehr Elemente das selbe Alter haben. Deshalb kann man nicht mehr genau
sagen, welches von den n Elementen DAS jüngste Element ist (wäre
hinreichend).
Deshalb ist AGE kein echter LRU-Algorithmus. Ist auch unsinnig sowas zu
implementieren, da sich der Aufwand i.A. nicht rechnet.
Würde man jedes mal wirklich sortieren, dann wäre durch die Position der
eindeutige Zugriff bestimmt, das wäre LRU, aber dann braucht man kein
Age.
Aus diesem Grund wählt man gerne den NFU (Not Frequently Used),
basierend auf dem Alter, welcher KEIN LRU-Algorithmus sondern eine
eigene Klasse darstellt.
Ah, also wenn ich es löse wie jetzt - immer das neueste oben drauf,
alles andere eins runter rutschen- wäre es LRU aber ineffizient. Führe
ich eine Alters-Variable ein ist es NFU und es ist nicht atomar welcher
Eintrag nun wirklich der älteste/wenigsten benutzte ist.
Dann frag ich mich nun aber zwei Dinge:
- Macht das Sinn was ich da zauber?
- Warum steht im Internet bei vielen Artikeln dabei das bei LRU eine Age
Variable standard ist?
Grüeß
>Ich bin derzeit dabei einen Cache zusammenzufrickeln.>- Macht das Sinn was ich da zauber?
Frickeln oder zaubern, entscheide Dich mal ...
>- Warum steht im Internet bei vielen Artikeln dabei das bei LRU eine>Age Variable standard ist?
Entweder haben die Autoren der Artikel schlecht plagiert, wörtlich
plagieren führt immer zu besseren Noten, oder die Artikel sprechen von
einem modifizierten NFU-Algorithmus, der einem LRU praktisch nahekommt.
Beim modifizierten NFU wird nicht nur das Alter des Eintrags
gespeichert, sondern es werden auch die Zeitpunkte der letzten Zugriffe
gewichtet. Kann recht einfach Schiebeoperatoren auf Age realisiert
werden.
Andererseits könnte Age beim echten LRU auch nicht wirklich das
zeitliche Alter, sondern die Position in der Zugriffsreihen beinhalten.
Da wäre der Variablenname aber misleading.
Ich tippe aber eher auf das schlechte Plagiat.
Du meinst ads schlechte Guttenberg ;)
Frickeln meinte ich weil ichs eben schnell Rapid Prototyping mäßig mit
wenig Design im VG gebaut habe
Zaubern mein ich im gleichen Sinn^^