StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Wednesday, March 6, 2013

Implement LRU cache with O(1) operations

 March 06, 2013     Programming problems in CPP     No comments   

Implement LRU cache with O(1) operations

LRU --> Least Recently Used cache is method where in when cache size is full to accommodate for new page, it will unload least recently used page.

The approach

  • To access the pages in the LRU cache, to have O(1) operation, good to go for hash table.

  • How do we maintain the time-stamp information. One way is to keep them ordered with latest used to previously used pages in a time decreasing order. So let us create a linked list with nodes to the page pointers and whenever a page in the cache is touched or a page is loaded that page node is made head of the list. And that way the tail is always least recently used and when cache size is full and we can delete the page pointed by the tail.
  • Creating a new node as head is O(1). Deleting form the tail would be O(1), if we maintain tail info, but however, updating tail is not. And when a touched page needs to be moved to the head position, we need to do 2 things 1. access it and 2 de-link to move to head. First is solved by the hash table, which keeps the pointers to the nodes as the values. And for second, to de-link the node from the middle to the front, we need to do in O(1). For this, instead of single linked list we use doubly linked list. This gives O(1) operation for de-linking as well as updating the tail.

C++ program to implement LRU cache

#include <iostream>
#include <unordered_map>

using namespace std;

// List nodeclass
class Node {
public:
int data;
Node* next;
Node* prev;
};

// Linked list class
class DLList {
public:
DLList() { head = NULL; tail = NULL; count = 0;}
~DLList() {}
Node* addNode(int val);
void print();
void removeTail();
void moveToHead(Node* node);
int size() { return count; }

private:
Node* head;
Node* tail;
int count;
};

// Function to add a node to the list
Node* DLList::addNode(int val)
{
Node* temp = new Node();
temp->data = val;
temp->next = NULL;
temp->prev = NULL;

if ( tail == NULL ) {
tail = temp;
head = temp;
}
else {
head->prev = temp;
temp->next = head;
head = temp;
}
count++;
return temp;
}

void DLList::moveToHead(Node* node)
{
if (head == node)
return;
node->prev->next = node->next;

if (node->next != NULL){
node->next->prev = node->prev;
} else {
tail = node->prev;
}
node->next = head;
node->prev = NULL;
head->prev = node;
head = node;
}

void DLList::removeTail()
{
count--;
if (head == tail) {
delete head;
head = NULL;
tail = NULL;
} else {
Node* del = tail;
tail = del->prev;
tail->next = NULL;
delete del;
}
}

void DLList::print()
{
Node* temp = head;
int ctr = 0;
while ( (temp != NULL) && (ctr++ != 25) ) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

class LRUCache {
public:
LRUCache(int aCacheSize);
void fetchPage(int pageNumber);

private:
int cacheSize;
DLList lruOrder;
unordered_map<int,Node*> directAccess;
};

LRUCache::LRUCache(int aCacheSize):cacheSize(aCacheSize)
{
}

void LRUCache::fetchPage(int pageNumber)
{
unordered_map<int,Node*>::const_iterator it = directAccess.find(pageNumber);

if (it != directAccess.end()) {
lruOrder.moveToHead( (Node*)it->second);
} else {
if (lruOrder.size() == cacheSize-1)
lruOrder.removeTail();
Node* node = lruOrder.addNode(pageNumber);
directAccess.insert(make_pair<int,Node*>(pageNumber,node));
}
lruOrder.print();
}


int main()
{
LRUCache lruCache(10);

lruCache.fetchPage(5);
lruCache.fetchPage(7);
lruCache.fetchPage(15);
lruCache.fetchPage(34);
lruCache.fetchPage(23);
lruCache.fetchPage(21);
lruCache.fetchPage(7);
lruCache.fetchPage(32);
lruCache.fetchPage(34);
lruCache.fetchPage(35);
lruCache.fetchPage(15);
lruCache.fetchPage(37);
lruCache.fetchPage(17);
lruCache.fetchPage(28);
lruCache.fetchPage(16);

return 0;
}

Output

5 
7 5
15 7 5
34 15 7 5
23 34 15 7 5
21 23 34 15 7 5
7 21 23 34 15 5
32 7 21 23 34 15 5
34 32 7 21 23 15 5
35 34 32 7 21 23 15 5
15 35 34 32 7 21 23 5
37 15 35 34 32 7 21 23 5
17 37 15 35 34 32 7 21 23
28 17 37 15 35 34 32 7 21
16 28 17 37 15 35 34 32 7
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk