|
![]() |
|
Registriert seit: 7. Jun 2006 Ort: Karlsruhe 3.724 Beiträge FreePascal / Lazarus |
#1
Ich geb mal meinen Senf dazu. Bin jetzt nicht wirklich glücklich über den ganzen Boilerplate-Code, aber ich kann ja auch nichts dafür, dass es keine gescheite Standardlib gibt (oder hat Delphi inzwischen eine verkettete Liste? Habe nichts gefunden).
Habe den Code nicht getestet, da ich kein Delphi mehr habe, also habe ich bestimmt irgendwo was übersehen. Aber es geht ja eher um den Ansatz, denke ich. Ein paar Worte zu meinen Designentscheidungen: - Ich habe es jetzt mal so interpretiert, dass es ein einfacher MRU-Cache sein soll. - Ich prüfe nicht explizit ob die Aufrufe gültig sind (z.B. ob bei Get der Key auch wirklich existiert) und werfe daher auch keine Exceptions. Denn offensichtlich ist die Schnittstelle so angelegt, dass der Benutzer vorher selbst mit Contain prüfen soll, ob der Key existiert. Wenn die Klasse selber es dann noch mal prüfen würde, würde doppelt geprüft. Deswegen habe ich die Prüfungen nur als nur Assertions drin. Die ganze Schnittstelle ist meiner Meinung nach nicht optimal (die von TDictionary übrigens auch nicht), aber war ja so vorgegeben, also muss man das beste daraus machen. - Edit: Achso, und falls sich jemand wundert: Ich verwende grundsätzlich (fast) nie private sondern immer protected (bis auf sehr wenige Ausnahmen, bei denen es wirklich gute Gründe gibt, die dagegen sprechen). Könnt ihr meinetwegen schlecht finden, ist mir aber egal ![]()
Delphi-Quellcode:
{ TLinkedListItem }
TLinkedListItem<T> = class protected FValue: T; FPrev: TLinkedListItem<T>; FNext: TLinkedListItem<T>; public constructor Create; constructor Create(Value: T); property Value: T read FValue write FValue; property Next: TLinkedListItem<T> read FNext; property Prev: TLinkedListItem<T> read FPrev; end; { TLinkedList } TLinkedList<T> = class protected FSentinel: TLinkedListItem<T>; function GetFirst: TLinkedListItem<T>; function GetLast: TLinkedListItem<T>; public constructor Create; destructor Destroy; override; procedure InsertBefore(Item: TLinkedListItem<T>; Successor: TLinkedListItem<T>); function Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>; property First: TLinkedListItem<T> read GetFirst; property Last: TLinkedListItem<T> read GetLast; end; { TCache } TCache = class protected type TKeyValuePair = record Key: Integer; Value: TObject; end; TCacheItem = TLinkedListItem<TKeyValuePair>; TCacheItemList = TLinkedList<TKeyValuePair>; protected FMaxSize: Integer; FMRU: TCacheItemList; FMap: TDictionary<Integer, TCacheItem>; function GetCurrentNumberOfElements: Integer; function GetSize: Integer; function MakePair(Key: Integer; Value: TObject): TKeyValuePair; procedure Bump(Item: TCacheItem); procedure Evict(Item: TCacheItem); public constructor Create(MaxSize: Integer); destructor Destroy; override; function Contains(ID: Integer): Boolean; function Get(ID: Integer): TObject; procedure Put(ID: Integer; Item: TObject); procedure Remove(ID: Integer); property MaxSize: Integer Read FMaxSize; property CurrentNumberOfElements : Integer Read GetCurrentNumberOfElements; end; implementation { TLinkedListItem } constructor TLinkedListItem<T>.Create; begin FNext := Self; FPrev := Self; end; constructor TLinkedListItem<T>.Create(Value: T); begin Create; Self.Value := Value; end; { TLinkedList } constructor TLinkedList<T>.Create; begin FSentinel := TLinkedListItem<T>.Create; end; destructor TLinkedList<T>.Destroy; override; begin FSentinel.Free; end; function TLinkedList<T>.GetFirst: TLinkedListItem<T>; begin Result := FSentinel.Next; end; function TLinkedList<T>.GetLast: TLinkedListItem<T>; begin Result := FSentinel.Prev; end; procedure TLinkedList<T>.InsertBefore(Item: TLinkedListItem<T>; Successor: TLinkedListItem<T>); begin Extract(Successor); Item.Next := Successor; Item.Prev := Successor.Prev; Item.Next.Prev := Item; Item.Prev.Next := Item; end; function TLinkedList<T>.Extract(Item: TLinkedListItem<T>): TLinkedListItem<T>; begin Item.Prev.Next := Item.Next; Item.Next.Prev := Item.Prev; Item.Prev := Item; Item.Next := Item; Result := Item; end; { TCache } constructor TCache.Create(MaxSize: Integer); begin FMaxSize := MaxSize; FMap := TDictionary<Integer, TCacheItem>.Create; FMRU := TCacheItemList.Create; end; destructor TCache.Destroy; override; begin while (NumberCurrentNumberOfElements > 0) do Evict(FMRU.First); FMRU.Free; FMap.Free; end; function TCache.GetCurrentNumberOfElements: Integer; begin Result := FMap.Count; end; function TCache.MakePair(Key: Integer; Value: TObject): TKeyValuePair; begin Result.Key := Key; Result.Value := Value; end; procedure TCache.Bump(Item: TCacheItem); begin FMRU.InsertBefore(CacheItem, FMRU.First); end; procedure TCache.Evict(Item: TCacheItem); begin FMap.Remove(CacheItem.Value.Key); FMRU.Extract(CacheItem); CacheItem.Value.Value.Free; CacheItem.Free; end; function TCache.Contains(ID: Integer): Boolean; begin Result := FMap.ContainsKey(ID); end; function TCache.Get(ID: Integer): TObject; var CacheItem: TCacheItem; begin Assert(Contains(ID)); CacheItem := FMap[ID]; Bump(CacheItem); Result := CacheItem.Value.Value; end; procedure TCache.Put(ID: Integer; Item: TObject); var CacheItem: TCacheItem; begin Assert(not Contains(ID)); if GetCurrentNumberOfElements >= FMaxSize then Evict(FMRU.Last); CacheItem := TCacheItem.Create(MakePair(ID, Item)); FMap[ID] := CacheItem; Bump(CacheItem); end; procedure TCache.Remove(ID: Integer); begin Assert(Contains(ID)); Evict(FMap[ID]); end; Geändert von Namenloser (31. Jul 2015 um 20:53 Uhr) |
![]() |
Registriert seit: 17. Mär 2010 Ort: Wien 1.027 Beiträge RAD-Studio 2009 Pro |
#2
Hier mein erster Versuch.
Das Interface der Klasse habe ich bewusst etwas anders gestaltet als in der Vorgabe: Die Klasse kümmert sich sowohl umd das Nachladen von Objekten aus dem externen Speicher als auch um das externe Speichern veränderter Daten. Dazu müssen ihr beim Create zwei Routinen übergeben werden, die das Laden und Speichern der Daten erledigen. Das Programm, das den Cache dann verwendet, holt alle Daten aus der Cache Klasse und schreibt Veränderungen auch nur in die Cache Klasse. Für die aktuellen Cacheelemente sollte wohl zusätzlich noch eine nach dem "Hinauswurfkriterium" sortierte Liste verwaltet werden (oder sogar statt des TDictionary, aber dadurch würde das Auffinden der im Cache vorhandenen Elemente wieder langsamer), damit man nicht alle Elemente durchgehen muss, wenn ein Element aus dem Cache zu entfernen ist, um herauszufinden, welches weggehört. Eine einfache verkettete Liste, wie sie namenloser in seinem Algorithmus verwendet, bringt nicht viel, weil man dann die verkettete Liste trotzdem immer durchgehen muss, um das an Stelle des hinausgeworfenen Elements hinzukommende neue Element an der richtigen Stelle einzufügen, das ist nämlich auch nicht unbedingt am Ende der Liste. Die gespeicherte Zugriffshäufigkeit eine Elements wird beim Entfernen des Elements aus dem Cache halbiert, damit sich uralte hohe Zugriffshäufigkeiten weniger stark auswirken.
Delphi-Quellcode:
unit CacheUnit;
interface uses Generics.Collections; Type // Callback zum Laden eines externen Objekts, wenn es noch nicht im Cache ist TLoadFunction = function (key: integer): TObject; // Callback zum externen Speichern eines Objekts TSaveFunction = procedure (key: integer; Obj: TObject); TCache = Class type TItem = record LastAccess: integer; AccessCount: integer; end; private FCurrentSize: Integer; FCache: array of TObject; FWeightTime: integer; FWeightFrequency: integer; FLoadObject: TLoadfunction; FSaveObject: TSavefunction; FCurrentAccess: integer; FAllItems: TDictionary<integer,TItem>; // enthält Nutzungsdaten der Elemente FCachedItems: TDictionary<integer,integer>; // Enthält Index der Elemente im Cache FHitCount: integer; FReadCount: integer; function GetMaxSize: integer; function FindPlaceInCache: integer; procedure RegisterAccess(ID: integer); function GetHitPercentage: integer; public Constructor Create (MaxSize : Integer; WeightTime, WeightFrequency: integer; LoadObject: TLoadfunction; SaveObject: TSaveFunction); Destructor Destroy; Function Get (ID : Integer) : TObject; Procedure Put (ID : Integer; Obj : TObject); Property MaxSize : Integer Read GetMaxSize; Property CurrentNumberOfElements : Integer Read FCurrentSize; Property HitPercentage: integer Read GetHitPercentage; end; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // implementation // //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// constructor TCache.Create(MaxSize: Integer; WeightTime, WeightFrequency: integer; LoadObject: TLoadFunction; SaveObject: TSaveFunction); begin inherited create; SetLength(FCache,MaxSize); FLoadObject := LoadObject; FSaveObject := SaveObject; FAllItems := TDictionary<integer,TItem>.Create; FCachedItems := TDictionary<integer,integer>.Create; FWeightTime:= WeightTime; FWeightFrequency:= WeightFrequency; end; destructor TCache.destroy; begin FCachedItems.free; FAllItems.free; inherited; end; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // // TCache.GetMaxSize und GetHitPercentage // //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// function TCache.GetMaxSize: integer; begin Result:=Length(FCache); end; function TCache.GetHitPercentage: integer; begin if FReadCount=0 then Result:=0 else Result:=FHitCount * 100 div FReadCount; end; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // // Platz im Cache finden und nötigenfalls freimachen // //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// function TCache.FindPlaceInCache: integer; var Key, KeyToRemove: integer; Worst,Kriterium: integer; Item: TItem; begin if FCurrentSize<Length(FCache) // noch Platz im Cache then begin result:=FCurrentSize; inc(FCurrentSize); exit end; Worst:=FCurrentAccess*FWeightFrequency; for Key in FCachedItems.Keys do begin with FAllItems[Key] do Kriterium:=AccessCount*FWeightFrequency-(FCurrentAccess-LastAccess)*FWeightTime; if Kriterium<Worst then begin Worst:=Kriterium; KeyToRemove:=key; Result:=FCachedItems[key]; end; end; FCachedItems.Remove(KeytoRemove); Item:=FAllItems[KeyToRemove]; Item.AccessCount:=Item.AccessCount div 2; FAllItems.AddOrSetValue(KeyToRemove,Item); end; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// // // TCache.Get und Put // //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// procedure TCache.RegisterAccess(ID: integer); var item: TItem; begin inc(FCurrentAccess); if FAllItems.ContainsKey(ID) then begin item:=FAllItems[ID]; inc(Item.AccessCount) end else item.Accesscount:=1; item.LastAccess:=FCurrentAccess; FAllItems.AddOrSetValue(ID,Item); end; function TCache.Get(ID: Integer): TObject; var idx: integer; begin inc(FReadCount); if FCachedItems.TryGetValue(ID, idx) then inc(FHitCount) else begin idx:=FindPlaceInCache; FCache[idx]:=FLoadObject(ID); FCachedItems.Add(ID,idx); end; RegisterAccess(ID); Result:=FCache[idx]; end; procedure TCache.Put(ID: Integer; Obj: TObject); var idx: integer; begin FSaveObject(ID, Obj); inc(FCurrentAccess); if not FCachedItems.TryGetValue(ID, idx) then begin idx:=FindPlaceInCache; FCachedItems.Add(ID,idx) end; FCache[idx]:=Obj; RegisterAccess(ID); end; end. |
![]() |
Registriert seit: 7. Jun 2006 Ort: Karlsruhe 3.724 Beiträge FreePascal / Lazarus |
#3
Für die aktuellen Cacheelemente sollte wohl zusätzlich noch eine nach dem "Hinauswurfkriterium" sortierte Liste verwaltet werden (oder sogar statt des TDictionary, aber dadurch würde das Auffinden der im Cache vorhandenen Elemente wieder langsamer), damit man nicht alle Elemente durchgehen muss, wenn ein Element aus dem Cache zu entfernen ist, um herauszufinden, welches weggehört. Eine einfache verkettete Liste, wie sie namenloser in seinem Algorithmus verwendet, bringt nicht viel, weil man dann die verkettete Liste trotzdem immer durchgehen muss, um das an Stelle des hinausgeworfenen Elements hinzukommende neue Element an der richtigen Stelle einzufügen, das ist nämlich auch nicht unbedingt am Ende der Liste.
|
![]() |
Registriert seit: 17. Mär 2010 Ort: Wien 1.027 Beiträge RAD-Studio 2009 Pro |
#4
Ich spreche von meinem Algorithmus.
Du hast einen einfachen MRU (laut inzwischen modifizierter Vorgabe, im Eingangspost war etwas anderes verlangt) implementiert, da braucht man das natürlich nicht. Geändert von idefix2 ( 1. Aug 2015 um 08:43 Uhr) |
![]() |
Registriert seit: 7. Jun 2006 Ort: Karlsruhe 3.724 Beiträge FreePascal / Lazarus |
#5
Ich spreche von meinem Algorithmus.
Du hast einen einfachen MRU (laut inzwischen modifizierter Vorgabe, im Eingangspost war etwas anderes verlangt) implementiert, da braucht man das natürlich nicht. Aber wenn ich so drüber nachdenke, müsste sich der Ansatz mit der verketteten Liste auch für beliebige Sortierungen erweitern lassen. Denn das schöne ist ja, wenn wir das Element gecached haben, kennen wir automatisch die Position bzw. das Glied in der Liste. Dann müssen wir nach dem Updaten des Scores also nur schauen ob das „linke“ (vorherige) Element einen schlechteren Score hat und solange das geupdatete Element nach links verschieben, bis die Sortierung wieder stimmt (wie bei Insertion-Sort). Ist im Worst-Case zwar auch O(n), aber im Best-Case O(1). Es wird auf jeden Fall schneller sein als jedes mal alle Keys zu durchlaufen wie aktuell bei dir. ![]() Gegenvorschlag?
Delphi-Quellcode:
TCache = Class;
TCacheHandle = class protected FParent: TCache; { ... } public property IsNull: Boolean; property ID: Integer; property Value: TObject; procedure Put(Value: TObject); procedure Remove; end; TCache = class protected { ... } public function GetHandle(ID: Integer): TCacheHandle; // Sonst keine öffentlichen Methoden end; ![]() Welche Gründe sprechen gegen private Felder? Properties sehe ich ein, aber Felder sollten so strict private sein, wie es nur geht.
Ich habe bei private einfach die Erfahrung gemacht, dass man oft im Laufe der Zeit mehr und mehr Dinge doch noch protected macht, weil sich Nutzungsmöglichkeiten ergeben, die man am Anfang nicht vorhergesehen hat. Auch bei der VCL/RTL habe ich mich schon oft aufgeregt, dass Sachen sinnloserweise private waren und ich dann deshalb Code kopieren musste (Gruß an himitsu an dieser Stelle). Deswegen habe ich mir einfach angewöhnt: Im Zweifel für protected. Weil man sich da seltener was verbaut. Protected heißt bei mir daher aber auch immer ein bisschen „Use at your own risk“. Also bloß, weil man auf protected Felder zugreifen kann, heißt es nicht, dass man es unbedingt sollte. Da muss man eben Vernunft walten lassen. In Python gibt es übrigens gar kein private. Dort gibt es nur die Konvention, dass Variablen, die mit einem _ beginnen, tabu sind. Es wird sich eben darauf verlassen, dass der Programmierer sich daran hält, aber wer sich unbedingt in den Fuß schießen will, kann es tun. So ähnlich halte ich es auch. ![]() Das 'MakePair' würde ich dem TKeyValuePair als Create spendieren. Gehört -finde ich- dorthin.
![]() Aber wieso gibst Du dort auch das 'Value' frei? Das ist doch das zu cachende Objekt? Damit hat doch der Cache nix am Hut. Oder hab ich mich verlesen?
![]() 'Bump' und 'Evict' sind für mich ungewöhnliche Begriffe. Ich würde zumindest 'Bump' anders benennen.
Aber wie heißt es so schön: „There are only two hard things in Computer Science: cache invalidation and naming things.“ Passt ja auch sonst zu diesem Thread. ![]() Geändert von Namenloser ( 1. Aug 2015 um 10:51 Uhr) |
![]() |
Ansicht |
![]() |
![]() |
![]() |
ForumregelnEs ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus. Trackbacks are an
Pingbacks are an
Refbacks are aus
|
|
Nützliche Links |
Heutige Beiträge |
Sitemap |
Suchen |
Code-Library |
Wer ist online |
Alle Foren als gelesen markieren |
Gehe zu... |
LinkBack |
![]() |
![]() |