Sortiertes Wörterbuch sortiert nach Wert in C# (LRU-Cache)

Question

Ich möchte ein LRU cache implementieren, wo die zuletzt verwendeten Elemente asynchron gelöscht werden. Meine derzeitige Idee ist es, eine Dictionary zu verwenden, um die <key,value> Paare zu speichern und die Zeiten der Zugriffe der Objekte zu verfolgen, um eine SortedDictionary <key, timestamp> zu behalten. Die Idee ist, dass der asynchrone Thread die LRU-Elemente von SortedDictionary erhält und aus dem Cache entfernt. Aber damit dies funktioniert, muss SortedDictionary nach Wert sortiert werden, was nicht der Fall ist.

ich die {Schlüssel und Zeitstempel} sortierten für das Halt auf dem Zeitstempel ein separates SortedList anstelle die SortedDictionary verwendet haben könnte, aber dann werde ich einen „linearen“ Nachschlag für die Suche nach dem Schlüssel aus der Liste tun (wenn Ich muss den Zeitstempel aktualisieren, wenn derselbe Schlüssel wieder aufgerufen wird) - ich suche nach einem besseren als linearen Weg, wenn möglich. Kann jemand Ideen teilen, um mit diesem Problem umzugehen?

So kocht mein Problem unten zu diesem:

Ich habe Tasten in < = logn Zeit zum Nachschlagen für die Aktualisierung des Zeitstempels, während zur gleichen Zeit in der Lage die Schlüssel zu erhalten, auf dem Zeitstempel sortierte, basiert.

Ein Weg, der gedacht wurde, war, einen SortedDictionary von <{key,timestamp},null> zu behalten, der die Schlüssel bestellt, die auf dem Timestampteil von {Schlüssel, timestamp} basieren. Während das in Ordnung ist, ist das Problem hashcode() wird nur key.hashcode() (für die Suche während der Aktualisierung Zeitstempel) zurückgeben, während equals() sollte auch timestamp verwenden. Also, und hashcode() sind in Konflikt, so fühlte, dass dies keine gute Idee ist ...

Answer 1

Was Sie tun sollten, ist zwei Wörterbücher, eines nach der Zeit und eines nach Schlüsseln sortiert.

Denken Sie daran, dass Wörterbücher nur Verweise auf Ihre tatsächlichen Objekte enthalten, also spielt es keine Rolle, welches Wörterbuch Sie zum Aktualisieren des Objekts verwenden.

So aktualisieren Sie das Objekt eine Funktion erstellen, die

var oldObj = keyedObject[key]; 
timedObjects.Remove(oldObj.LastUpdateTime); 
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject); 
keyedObject[key] = myUpdatedObject; 

Jetzt Sie verfolgen das gleiche Objekt von Zeit und Schlüssel haben sowohl die Wörterbücher aktualisieren.

Ich behalte nur einen Verweis auf ein Objekt in timedObjects. Dies hilft beim Entfernen.

Sie können das TimedObjects-Wörterbuch nach Bedarf zuschneiden.

Ofcource, während des Trimmens müssen Sie bedenken, dass es ein anderes Wörterbuch gibt, das sich auf dasselbe Objekt bezieht: keyedObject. Einfach anrufen Remove wird nicht genug sein.

Ihre entfernen Code wird so sein:

removeObject = timedObjects[timeToRemove]; 
timedObjects.Remove(timeToRemove); 
keyedObject.Remove(removeObject.key); 

timeToRemove wird meist von einem kommen for-Schleife, wo Sie entscheiden, welche

Answer 2

Die Art der Karte zu entfernen Objekt, das Sie Auf der Suche nach ist (zumindest in Java) LinkedHashMap genannt.

Vom javadoc:

Hash-Tabelle und verknüpfte Liste Implementierung der Map-Schnittstelle, mit vorhersagbar Iterationsreihenfolge. Diese Implementierung unterscheidet sich von HashMap darin, dass sie eine doppelt verknüpfte Liste verwaltet, die alle ihre Einträge durchläuft. Diese verkettete Liste definiert die Iterationsreihenfolge, die normalerweise die Reihenfolge ist, in der Schlüssel in die Karte eingefügt wurden (Einfügereihenfolge).

ist ein spezieller Konstruktor bereitgestellt einen verknüpften Hash-Map, deren Reihenfolge der Iteration zu erzeugen, ist die Reihenfolge, in der die Einträgen , aus dem am wenigsten kürzlich am meisten kürzlich (Zugriffs Ordnung) zugegriffen letzten Zugriff. Diese Art von Karte ist gut geeignet für den Bau von LRU Caches.

Source for LinkedHashMap from the OpenJDK

AFAIK gibt es keine bestehenden Implementierungen eines LinkedHashMap in C#. Davon abgesehen, sollte es nicht besonders schwierig sein, einen zu schreiben.

Answer 3

Schreiben Sie anstelle von sorteddictionary Ihre eigene verknüpfte Liste und lassen Sie das Dictionary auf seine Knoten als Werte zeigen. Es wird immer nach Zeitstempel sortiert, der Zeitstempel wird aktualisiert und das zuletzt verwendete Element wird mit O (1) gelöscht.