Least Recently Used implementation using Python
The Least Recently Used (LRU) Cache is a powerful strategy for managing limited memory by evicting the least recently accessed items. It’s widely used across systems where performance and resource optimization are critical.
LRU -Least Recently Used. It is a cache which manages the less
memory. Mainly, it handles the resource in optimize manner.
Example:
Let us consider a Web browser. It stores the recently
visited pages, scripts and images.
Python implementation:
It uses
doubly Linked list for storing the data. The steps are given as follows…
- Create a c_node class and initialise three values. c_self,c_key and c_value.
- Make the previous and nest pointers as Null.
- Write the code for LRUcache. It holds the capacity value.
- let us create a Dummy head and tail nodes.
- Insert the values to the cache.
- Delete a value in the list.
- Function ‘get()’ is used to get the value. ‘put’ function displays the value.
- ‘main()’ function calls the function to get the output.
Program:
class c_Node:
def
__init__(c_self, c_key, c_value):
c_self.c_key =
c_key
c_self.c_value
= c_value
c_self.prev =
c_self.next = None
class LRUCache:
def
__init__(c_self, capa: int):
c_self.capa =
capa
c_self.cache =
{} # key -> node
# let us
create a Dummy head and tail nodes
c_self.head =
c_Node(0, 0)
c_self.tail =
c_Node(0, 0)
c_self.head.next = c_self.tail
c_self.tail.prev = c_self.head
def
_remove(c_self, node):
"""Method to Remove the node from linked
list."""
prev, nxt =
node.prev, node.next
prev.next =
nxt
nxt.prev =
prev
def _add(c_self,
node):
"""insert the node right before tail
(MRU)."""
prev =
c_self.tail.prev
prev.next =
node
node.prev =
prev
node.next =
c_self.tail
c_self.tail.prev = node
def get(c_self,
c_key: int) -> int:
if c_key not
in c_self.cache:
return -1
node =
c_self.cache[c_key]
c_self._remove(node)
c_self._add(node)
return
node.c_value
def put(c_self,
c_key: int, c_value: int) -> None:
if c_key in
c_self.cache:
c_self._remove(c_self.cache[key])
node =
c_Node(c_key, c_value)
c_self._add(node)
c_self.cache[c_key] = node
if
len(c_self.cache) > c_self.capa:
# delete
the least recently used node
lru =
c_self.head.next
c_self._remove(lru)
del
c_self.cache[lru.c_key]
if __name__ == "__main__":
lru = LRUCache(2)
lru.put(1, 130)
lru.put(2, 220)
print("Get
the key value of node1:", lru.get(1))
# Output: 130
lru.put(3,
30) # Evicts the key 2
print("Get
the key value of node2:", lru.get(2))
# Output: -1 (because idt is evicted already)
print("Get
the key value of node3:", lru.get(3))
# Output: 30
Output:
C:\raji\blog>py LRUcache.py
Get the key value of node1: 130
Get the key value of node2: -1
Get the key value of node3: 30
Here, the python program to implment LRU using linked list
is written efficiently.
Comments
Post a Comment