Welche Datenstruktur sollte ich für diese Caching-Strategie verwenden?

Ich arbeite an einer .NET 4.0-Anwendung, die eine ziemlich teure Berechnung für zwei Doubles durchführt, die ein Double zurückgeben. Diese Berechnung wird für jedes von mehreren tausend Elementen durchgeführt . Diese Berechnungen werden in Taskeinem Threadpool-Thread ausgeführt.

Einige vorläufige Tests haben gezeigt, dass dieselben Berechnungen immer wieder durchgeführt werden, daher möchte ich n Ergebnisse zwischenspeichern. Wenn der Cache voll ist, möchte ich das am wenigsten häufig verwendete Element wegwerfen . ( Bearbeiten: Ich habe festgestellt, dass es am seltensten keinen Sinn macht, denn wenn der Cache voll ist und ich ein Ergebnis durch ein neu berechnetes ersetzen würde, würde dieses am seltensten verwendet und beim nächsten Berechnen eines neuen Ergebnisses sofort ersetzt und zum Cache hinzugefügt)

Um dies zu implementieren, dachte ich darüber nach, eine Dictionary<Input, double>(wo Inputeine Miniklasse wäre, in der die beiden Eingabedoppelwerte gespeichert werden) zu verwenden, um die Eingaben und die zwischengespeicherten Ergebnisse zu speichern. Ich müsste jedoch auch nachverfolgen, wann ein Ergebnis das letzte Mal verwendet wurde. Dafür würde ich wahrscheinlich eine zweite Sammlung benötigen, in der die Informationen gespeichert sind, die ich benötige, um ein Ergebnis aus dem Diktat zu entfernen, wenn der Cache voll ist. Ich bin besorgt, dass eine ständige Sortierung dieser Liste die Leistung beeinträchtigen würde.

Gibt es eine bessere (dh performantere) Möglichkeit, dies zu tun, oder vielleicht sogar eine gemeinsame Datenstruktur, die mir nicht bekannt ist? Welche Art von Dingen sollte ich profilieren / messen, um die Optimalität meiner Lösung zu bestimmen?

Wenn Sie einen LRU-Räumungscache (am wenigsten kürzlich verwendete Räumung) verwenden möchten, ist wahrscheinlich eine gute Kombination der zu verwendenden Datenstrukturen:

• Zirkuläre verknüpfte Liste (als Prioritätswarteschlange)
• Wörterbuch

Deshalb:

• Die verknüpfte Liste hat eine Einfüge- und Entfernungszeit von O (1)
• Listenknoten können wiederverwendet werden, wenn die Liste voll ist und keine zusätzlichen Zuordnungen durchgeführt werden müssen.

So sollte der grundlegende Algorithmus funktionieren:

Die Datenstrukturen

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. Eingabe wird empfangen
2. Wenn das Wörterbuch den Schlüssel enthält
   • Geben Sie den im Knoten gespeicherten Wert zurück und verschieben Sie den Knoten an den Anfang der Liste
3. Wenn das Wörterbuch den Schlüssel nicht enthält
   • Berechnen Sie den Wert
   • Speichern Sie den Wert im letzten Knoten der Liste
   • Wenn der letzte keinen Wert hat, entfernen Sie den vorherigen Schlüssel aus dem Wörterbuch
   • Bewegen Sie den letzten Knoten an die erste Position.
   • Speichern Sie im Wörterbuch das Schlüsselwertpaar (Eingabe, Knoten).

Einige Vorteile dieses Ansatzes sind, dass das Lesen und Setzen eines Wörterbuchwerts sich O (1) nähert, das Einfügen und Entfernen eines Knotens in eine verknüpfte Liste O (1) ist, was bedeutet, dass sich der Algorithmus O (1) zum Lesen und Schreiben von Werten nähert in den Cache und vermeidet Speicherzuweisungen und blockiert Speicherkopiervorgänge, wodurch er aus Speichersicht stabil wird.

Angesichts der Rechenleistung, die Ihnen in einem durchschnittlichen PC zur Verfügung steht, scheint dies ein großer Aufwand für eine einzelne Berechnung zu sein. Außerdem haben Sie immer noch die Kosten für den ersten Aufruf Ihrer Berechnung für jedes eindeutige Wertepaar, sodass 100.000 eindeutige Wertepaare immer noch mindestens _n * 100.000 Zeit kosten . Bedenken Sie, dass der Zugriff auf Werte in Ihrem Wörterbuch wahrscheinlich langsamer wird, wenn das Wörterbuch größer wird. Können Sie garantieren, dass die Zugriffsgeschwindigkeit Ihres Wörterbuchs ausreicht, um eine angemessene Rendite gegenüber der Geschwindigkeit Ihrer Berechnung zu erzielen?

Unabhängig davon klingt es so, als müssten Sie wahrscheinlich überlegen, wie Sie Ihren Algorithmus optimieren können. Dazu benötigen Sie ein Profiling-Tool wie Redgate Ants, um festzustellen, wo die Engpässe liegen, und um festzustellen, ob es Möglichkeiten gibt, den Overhead zu reduzieren, den Sie möglicherweise im Zusammenhang mit Klasseninstanziierungen, Listenüberquerungen und Datenbanken haben Zugriffe oder was auch immer Sie so viel Zeit kostet.

Ein Gedanke ist, warum nur Cache n Ergebnisse? Selbst wenn n 300.000 ist, würden Sie nur 7,2 MB Speicher verwenden (zuzüglich aller zusätzlichen Daten für die Tabellenstruktur). Das setzt natürlich drei 64-Bit-Doubles voraus. Sie können Memoization einfach auf die komplexe Berechnungsroutine selbst anwenden, wenn Sie nicht befürchten, dass Ihnen der Speicherplatz ausgeht.

Der Ansatz mit der zweiten Sammlung ist in Ordnung. Es sollte sich um eine Prioritätswarteschlange handeln , mit der Min-Werte schnell gefunden / gelöscht und Prioritäten innerhalb der Warteschlange geändert (erhöht) werden können (letzterer Teil ist der schwierige Teil, der von den meisten einfachen Implementierungen der Prio-Warteschlange nicht unterstützt wird). Die C5-Bibliothek hat eine solche Sammlung, heißt sie IntervalHeap.

Oder natürlich können Sie versuchen, Ihre eigene Sammlung aufzubauen, so etwas wie eine SortedDictionary<int, List<InputCount>>. ( InputCountmuss eine Klasse sein, die Ihre InputDaten mit Ihrem CountWert kombiniert )

Das Aktualisieren dieser Sammlung beim Ändern Ihres Zählwerts kann durch Entfernen und erneutes Einfügen eines Elements implementiert werden.

Wie in der Antwort von Peter Smith ausgeführt, wird das Muster, das Sie implementieren möchten, als Memoisierung bezeichnet . In C # ist es ziemlich schwierig, Memoization auf transparente Weise ohne Nebenwirkungen zu implementieren. Oliver Sturms Buch über funktionale Programmierung in C # bietet eine Lösung (der Code steht zum Download zur Verfügung, Kapitel 10).

In F # wäre es viel einfacher. Natürlich ist es eine große Entscheidung, eine andere Programmiersprache zu verwenden, aber es kann sich lohnen, darüber nachzudenken. Insbesondere bei komplexen Berechnungen ist das Programmieren einfacher als das Auswendiglernen.