Home > programming > LRU (least recently used cache) zz

LRU (least recently used cache) zz


Use a Hashmap along with doubly linked list.

Insertion O(1): When an element is inserted into the hashmap create a new node at the front of the doubly linked list. The hashmap entry will have the reference to this node in the douly linked list.
Also the node in the liked list will have a reference to the entry in the hashmap.
If the cache is full, then remove the tail of the doubled linkedlist, and insert the new node at head.

Deletion O(1): Delete the entry from the hashmap and also following the reference to the doubly linked list, delete the node too.

Access O(1): Get the element in the hashmap, follow the reference to the doubly linked list and just move this node in the doubly linked list to the front of the list.

Recently used O(1): Get the first element from the linked list.

using System;
using System.Collections.Generic;

namespace LRU
{
    public class Cache
    {
        public class Container
        {
            public Object obj;
            public Container next;
            public Container prev;

            public Container(object o)
            {
                this.obj = o;
            }
        }

        private const int MaxSize = 100;
        private Container start;
        private Container end;
        private Dictionary lookupTable;

        public Cache()
        {
            lookupTable = new Dictionary();
        }

        public void PutObj(object obj)
        {
            Container newNode;

            if (lookupTable.TryGetValue(obj, out newNode))
            {
                // object already exists in cache. no need to cache it again.
                return;
            }

            newNode = new Container(obj);
            if (lookupTable.Count == MaxSize)
            {
                // Purge 20% of the cache
                for (int i = 0; i < MaxSize / 5; i++)
                {
                    lookupTable.Remove(start.obj);
                    
                    start = start.next;
                    start.prev = default(Container);
                }
                GC.Collect();
            }

            if (lookupTable.Count < 1)
            {
                end = start = newNode;
            }
            else
            {
                end.next = newNode;
                newNode.prev = end;
                end = end.next;
            }

            lookupTable.Add(obj, newNode);
        }

        public Container GetObj(Object obj)
        {
            Container tmpNode;

            if (!lookupTable.TryGetValue(obj, out tmpNode))
            {
                // If the object doesn't exist in cache
                return default(Container);
            }

            // if the object is at the end of cache list, no need to shift its position.
            if (tmpNode != end)
            {
                if (tmpNode == start)
                {
                    start = start.next;
                    start.prev = default(Container);
                }
                else
                {
                    tmpNode.prev.next = tmpNode.next;
                    tmpNode.next.prev = tmpNode.prev;
                }

                tmpNode.prev = end;
                end.next = tmpNode;
                end = end.next;
                end.next = default(Container);
            }

            return tmpNode;
        }
    }
}
Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: