Dynamic programming

LRU cache

Pinterest LinkedIn Tumblr

LRU cache algorithm discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item.

Write a program to implement LRU Cache.

source Code

package com.dsacode.Algorithm.dynamic;
 
import java.util.HashMap;
 
public class LRUCahce {
 
       private int capacity;
       private int currentSize;
      
       class DoublyLinkedListNode {
          DoublyLinkedListNode prev;
          DoublyLinkedListNode next;
          int key;
          int value;
      
          public DoublyLinkedListNode(int key, int value) {
             this.key = key;
             this.value = value;
          }
       }
      
 
       private DoublyLinkedListNode start;
       private DoublyLinkedListNode end;
       private HashMap < Integer, DoublyLinkedListNode > nodeMap;
      
       public LRUCahce(int capacity) {
          this.capacity = capacity;
          currentSize = 0;
          nodeMap = new HashMap < Integer, DoublyLinkedListNode >();
       }
      
       private void printLRUCache() {
          DoublyLinkedListNode traverseNode = start;
          while (traverseNode != null) {
             System.out.println("[" + traverseNode.key + "]= ["
                   + traverseNode.value + "]");
             traverseNode = traverseNode.next;
          }
          System.out.println();
       }
      
       private void set(int key, int value) {
          if (nodeMap.containsKey(key)) {
             DoublyLinkedListNode node = nodeMap.get(key);
             node.value = value;
             bringToFront(node);
          } else {
             DoublyLinkedListNode insertNode = new DoublyLinkedListNode(key,
                   value);
             if (currentSize < capacity) {
                addToFront(insertNode);
                currentSize++;
             } else {
                removeLastNode();
                addToFront(insertNode);
             }
          }
       }
      
       private int get(int key) {
          if (nodeMap.containsKey(key)) {
             DoublyLinkedListNode node = nodeMap.get(key);
             bringToFront(node);
             return node.value;
          } else {
             return -1;
          }
       }
      
       private DoublyLinkedListNode removeLastNode() {
          DoublyLinkedListNode lastNode = nodeMap.remove(end.key);
          end = end.prev;
          if (end != null)
             end.next = null;
          lastNode = null;
          return lastNode;
       }
      
       private void addToFront(DoublyLinkedListNode insertNode) {
          insertNode.next = start;
          insertNode.prev = null;
          if (start != null)
             start.prev = insertNode;
          start = insertNode;
          if (end == null)
             end = insertNode;
          nodeMap.put(insertNode.key, insertNode);
       }
      
       private void bringToFront(DoublyLinkedListNode node) {
          DoublyLinkedListNode prevNode = node.prev;
          DoublyLinkedListNode nextNode = node.next;
 
          if (prevNode != null)
             prevNode.next = nextNode;
          else
             start = nextNode;
 
          if (nextNode != null)
             nextNode.prev = prevNode;
          else
             end = prevNode;
 
          addToFront(node);
       }
    public static void main(String[] args) {
         
            System.out.println("LRU Cache initlized with size 5");
            LRUCahce lru = new LRUCahce(5);
            for (int i = 5; i < 11; i++) {
              lru.set(i, i * 2);
            }
             
           System.out.println("Display LRU:");
           lru.printLRUCache();
           lru.get(7);
            
           System.out.println("LRU Cache after retrieving 7");
           lru.printLRUCache();
           lru.set(11, 11 * 2);
            
           System.out.println("LRU cache on adding one more item. It will replace last one");
           lru.printLRUCache();
    }
 
}

Output

LRU Cache unitized with size 5
Display LRU:
[10]= [20]
[9]= [18]
[8]= [16]
[7]= [14]
[6]= [12]
 
LRU Cache after retrieving 7
[7]= [14]
[10]= [20]
[9]= [18]
[8]= [16]
[6]= [12]
 
LRU cache on adding one more item. It will replace last one
[11]= [22]
[7]= [14]
[10]= [20]
[9]= [18]
[8]= [16]

Algorithm Explanation

Doubly linked list navigate backward and forward easily using two pointers.
The maximum size of the queue will be equal to the total number of frames available.
Least Recently Used(LRU) cache is a hash table of keys and double linked nodes. The node insert or remove using O(1) time complexity.
The most recently used pages will be near the front end and least recently pages will be near rear end.

Reference

  1. http://timday.bitbucket.org/lru.html
  2. https://en.wikipedia.org/wiki/Cache_algorithms
  3. http://www.geeksforgeeks.org/implement-lru-cache/

Write A Comment