Sorted Dictionary sorted on value in C# (LRU cache)

2018-06-22 00:27:56

I want to implement an LRU cache , where least recently used elements will be evicted asynchronously . My current idea is to use a Dictionary to store the <key,value> pairs , and to keep track of the times of accesses of the objects, to keep a SortedDictionary <key, timestamp> . The idea is for the async thread to get the LRU items from the SortedDictionary and remove from the cache . But for this to work, SortedDictionary needs to sort by value, which it does not.

I could have used a separate SortedList instead of the SortedDictionary for keeping the {key and timestamp} sorted on the timestamp , but then I'll have to do a "linear" lookup for finding the key from the list (when I have to UPDATE the timestamp, when the same key is accessed again) - I am looking for a better than linear way if possible. Can someone share ideas to deal with this problem?

So, my problem boils down to this:

I've to lookup keys in <= logn time for UPDATING the timestamp while at the same time able to get the keys sorted based on the timestamp .

One way thought of was to keep a SortedDictionary of <{key,timestamp},null> which orders the keys based on the timestamp part of {key,timestamp} . While this is fine , the problem is hashcode() will just have to return key.hashcode() (for lookup while updating timestamp) , while equals() should also use timestamp . So , equals() and hashcode() are in conflict , so felt that this is not a good idea ...

What you should do is keep two dictionaries, one sorted by time and one by keys.

Remember that dictionaries are only holding references to your actual objects, so which dictionary you use to update the object doesn't matter.

To update the object create a function that will update both the dictionaries

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

Now you have track of the same object by both time and key.

I am keeping only one reference to an object in timedObjects . This helps while removing.

You can keep trimming your timedObjects dictionary as required.

Ofcource, while trimming you must bear in mind that there is another dictionary keyedObject that has reference to the same object. Merely calling Remove will not be enough.

Your remove code will have to be like this:

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

timeToRemove will mostly come from a for loop, where you decide which object to remove

The type of map you're looking for is (at least in Java) called a LinkedHashMap .

From the javadoc:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches .

Source for LinkedHashMap from the OpenJDK

AFAIK, there are no existing implementations of a LinkedHashMap in C#. That being said, it shouldn't be terribly difficult to write one.

Instead of sorteddictionary, write your own linked list, and have the Dictionary point to its nodes as values. It will be always sorted by timestamp, updating timestamp and removing the least resently used element will be O(1).

链接地址: http://www.djcxy.com/p/61802.html

上一篇: 如何获得覆盖另一堆矩形的最小数量的矩形？

下一篇: 按C＃中的值排序的排序字典（LRU缓存）