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

[Mavarik]

Zitat:

Zitat von Der schöne Günther (Beitrag 1310282)

Was seid ihr alle so schnell? Ich hätte immer häppchenweise was daran gemacht und wäre frühestens zum Wochenende fertig :o

Zu schnell... Auf jeden Fall...

Darf das Vorgabe Objekt auch umgestellt werden? Es ist für mich vom System schon falsch...
Wer will schon ein Cache den er "per Hand" ansprechen muss...

Der Cache sollte so funktionieren, dass er bei Ansprache eines Objectes automatisch arbeiten kann...

[TiGü]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310281)

Zitat:

Zitat von TiGü (Beitrag 1310276)

Auch wenn ich weiß, dass nicht alle Anforderungen erfüllt sind, will ich doch einen ersten Versuch posten.

Dein Ansatz hat aber ein paar klitzekleine Denkfehler:

Logo, so wirklich gelöst ist das natürlich nicht.

Am einfachsten würde ich das so lösen: Die Systems.Generics.Collections.TDictionary-Klasse nehmen, kopieren und alles Generische entfernen, damit es mit Delphi 7 kompilierbar wird.
An den Stellen (z. B. Add), wo auf den FGrowThreshold geprüft wird, zusätzlich die MaxSize mit ins Spiel bringen.

Fragen:
Was soll passieren, wenn die MaxSize erreicht wird und man weitere Elemente hinzufügt? Solls eine Exception geben?
Was soll passieren, wenn ich das selbe (!) Objekt unter verschiedenen Schlüsseln hinzufüge?
Welches Element soll eigentlich zurückgeben werden, wenn ich hinter einen Schlüssel 2..N Elemente gespeichert habe?

Ich verlange auch einen Testfall!

[Uwe Raabe]

Zitat:

Zitat von TiGü (Beitrag 1310288)

damit es mit Delphi 7 kompilierbar wird.

Ist das etwa eine Vorgabe? :shock:

[TiGü]

Zitat:

Zitat von Uwe Raabe (Beitrag 1310290)

Zitat:

Zitat von TiGü (Beitrag 1310288)

damit es mit Delphi 7 kompilierbar wird.

Ist das etwa eine Vorgabe? :shock:

Habe ich wegen folgenden Satz und dem Profil von Dejan Vu mal angenommen:

Zitat:

Zitat von Dejan Vu (Beitrag 1310261)

Obwohl so eine Klasse nach Generics schreit, wollen wir darauf verzichten und als ID-Type einen Integer verwenden. Der Cache soll beliebige TObject-Referenzen verwalten.

[TRomano]

In der Praxis würde ich auch ein TDictionary nehmen und die Größe halt im Code auf MaxSize begrenzen. Ich würde auch nebenbei eine Statistik mit den den Aufrufen (Hits) führen und nur bei Überschreitung von MaxSize das Element mit den wenigsten Hits löschen, um das neue einzufügen. Ist aber vielleicht am Thema vorbei ...

[BUG]

Zitat:

Zitat von TRomano (Beitrag 1310294)

Ich würde auch nebenbei eine Statistik mit den den Aufrufen (Hits) führen und nur bei Überschreitung von MaxSize das Element mit den wenigsten Hits löschen, um das neue einzufügen. Ist aber vielleicht am Thema vorbei ...

Das ist eben die Frage: Geht es hier nur um die saubere Umsetzung von Cache-Verdrängungsstrategien oder auch um deren Auswahl. Für das zweite gibt es Unmengen an wissenschaftlicher Literatur. Afaik geht das aber an der Zielstellung von so einem Kata vorbei :gruebel:
Vielleicht sollte man eine Strategie vorgeben.

[Stevie]

[OT] Fiel mir grad so ein, als ich das hier las: http://martinfowler.com/bliki/TwoHardThings.html [/OT]

[Dejan Vu]

Wo hast Du das denn schon wieder her :lol:

Ich hatte meinen Ansatz mit der MRU-Strategie ('Most Recently Used') umgesetzt, so wie sie im SQL-Server zum Einsatz kommt. Sie ist verblüffend einfach.

In einer Dictionary werden die gecachten Objekte vorgehalten. Zusätzlich sind sie in einer verketteten Liste verbunden. Wird der Cache zu voll, werden die Items, die am Ende der Liste sind, entfernt (aus der Liste und dem Dictionary).

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

Das kann man dann alles wunderbar testen.

Bezüglich der 'Vorgaben'... Ich habe einfach mal angefangen. Und der kleinste Nenner wäre etwas ohne Generics. Ich denke, eine entsprechende Implementierung ist davon unabhängig, aber sinnvoller wäre natürlich eine, die wirklich wiederverwendbar wäre, und das geht nun mal nur mit Generics.

Bezüglich der Testsuite... Das wäre wirklich optimal, aber ich hab keine ;-(

Ich poste später vielleicht meinen Ansatz. Nur sitze ich bei 36°C und da denkt man nicht direkt daran, alten Code rauszukramen und zu reinigen.

[idefix2]

Zitat:

Zitat von Mavarik (Beitrag 1310284)

Zu schnell... Auf jeden Fall...

Darf das Vorgabe Objekt auch umgestellt werden? Es ist für mich vom System schon falsch...
Wer will schon ein Cache den er "per Hand" ansprechen muss...

Der Cache sollte so funktionieren, dass er bei Ansprache eines Objectes automatisch arbeiten kann...

Ja, das sehe ich auch so.
Beim Zugriff auf ein Element, das nicht im Cache ist, sollte das Nachladen meines Erachtens durch die Klasse selbst erledigt werden - z.B. durch eine Callback-Routine, die beim Create übergeben wird.

[Uwe Raabe]

Zitat:

Zitat von Dejan Vu (Beitrag 1310417)

Wenn ein Item eingefügt wird, kommt es an den Anfang der Liste. Ebenso, wenn ein Item abgefragt wird.
So enthält die Liste vorne die Elemente, die in der Tendenz öfter oder vor kurzem abgefragt wurden und hinten sind eher die Elemente, die schon länger keine Sau mehr interessieren. Und das sind dann genau die, die verschwinden.

So in der Art wäre auch mein Ansatz gewesen, bis ich realisierte, daß er gegen die Vorgabe verstößt (weshalb steht etwas weiter vorn im Thread). Schreib doch die Vorgabe einfach um:

Zitat:

Der Cache soll die maximal N zuletzt verwendeten Elemente im Speicher halten.

Der Satz mit Wahrscheinlichkeit und häufiger kann dann entfallen. Damit ist die Cache-Strategie klar definiert und es kommt nur noch auf die Implementierung an.