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.
Achso, war wohl noch zu früh.
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.
Zitat von
Dejan Vu:
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;
Zitat von
Dejan Vu:
Welche Gründe sprechen gegen private Felder? Properties sehe ich ein, aber Felder sollten so strict private sein, wie es nur geht.
Ja, da hast du recht, es wäre sauberer, die Felder private zu machen und über eine protected property Zugriff darauf zu gewähren. Bin aber meistens zu faul dazu und es bläht mir den Code zu sehr auf.
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.
Zitat von
Dejan Vu:
Das 'MakePair' würde ich dem TKeyValuePair als Create spendieren. Gehört -finde ich- dorthin.
Habe ich auch schon oft so gemacht, als static class function. Aber damals gab es noch keine echten Konstruktoren von records, und das hat sich in neueren Delphi-Versionen ja glaube ich geändert. Ich wollte da lieber nichts verwenden, was ich nicht kenne.
Zitat von
Dejan Vu:
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?
Habe das so gemacht, weil TCache keinen OnRemove-Handler hat.
Zitat von
Dejan Vu:
'Bump' und 'Evict' sind für mich ungewöhnliche Begriffe. Ich würde zumindest 'Bump' anders benennen.
Also Evict ist glaube ich schon ein Standardbegriff, Bump vielleicht eher nicht. Habe da irgendwie an Internetforen gedacht.
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.
