Code-Kata: Cache-Klasse. Wer produziert den besten Code

[idefix2]

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.