Diccionario ordenado según el valor en C# (caché LRU)

Question

Deseo implementar un LRU cache, donde los elementos utilizados menos recientemente se expulsarán de forma asincrónica. Mi idea actual es usar un Dictionary para almacenar los pares <key,value>, y para realizar un seguimiento de los tiempos de acceso de los objetos, para mantener un SortedDictionary <key, timestamp>. La idea es que el subproceso asincrónico obtenga los elementos LRU del SortedDictionary y lo elimine del caché. Pero para que esto funcione, SortedDictionary debe ordenar por valor, lo que no ocurre.

Podría haber usado una por separado en lugar de la SortedListSortedDictionary para mantener la llave y {} marca de tiempo ordenados en la marca de tiempo, pero entonces voy a tener que hacer una búsqueda de "lineal" para encontrar la clave de la lista (cuando Tengo que ACTUALIZAR la marca de tiempo, cuando se accede a la misma clave de nuevo) - Estoy buscando una forma mejor que lineal, si es posible. ¿Alguien puede compartir ideas para lidiar con este problema?

Por lo tanto, mi problema se reduce a esto:

tengo para buscar las llaves en < = log n tiempo para actualizar la marca de tiempo, mientras que al mismo tiempo capaz de obtener las claves ordenados en base a la marca de tiempo.

Una forma de pensar era mantener un SortedDictionary de <{key,timestamp},null> que ordena las claves en función de la marca de tiempo de {key, timestamp}. Si bien esto está bien, el problema es hashcode() simplemente tendrá que devolver key.hashcode() (para buscar mientras se actualiza la marca de tiempo), mientras que equals() también debe usar la marca de tiempo. Por lo tanto, equals() y hashcode() están en conflicto, por lo que consideró que esta no es una buena idea ...

Answer 1

Lo que debe hacer es mantener dos diccionarios, uno ordenado por tiempo y otro por claves.

Recuerde que los diccionarios solo contienen referencias a sus objetos reales, por lo tanto, el diccionario que utilice para actualizar el objeto no es relevante.

Para actualizar el objeto de crear una función que va a actualizar tanto los diccionarios

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

Ahora usted tiene un registro de un mismo objeto por tanto de tiempo como clave.

Mantengo solo una referencia a un objeto en timedObjects. Esto ayuda mientras se elimina.

Puede seguir recortando el diccionario de timedObjects según sea necesario.

Ofcource, durante el recorte debe tener en cuenta que existe otro diccionario keyedObject que hace referencia al mismo objeto. Simplemente llamando al Remove no será suficiente.

Su código de eliminación tendrá que ser así:

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

timeToRemove en su mayoría provienen de un bucle, donde se decide cuál es el objeto de eliminar

Answer 2

El tipo de mapa que está buscando es (al menos en Java) llamado LinkedHashMap.

Desde el javadoc:

tabla hash y lista enlazada implementación de la interfaz del mapa, con orden de iteración predecible. Esta implementación difiere de HashMap en que mantiene una lista doblemente enlazada que se ejecuta a través de todas sus entradas . Esta lista vinculada define el orden de iteración, que es , normalmente el orden en que se insertaron las claves en el mapa (orden de inserción).

Se proporciona un constructor especial para crear un mapa hash vinculado cuya orden de iteración es el orden en que sus entradas eran última acceder, desde menos recientemente acceder a más recientemente (Acceso orden). Este tipo de mapa es adecuado para la construcción de memorias caché LRU .

Source for LinkedHashMap from the OpenJDK

yo sepa, no existen implementaciones existentes de un LinkedHashMap en C#. Dicho esto, no debería ser terriblemente difícil escribir uno.

Answer 3

En lugar de sorteddictionary, escriba su propia lista vinculada y haga que el diccionario señale sus nodos como valores. Se ordenará siempre por marca de tiempo, se actualizará la marca de tiempo y se eliminará el elemento menos utilizado con menos resentimiento será O (1).