AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Code-Kata: Cache-Klasse. Wer produziert den besten Code
Thema durchsuchen
Ansicht
Themen-Optionen

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

Ein Thema von Dejan Vu · begonnen am 30. Jul 2015 · letzter Beitrag vom 1. Aug 2015
 
idefix2

Registriert seit: 17. Mär 2010
Ort: Wien
1.027 Beiträge
 
RAD-Studio 2009 Pro
 
#19

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

  Alt 31. Jul 2015, 06:50
Uwe Raabe hat es richtig geschrieben. Es fehlt in deiner Vorgabe eine zeitliche Komponente, ohne die wird keine gute Performance herauskommen (und dein eigener Lösungsansatz ignoriert deine Vorgabe übrigens komplett, der implementiert NUR die zeitliche Komponente).
Das Problem dabei: Wenn ab irgendeinem Zeitpunkt ein anderes (ganz neues) Element als die bisher häufigsten öfter gebraucht wird, dauert es sehr lange, bis das Element im Cache gelassen wird. Zu Beginn ist die "Wahrscheinlichkeit" nahe 0, und das Element wird sehr oft hinausgeworfen (und verursacht dadurch viele cache misses), bis es aufgeholt hat und im Speicher bleiben darf. Deshalb gehört unbedingt auch der Zeitfaktor in irgendeiner Form ins Spiel, in der einfachsten Form z.B., dass ein Element, das neu in den Cache geholt wurde, bei den nächsten n (n deutlich kleiner als die Cachegrösse) Malen, die ein Element aus dem Cache fliegt, geschützt wird.

Elemente, die vor langer Zeit oft benötigt wurden, inzwischen aber längst nicht mehr, behalten nach deiner Vorgabe eine sehr hohe "Wahrscheinlichkeit". Auch dagegen gibt es ein einfaches Mittel:
Für den ganzen Cache wird eine Zugriffsnummer bei jedem Zugriff hochgezählt. Bei jedem Element, auf das zugegriffen wurde, wird zuzätzlich zur um 1 erhöhten Häufigkeit auch die Zugriffsnummer gespeichert. Dann ergibt die Zugriffsnummer des Cache minus Zugriffsnummer eines Elements sein Alter (= wie lange wurde das Element nicht gebraucht). Für die Berechnung, welches Element rausfliegt, wird dann nicht nur die Zugriffshäufigkeit hergenommen, sondern (Zugriffshäufigkeit*a-Alter*b), wobei man mit den Parametern a und b die Gewichtung der beiden Faktoren zueinander optimieren kann.

Und natürlich muss die Häufigkeit auch für die Elemente gespeichert bleiben, die schon aus dem Cache rausgeflogen sind.

Geändert von idefix2 (31. Jul 2015 um 07:07 Uhr)
  Mit Zitat antworten Zitat
 


Forumregeln

Es 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

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 17:33 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz