What is LRU Algo?
LRU which stands for Least Recently Used, it is a popular algorithm used in computer science for managing memory caches. It is a type of cache eviction algorithm, which determines about which data to be removed from a cache when the cache is full.
How it Works
In a computer system, caches are used to store frequently accessed data in memory. This helps to speed up access to data as accessing data from memory is much faster than accessing data from the disk or other external storage devices. However, as the size of the cache is limited, it is important to manage the cache efficiently so that the most frequently accessed data is always available in the cache.
The LRU algorithm works on the principle of removing the least recently used data from the cache. The idea behind this is that the data that has not been accessed for a long time is less likely to be accessed again in the near future. Therefore, if the cache is full, the data that was accessed least recently is removed from the cache to make space for new data.
The LRU algorithm is implemented using a data structure called a doubly linked list. In a doubly linked list, each node contains a pointer to the next node as well as a pointer to the previous node. In the context of the LRU algorithm, each node in the doubly linked list represents a data item in the cache.
When a data item is accessed, it is moved to the front of the linked list. This indicates that it has been accessed most recently. When the cache is full and a new data item needs to be added, the least recently used item is removed from the back of the linked list.
Implementation in Java
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
class Main {
public static void main(String[] args) {
System.out.println("Hello world!");
LRUCache cache = new LRUCache(4);
cache.addToCache(11);
cache.addToCache(12);
cache.printLRU();
cache.addToCache(13);
cache.printLRU();
cache.addToCache(11);
cache.addToCache(14);
cache.printLRU();
cache.addToCache(15);
cache.addToCache(11);
cache.addToCache(12);
cache.printLRU();
}
}
class LRUCache {
// doublyLRUList - List for LRU data holding
private Deque<Integer> doublyLRUList;
// for checking if any page is avalabile in cache
// it saves the iteration on doublyLRUList
private HashSet<Integer> LRUhashSet;
// LRU_SIZE - maximum size of cache
private final int LRU_SIZE;
LRUCache(int capacity) {
doublyLRUList = new LinkedList<>();
LRUhashSet = new HashSet<>();
LRU_SIZE = capacity;
}
// addToCache add the page in the LRU cache
public void addToCache(int page) {
if (!LRUhashSet.contains(page)) {
if (doublyLRUList.size() == LRU_SIZE) {
int last = doublyLRUList.removeLast();
LRUhashSet.remove(last);
}
} else {
doublyLRUList.remove(page);
}
doublyLRUList.push(page);
LRUhashSet.add(page);
}
// printLRU prints contents of cache
public void printLRU() {
Iterator<Integer> itr = doublyLRUList.iterator();
while (itr.hasNext()) {
System.out.print(itr.next() + " ");
}
System.out.println();
}
}
Repl Link:: https://replit.com/@AnkitMalik2/LRU-Java#Main.java
Implementation in Golang
package main
import (
"fmt"
)
type LRUCache struct {
LRUList []int
LRUHashMap map[int]bool
Size int
}
func NewLRUCache(size int) *LRUCache {
return &LRUCache{
LRUList: make([]int, 0),
LRUHashMap: make(map[int]bool),
Size: size,
}
}
// Add insert the data in LRU
func (lru *LRUCache) Add(value int) {
l := len(lru.LRUList)
if !lru.LRUHashMap[value] {
if l >= lru.Size {
last := lru.LRUList[l-1]
lru.LRUList = lru.LRUList[:l-1]
delete(lru.LRUHashMap, last)
}
} else {
for idx, data := range lru.LRUList {
if data == value {
lru.LRUList = append(lru.LRUList[:idx], lru.LRUList[idx+1:]...)
break
}
}
}
lru.LRUList = append([]int{value}, lru.LRUList...)
lru.LRUHashMap[value] = true
}
// PrintLRU - prints the data of LRU cache
func (lru *LRUCache) PrintLRU() {
for _, data := range lru.LRUList {
fmt.Print(data, " ")
}
fmt.Println()
}
func main() {
// initiate lru with defined size
lru := NewLRUCache(5)
// use of Add function
lru.Add(1)
lru.Add(2)
lru.Add(3)
lru.Add(4)
lru.Add(5)
lru.Add(6)
lru.Add(1)
// printing all data of LRU
lru.PrintLRU()
}
Repl Link: https://replit.com/@AnkitMalik2/LRU-Golang#main.go
You can see some complicated LRU implementation here: https://github.com/hashicorp/golang-lru/blob/8d9a62dcf60cd87ed918b57afad8a001d25db3de/simplelru/lru.go
Top comments (0)