Design LRU Cache using C++




LRU Cache - C++ Implementation


LRU, or Least Recetly Used, is one of the Page Replacement Algorithms, in which the system manages a given amount of memory - by making decisions what pages to keep in memory, and which ones to remove when the memory is full.
Let’s say, the capacity of a given cache (memory) is C.
Our memory stores key, value pairs in it.
It should support the following operations:
  • get(key) - Get the value of the given key if it exists in the memory (else, let’s say -1)
  • put(key, value) - Set, or insert the value if not present. If our cache reaches its capacity, we should remove the item which was least recently used.
Another constraint to the given problem is:
Both the operations must be done in constant Time Complexity, ie in O(1).
Now, we need to think of some of the data structures, which would allow us to perform the above operations in O(1).

Choice of data structures

  • Queue - We should maintain a Queue (double ended queue), in which the most recently used pages (items) are in the front, and the least recently used pages are in the rear. This would allow to remove the least recently used item in O(1) time.
  • Doubly Linked List - We should implement our Queue using a doubly linked list (instead of arrays), which would allow us to apply shifting operations in O(1) time. (like, when we need to shift a page to the front of the queue)
  • HashMap - We should hash the key values to the location where the page is stored. This would allow get operation in O(1) time.

Design and Implementation

Now that we know which what all data structures to use, let’s look at the implementation.
Whenever a user gets a page, we return its value, and also move that page to the front of our Queue.
Whenever a user sets a page, if the page is already present, we update its value and move that page to the front of our Queue,
else we add a new page to our cache in the front of the Queue.
But if our cache has reached its capacity, we remove the least recently used page (ie the rear item in our Queue) from our memory.
  1. class Node
    • Data members:
      1. key
      2. value
      3. next node address
      4. previous node address

  2. class DoublyLinkedList
    • Data members:
      1. front node address
      2. rear node address
    • Member functions:
      1. move_page_to_head(..)
      2. remove_rear_page()
      3. get_rear_page()
      4. add_page_to_head(..)

  3. class LRU
    • Data members:
      1. capacity
      2. current size
      3. a DoublyLinkedList object
      4. Hashmap
    • Member functions:
      1. get(key)
      2. put(key, value)
Let’s make the 3 classes.

Code


#include <iostream> #include <map> using namespace std; class Node { public: int key, value; Node *prev, *next; Node(int k, int v): key(k), value(v), prev(NULL), next(NULL) {} }; class DoublyLinkedList { Node *front, *rear; bool isEmpty() { return rear == NULL; } public: DoublyLinkedList(): front(NULL), rear(NULL) {} Node* add_page_to_head(int key, int value) { Node *page = new Node(key, value); if(!front && !rear) { front = rear = page; } else { page->next = front; front->prev = page; front = page; } return page; } void move_page_to_head(Node *page) { if(page==front) { return; } if(page == rear) { rear = rear->prev; rear->next = NULL; } else { page->prev->next = page->next; page->next->prev = page->prev; } page->next = front; page->prev = NULL; front->prev = page; front = page; } void remove_rear_page() { if(isEmpty()) { return; } if(front == rear) { delete rear; front = rear = NULL; } else { Node *temp = rear; rear = rear->prev; rear->next = NULL; delete temp; } } Node* get_rear_page() { return rear; } }; class LRUCache{ int capacity, size; DoublyLinkedList *pageList; map<int, Node*> pageMap; public: LRUCache(int capacity) { this->capacity = capacity; size = 0; pageList = new DoublyLinkedList(); pageMap = map<int, Node*>(); } int get(int key) { if(pageMap.find(key)==pageMap.end()) { return -1; } int val = pageMap[key]->value; // move the page to front pageList->move_page_to_head(pageMap[key]); return val; } void put(int key, int value) { if(pageMap.find(key)!=pageMap.end()) { // if key already present, update value and move page to head pageMap[key]->value = value; pageList->move_page_to_head(pageMap[key]); return; } if(size == capacity) { // remove rear page int k = pageList->get_rear_page()->key; pageMap.erase(k); pageList->remove_rear_page(); size--; } // add new page to head to Queue Node *page = pageList->add_page_to_head(key, value); size++; pageMap[key] = page; } ~LRUCache() { map<int, Node*>::iterator i1; for(i1=pageMap.begin();i1!=pageMap.end();i1++) { delete i1->second; } delete pageList; } };




#include <iostream> #include "LRUCache.cpp" using namespace std; int main() { LRUCache cache(2); // cache capacity 2 cache.put(2,2); cout << cache.get(2) << endl; cout << cache.get(1) << endl; cache.put(1,1); cache.put(1,5); cout << cache.get(1) << endl; cout << cache.get(2) << endl; cache.put(8,8); cout << cache.get(1) << endl; cout << cache.get(8) << endl; }



This article revolves around the implementation of Least Recently Used Cache (LRU Cache) in C++. The article has been  broken down into 3 sections:
                                             1. What is a Cache
                                             2. How can it be implemented
                                             3. Source Code
 What is a Cache?
     A cache is a high speed memory that is used by the CPU to store the most recently used information for faster retrieval. The execution time of an instruction is basically the processing speed of the CPU. If the time taken for retrieval of information is higher than the processing speed then obviously the execution time will be higher than the processing speed. In Order to  speed up the processing, certain information is prefetched in the cache memory as the cache memory is much faster than main memory or secondary memory.
 How can it be implemented?
     In general, any algorithm can be executed in n number of ways but it is always wise to look at the most optimal solution with respect to space and time complexity. In simple words, time complexity is the amount of time taken to perform a certain function and space complexity is the amount of space required for the function regardless of the number of inputs.
     Inorder to build an LRU cache, we must have an efficient system with a very fast(O(1)) lookup, deletion and updation of the order. Here O(1) means that the program will always take constant time for an action regardless of the no of values.
     The best bet for this is a combination of hashtable and doubly linked list because if we look at hashtables, they have constant lookup and insertion but there is no functionality for looking at the recently queried value. If we look at doubly linked list, we can have a constant lookup, deletion and updation provided we have the address of the value which can be provided by the hash table.
     For the implementation, we can have the addresses and key value of each node in hashmap and the linked list will hold a value of keys. The linked list is designed such that the head is the place where the updation takes place and so least used will automatically be pushed to the tail.


Source code:
#include<iostream>
#include<unordered_map>
#include<list>
using namespace std;class lru{
list<int> el;//Doubly linked list to store the elements
unordered_map<int, list<int>::iterator> ref;//hashtable for storing the reference address
int n;//hashtable for storing the refernce address
public:
/*Constructor to initialize the capacity of cache*/
lru(int cap){
n=cap;
}
void insert(int);
void print();
};/*add a value to the list if new or move the value to the front if already present*/
void lru::insert(int val){
if(ref.find(val)==ref.end()){// if the value is not found in the list
if(ref.size()==n){//if the cache size is equal to the capacity
int x=el.back();
el.pop_back();//removing the last element from the queue
ref.erase(x); //erasing the key value pair from the hash table
}
}
else{
el.erase(ref.find(val)->second);//if present erasing it
}
el.push_front(val);//adding the value to the front
ref[val]=el.begin();//storing the address in the hashtable
}/*Iterating through the entire list and printing the elements*/
void lru::print(){
for(auto it=el.begin();it!=el.end();it++)
cout<<*it<<" ";
cout<<endl;
}int main(){lru cache(3); //to specify the capacity
/*Refer explanation*/cache.insert(1);//1
cache.insert(2);//2
cache.insert(3);//3
cache.insert(2);//4
cache.insert(4);//5
cache.insert(2);//6
cache.insert(5);//7
cache.print();
}

OUTPUT:
5 2 4 
Explanation:


1. 1


2. 2, 1


3. 3, 2, 1


4. 2, 3, 1 (Position of 2 is changed)


5. 4, 2, 3 (least recently used 1 is deleted and 4 is inserted)


6. 2, 4, 3 (Position of 2 is changed)


7. 5, 2, 4 (least recently used 3 is deleted and 5 is inserted
































































































































Comments











Post a Comment























Popular posts from this blog









unordered_map in C++ STL





















    unordered_map in C++ STL       unordered_map is an associated container that stores elements formed by combination of key value and a mapped value. The key value is used to uniquely identify the element and mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.  Internally unordered_map is implemented using  Hash Table , the key provided to map are hashed into indices of hash table that is why performance of data structure depends on hash function a lot but on an average the cost of  search, insert and delete  from hash table is O(1).     // C++ program to demonstrate functionality of unordered_map   #include <iostream>   #include <unordered_map>   using  namespace  std;         int  main()   {        // Declaring umap to be of <string, int> type        // key will be of string type and mapped value will        // be o...








Read more










LFU Cache implementation





















   Least Frequently Used (LFU) Cache Implementation    Least Frequently Used (LFU)  is a caching algorithm in which the least frequently used cache block is removed whenever the cache is overflowed. In LFU we check the old page as well as the frequency of that page and if the frequency of the page is larger than the old page we cannot remove it and if all the old pages are having same frequency then take last i.e FIFO method for that and remove that page.     Min-heap  data structure is a good option to implement this algorithm, as it handles insertion, deletion, and update in logarithmic time complexity. A tie can be resolved by removing the least recently used cache block. The following two containers have been used to solve the problem:   A vector of integer pairs has been used to represent the cache, where each pair consists of the block number and the number of times it has been used. The vector is ordered in the form of a min-heap, which allows us to access the least fre...








Read more