Gibt es eine TestSuite, die die Korrektheit der Klasse an sich und die Einhaltung der Vorgaben überprüft?
Gerade bei der Forderung
Zitat:
Dabei soll die Wahrscheinlichkeit eines Treffers im Cache umso höher sein, je häufiger ich ein Element verwende.
sehe ich eine gewisse Problematik für die Implementation. Nehmen wir mal die maximale Anzahl der Elemente im Cache mit 10 an und jedes Element ist über 100x verwendet worden. Jetzt wird ein elftes Element "X" angefordert und kommt in den Cache (Put). Dafür muss eines der vorhandenen 10 Elemente (nennen wir es "Y") aber weichen. Nun haben wir den Fall, daß Element X im Cache ist, obwohl es nur einmal verwendet wurde, Element Y trotz seiner über 100 Verwendungen aber nicht. Das widerspricht eindeutig der Forderung, nach der Element X wegen der geringeren Verwendung gar nicht in den Cache gehört.
Man kann sich jetzt mindestens zwei Szenarien vorstellen:
- Element Y wird nicht mehr gebraucht, X aber schon
- Die Elemente X und Y werden gleichmäßig verwendet
Im Fall von 1 würde das Rauswerfen von Y und das Aufnehmen von X passen. Bei Fall 2 wird es wohl eine Art Ping-Pong zwischen X und Y geben, bei dem das eine Element das andere immer wieder rausschmeisst, solange die anderen Cache-Bewohner eine höhere Verwendungszahl aufweisen. Die obige Betrachtung kann analog auf die anderen Cache-Bewohner erweitert werden.
Die Forderung, daß die Treffer-Wahrscheinlichkeit mit der Häufigkeit der Verwendung (in der Vergangenheit) gekoppelt wird, kann also zu einer erheblichen Degradation des Cache führen. Hier fehlt irgendwie noch eine Zeitkomponente.