Ordinato dizionario ordinato sul valore in C# (cache LRU)

Question

Desidero implementare uno LRU cache, dove elementi utilizzati meno di recente verranno eliminati in modo asincrono. La mia idea attuale è di usare un Dictionary per memorizzare le coppie <key,value> e per tenere traccia dei tempi di accesso degli oggetti, per mantenere un SortedDictionary <key, timestamp>. L'idea è per il thread asincrono per ottenere gli elementi LRU dal SortedDictionary e rimuoverli dalla cache. Ma per fare questo, SortedDictionary ha bisogno di ordinare per valore, che non è così.

Avrei potuto utilizzare uno SortedList separato anziché lo SortedDictionary per mantenere la {chiave e la data/ora} ordinati per la data/ora, ma poi dovrò fare una ricerca "lineare" per trovare la chiave dall'elenco (quando Devo AGGIORNARE il timestamp, quando si accede nuovamente alla stessa chiave) - Sto cercando un modo migliore di quello lineare, se possibile. Qualcuno può condividere idee per affrontare questo problema?

Quindi, il mio problema si riduce a questo:

ho di ricercare chiavi in ​​< = tempo logn per l'aggiornamento del timestamp, mentre allo stesso tempo in grado di ottenere le chiavi ordinati in base ai timestamp.

Un modo per pensare era mantenere uno SortedDictionary di <{key,timestamp},null> che ordina le chiavi in ​​base alla parte timestamp di {chiave, timestamp}. Mentre questo va bene, il problema è hashcode() dovrà solo restituire key.hashcode() (per la ricerca durante l'aggiornamento di timestamp), mentre equals() dovrebbe utilizzare anche timestamp. Quindi, equals() e sono in conflitto, quindi sentivo che questa non è una buona idea ...

Answer 1

Quello che dovresti fare è tenere due dizionari, uno ordinato per ora e uno per chiavi.

Ricorda che i dizionari contengono solo riferimenti ai tuoi oggetti reali, quindi il dizionario che usi per aggiornare l'oggetto non ha importanza.

per aggiornare l'oggetto creare una funzione che aggiornerà sia i dizionari

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

ora avete traccia dello stesso oggetto da tempo e chiave.

Sto mantenendo un solo riferimento a un oggetto in timedObjects. Questo aiuta durante la rimozione.

È possibile continuare a ritagliare il dizionario TimedObjects come richiesto.

Ofcource, mentre si esegue il taglio si deve tenere presente che esiste un altro dizionario keyedObject che ha riferimento allo stesso oggetto. Chiamare semplicemente Remove non sarà sufficiente.

Il codice di rimozione dovrà essere simile a questo:

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

timeToRemove saranno per lo più provengono da un ciclo for, dove si decide quale oggetto per rimuovere

Answer 2

Il tipo di carta si è cercare è (almeno in Java) chiamato LinkedHashMap.

Dal javadoc:

tabella di hash e l'attuazione lista collegata dell'interfaccia Map, con ordine di iterazione prevedibile. Questa implementazione differisce da HashMap in quanto mantiene una lista doppiamente collegata che attraversa tutte le sue voci . Questo elenco collegato definisce l'ordine di iterazione, che è normalmente l'ordine in cui le chiavi sono state inserite nella mappa (ordine di inserzione).

Un costruttore speciale è previsto per creare una mappa hash legata cui ordine di iterazione è l'ordine in cui le voci loro ultima accessibile, da meno di recente accedere a più di recente (accesso ordine). Questo tipo di mappa è adatto per la costruzione di cache LRU .

Source for LinkedHashMap from the OpenJDK

per quanto ne so, non ci sono implementazioni esistenti di un LinkedHashMap in C#. Detto questo, non dovrebbe essere terribilmente difficile scriverne uno.

Answer 3

Invece di ordinamento automatico, scrivere il proprio elenco collegato e fare in modo che il Dizionario punti ai suoi nodi come valori. Sarà sempre ordinato per data/ora, aggiornando la data/ora e rimuovendo l'elemento meno utilizzato in modo permanente sarà O (1).