least recently used Algorithm
The Least Recently Used (LRU) algorithm is a widely-used cache replacement policy that aims to optimize cache performance by prioritizing the eviction of the least recently accessed data. This heuristic assumes that data items that have been accessed recently are more likely to be accessed again in the near future, whereas items that have not been used for a long time may not be required again soon. The LRU algorithm is employed in various applications, such as operating systems, databases, and memory management systems, to manage limited resources and maintain fast data retrieval times.
In the LRU algorithm, each data item in the cache is associated with a timestamp or a counter, which is updated every time the item is accessed. When the cache reaches its maximum capacity and a new item needs to be added, the algorithm identifies the item with the lowest timestamp or counter value (i.e., the least recently used item) and replaces it with the new data. To efficiently track the usage order of items, the LRU algorithm typically employs a data structure, such as a doubly-linked list or a priority queue, which allows for quick insertion and removal of elements. By continuously updating the cache with more frequently accessed items and discarding the least recently used ones, the LRU algorithm strives to minimize cache misses and improve overall system performance.
from abc import abstractmethod
import sys
from collections import deque
class LRUCache:
""" Page Replacement Algorithm, Least Recently Used (LRU) Caching."""
dq_store = object() # Cache store of keys
key_reference_map = object() # References of the keys in cache
_MAX_CAPACITY: int = 10 # Maximum capacity of cache
@abstractmethod
def __init__(self, n: int):
""" Creates an empty store and map for the keys.
The LRUCache is set the size n.
"""
self.dq_store = deque()
self.key_reference_map = set()
if not n:
LRUCache._MAX_CAPACITY = sys.maxsize
elif n < 0:
raise ValueError("n should be an integer greater than 0.")
else:
LRUCache._MAX_CAPACITY = n
def refer(self, x):
"""
Looks for a page in the cache store and adds reference to the set.
Remove the least recently used key if the store is full.
Update store to reflect recent access.
"""
if x not in self.key_reference_map:
if len(self.dq_store) == LRUCache._MAX_CAPACITY:
last_element = self.dq_store.pop()
self.key_reference_map.remove(last_element)
else:
index_remove = 0
for idx, key in enumerate(self.dq_store):
if key == x:
index_remove = idx
break
self.dq_store.remove(index_remove)
self.dq_store.appendleft(x)
self.key_reference_map.add(x)
def display(self):
"""
Prints all the elements in the store.
"""
for k in self.dq_store:
print(k)
if __name__ == "__main__":
lru_cache = LRUCache(4)
lru_cache.refer(1)
lru_cache.refer(2)
lru_cache.refer(3)
lru_cache.refer(1)
lru_cache.refer(4)
lru_cache.refer(5)
lru_cache.display()
