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

user_214849 0
Viewed 1900

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 ...

caching collections algorithm c#
4 Answers

here is the implementation of the LRU Cache in c#. efficient O(1), but not thread safe;

    static void Main(string[] args)
    {
        var cache = new LruCache(3);
        cache.Put(1, 1);
        cache.Put(2, 2);
        Console.WriteLine(cache.Get(1));       // returns 1
        cache.Put(3, 3);    // evicts key 2
        Console.WriteLine(cache.Get(2));       // returns -1 (not found)
        cache.Put(4, 4);    // evicts key 1
        Console.WriteLine(cache.Get(1));       // returns -1 (not found)
        Console.WriteLine(cache.Get(3));       // returns 3
        Console.WriteLine(cache.Get(4));       // returns 4     

    }

    public class DoubleLinkedList
    {
        public int key;
        public int value;
        public DoubleLinkedList next;
        public DoubleLinkedList prev;
        public DoubleLinkedList(int k, int v)
        {
            key = k;
            value = v;
        }
    }

    public class LruCache
    {
        private int size;
        private int capacity;
        private Dictionary<int, DoubleLinkedList> map;
        private DoubleLinkedList head;
        private DoubleLinkedList tail;
        public LruCache(int cap)
        {
            capacity = cap;
            map = new Dictionary<int, DoubleLinkedList>();
            head = new DoubleLinkedList(0, 0);
            tail = new DoubleLinkedList(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        public int Get(int key)
        {
            if (map.ContainsKey(key))
            {
                if (tail.prev.key != key)
                {
                    var node = map[key];
                    RemoveNode(node);
                    AddToEnd(node);
                }
                return map[key].value;
            }
            return -1;
        }

        private void AddToEnd(DoubleLinkedList node)
        {
            var beforeTail = tail.prev;
            node.prev = beforeTail;
            beforeTail.next = node;
            tail.prev = node;
            node.next = tail;
        }

        private void RemoveNode(DoubleLinkedList node)
        {
            var before = node.prev;
            before.next = node.next;
            node.next.prev = before;
        }

        public void Put(int key, int value)
        {
            if (map.ContainsKey(key))
            {
                map[key].value = value;
                var node = map[key];
                RemoveNode(node);
                AddToEnd(node);
            }
            else
            {
                size++;
                if (size > capacity)
                {
                    var node = head.next;
                    RemoveNode(node);
                    map.Remove(node.key);
                    size--;
                }

                var newNode = new DoubleLinkedList(key, value);
                AddToEnd(newNode);
                map.Add(key, newNode);
            }
        }
    }
user_20418820
Related