The Least Recently Used (LRU) algorithm is a cache replacement algorithm commonly used to manage a cache when its space is limited. The primary goal of LRU is to maximize cache efficiency by removing the least recently used items, allowing faster access to frequently accessed values. LRU cache is a popular topic often discussed in interviews, either directly or with variations. It plays a significant role in operating systems as it provides a page replacement method that helps reduce the number of page faults.
The LRU cache operates with a fixed size, and when it reaches its capacity, the algorithm removes the least recently used value to make space for a new value. To implement the LRU cache, we need to define two essential functions: get() and put().
get()
The get() function is responsible for retrieving a value from the cache. If the requested value is present in the cache, it is returned. However, if the value is not found in the cache, it signifies a cache miss or page fault, and the function returns -1.
put()
The put() function is used to insert a key-value pair into the cache. If the cache is already at its maximum capacity, the algorithm evicts the least recently used item before adding the new key-value pair.
Implementing an LRU cache requires careful management of the cache's data structure and the tracking of usage statistics to determine the least recently used items.
Understanding and implementing LRU cache is crucial for optimizing cache performance in systems with limited resources. It enables efficient data storage and retrieval, minimizing the number of cache misses and improving overall system performance.
Implementation of LRU Cache in Javascript
To implement an LRU Cache in JavaScript, we can utilize two data structures: a queue and a hash table.
Queue: We can implement the queue using a doubly linked list. The size of the queue will be equal to the total number of frames available in the cache (cache size). The most recently used pages will be positioned near the front end of the queue, while the least recently used pages will be near the rear end.
Hash Table: We will use a hash table to store the page numbers as keys and the corresponding addresses of the queue nodes as values. This allows us to quickly access and update the queue nodes.
The LRU cache will support the following operations:
get(item): Returns the cache value for the given item/page number. This operation involves checking if the item exists in the cache and updating its position in the queue to mark it as the most recently used.
put(item, value): Adds a new value to the cache. If the cache is already full, the least recently used item will be evicted before inserting the new item. This operation involves adding the item to the queue and updating the hash table.
use(item): Marks an existing value as used, re-arranging the cache to prioritize the used item as the most recently used. This operation involves updating the position of the item in the queue.
evict(): Removes a value from the cache. This operation is triggered when the cache is full and a new item needs to be inserted. It involves removing the least recently used item from the queue and updating the hash table.
insert(item, value): A helper function to add a value to the cache while performing the put() operation. This function handles the case where the item already exists in the cache and only needs to update its value.
By combining these operations and managing the queue and hash table efficiently, we can implement a functional LRU cache in JavaScript. This cache replacement algorithm helps optimize data access and storage, resulting in improved performance and reduced cache misses.
How LRU cache work?
Let us understand how LRU cache works by taking an example of a cache of 4 elements, say 1, 2, 3, 4.
In order to add a new element to this (say 5), we will have to first remove the least recently used which in this case is 1.
Now when you try to access the 2 again it will be shifted to the end again as it will be the most recently used one and 3 will become the least recently used.
Example:
The example demonstrates the usage of the LRUCache class by creating an instance with a capacity of 4. Four key-value pairs (1, 'a'), (2, 'b'), (3, 'c'), and (4, 'd') are inserted into the cache using the put() function. The cache is then displayed. After that, the use() function is called with key 2, which moves the corresponding node to the front of the queue. Finally, the cache is displayed again to show the updated order.
class Node {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
}
const LRUCache = function(cap) {
this.cap = cap;
this.count = 0;
this.head = null;
this.tail = null;
this.cache = new Map();
//Returns the value of the given key
this.get = function(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.use(key);
return node.val;
};
//Adds new item in the list
this.put = function(key, val) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.val = val;
this.use(key);
this.cache.set(key, node);
} else {
if (this.count >= this.cap) {
this.evict();
}
this.insert(key, val);
this.use(key); // may not be needed
}
};
//Uses the cache with given key and marks it as most recently used
this.use = function(key) {
const node = this.cache.get(key);
if (node === this.head) {
return;
} else if (node === this.tail) {
node.prev.next = null;
this.tail = node.prev;
node.prev = null;
node.next = this.head;
this.head.prev = node;
this.head = node;
} else {
if (node.prev) {
node.prev.next = node.next;
}if (node.next) {
node.next.prev = node.prev;
}
node.next = this.head;
node.prev = null;
this.head.prev = node;
this.head = node;
}
};
//Removes the least recent used cache
this.evict = function() {
const keyToEvict = this.tail ? this.tail.key : null;
if (!this.tail) {
return;
} else if (this.head === this.tail) {
this.head = null;
this.tail = null;
} else {
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
if (keyToEvict) {this.count--;
this.cache.delete(keyToEvict);
}
};
//Helper function to add new cache in the queue
this.insert = function(key, val) {
const node = new Node(key, val);
this.count++;
this.cache.set(key, node);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
this.head.prev = node;
node.next = this.head;
this.head = node;
}
};
//Display the list
this.display = function(){
let current = this.head;
while(current){
console.log(current.key, current.val);
current = current.next;
}
}
};The provided code implements an LRU Cache in JavaScript using a combination of a doubly linked list and a hash table. Let's understand how it works with the given example:
Queue Implementation: The Node class represents a node in the doubly linked list. Each node contains a key, val (value), prev (reference to the previous node), and next (reference to the next node). The LRU Cache class, LRUCache, maintains a head and tail pointer to the first and last nodes in the queue, respectively.
Cache Initialization: The LRUCache class takes a capacity parameter (cap) to set the maximum size of the cache. It also initializes a count variable to keep track of the number of items in the cache and a cache Map to store the key-value pairs.
get(key) Function: This function is used to retrieve the value of a given key from the cache. If the key is not present, it returns -1. If the key exists, the function updates the position of the corresponding node in the queue by calling the use(key) function, and then returns the value.
put(key, value) Function: This function is used to add or update a key-value pair in the cache. If the key already exists, it updates the value and calls the use(key) function to move the corresponding node to the front of the queue. If the key is not present, it checks if the cache is full (count >= cap). If it is full, the evict() function is called to remove the least recently used item from the cache. Then, the new key-value pair is inserted using the insert(key, value) function and marked as the most recently used by calling use(key).
use(key) Function: This function is responsible for marking a node as the most recently used. It moves the node to the front of the queue by adjusting the pointers of the previous and next nodes accordingly.
evict() Function: This function is called when the cache is full and a new item needs to be inserted. It removes the least recently used item from the cache by deleting the tail node, adjusting the tail pointer, and updating the cache count.
insert(key, value) Function: This helper function adds a new node containing the key-value pair to the front of the queue. It also updates the cache Map and adjusts the head pointer accordingly.
display() Function: This function is used to display the current state of the cache by traversing the linked list from the head to the tail.
Output:
Input:const lru = new LRUCache(4);
lru.put(1, 'a');
lru.put(2, 'b');
lru.put(3, 'c');
lru.put(4, 'd');
lru.display();
lru.use(2);
lru.display();
Output:
//LRU
4 "d"
3 "c"
2 "b"
1 "a"
//After using 2
2 "b"
4 "d"
3 "c"
1 "a"The above output demonstrates how the LRU Cache works by maintaining the most recently used items at the front of the queue and evicting the least recently used item when the cache is full.