How to implement LRU cache in python?
What is LRU cache?
Least-recently-used (LRU) cache replacement is algorithms that removes least recent used data to make room for newdata.
Terminology Used in post
DLL -> Doubly Linked ListFront of DLL -> node just after head node of DLL
Last node of DLL-> Node just before tail node of DLL
LRU CLASS
We have implemented LRU using a Doubly Linked list and Dictionary data structure. There are two nodes at the beginning and end of DLL, (HEAD and TAIL) that both have Key = -1 and Val = -1.
We have used dictionary to store key as key of item and value as node object DLL of the LRU class. We are saving item in dictionary having key as key of LRU cache(Node) item and value as Node object of LRU cache item, so at any instance if we have Key of item we can get the item by getting value of key which is Node object.
Instance variable "size" is defined in order to define max size of LRU cache.
ALGORITHM
put(key, value) method - to insert new item
1) If the provided key is already present in the dictionary remove the node with the provided key in Doubly Linked List(DLL) by getting node object from dictionary and remove item from dictionary with provided key.
Add new node in front of DLL and add item with key as new key and value as new node object in dictionary.
2) If length of dictionary is equal to the max length of LRU, remove last node from DLL and remove item from dictionary.
Add new node in front of DLL and add item to dictionary.
3) If provided key is not present in dictionary and current size of LRU is also less than max size of LRU, add new node in front of DLL and add
(key and node object) in dictionary.
get(key) method -to get value of an item
1) If key is not present in dictionary return -1
2) If present, remove the node from DLL and remove item from dictionary. Add new node in front of DLL, also add item in dictionary having key as key and new node object as value.
Python Code
class Node:
"""
Node of Doubly linked list
"""
def __init__(self, key=-1, val=-1, next = None, prev=None) -> None:
self.key = key
self.val = val
self.next = next
self.prev = prev
class LRU:
"""
Doubly linked list to keep (key, val) of LRU Cache
"""
def __init__(self, size = 3):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.size = size
self.hashmap = {} #{key:hashaddress_of_node}
def __remove_node(self, key):
#get node with same key from hashmap
node_to_be_remove = self.hashmap.get(key) #value will be node obejct
#remove node from DLL
temp_prev_node_from_node_to_be_remove = node_to_be_remove.prev
temp_next_node_from_node_to_be_remove = node_to_be_remove.next
temp_prev_node_from_node_to_be_remove.next = temp_next_node_from_node_to_be_remove
temp_next_node_from_node_to_be_remove.prev = temp_prev_node_from_node_to_be_remove
#remove node from hashmap
self.hashmap.pop(key)
def __append_node(self, key, val):
new_node = Node(key, val)
temp_next_from_head = self.head.next
self.head.next = new_node #1st connction
new_node.prev = self.head #2nd connection
new_node.next = temp_next_from_head #3rd connection
temp_next_from_head.prev = new_node #4th connection
#append node obejct in hashmap
self.hashmap[key]=new_node
def put(self, key, val):
if self.hashmap.get(key):
#REMOVE NODE WITH SAME KEY IN DLL AND HASHMAP
self.__remove_node(key)
#ADD NEW NODE IN FRONT OF DLL AND HASHMAP AS IT IS LRU KEY IN PREVIOUS STEP
self.__append_node(key, val)
else:
if len(self.hashmap) == self.size:
#REMOVE LAST NODE AS LRU IS FULL AND LAST NODE IN DLL IS LEAST RECENTLY USED NODE
#get last node
last_node = self.tail.prev
key_to_remove = last_node.key
#REMOVE LAST NODE
self.__remove_node(key_to_remove)
#ADD NEW NODE IN FRONT OF DLL
self.__append_node(key, val)
else:
self.__append_node(key, val)
def get(self, key):
#check if key present
if self.hashmap.get(key):
#get node object of provided key
node = self.hashmap.get(key)
val = node.val
#As this node is getting accessed, need to push this node in front of DLL becoz it will
# become LRU
#first delete node from its place
node_to_be_remove = node
#remove node from DLL
temp_prev_node_from_node_to_be_remove = node_to_be_remove.prev
temp_next_node_from_node_to_be_remove = node_to_be_remove.next
temp_prev_node_from_node_to_be_remove.next = temp_next_node_from_node_to_be_remove
temp_next_node_from_node_to_be_remove.prev = temp_prev_node_from_node_to_be_remove
#add new node in front of DLL
new_node = Node(key, val)
temp_next_from_head = self.head.next
self.head.next = new_node #1st connction
new_node.prev = self.head #2nd connection
new_node.next = temp_next_from_head #3rd connection
temp_next_from_head.prev = new_node #4th connection
#change node object in hashmap
self.hashmap[key] = new_node
return val
else:
return -1
def print_lru(self):
current_node = self.head
while current_node:
print(current_node.key, current_node.val)
current_node = current_node.next
lru_object = LRU()
lru_object.put(1,1)
lru_object.print_lru()
lru_object.put(2,2)
lru_object.print_lru()
lru_object.put(3,3)
lru_object.print_lru()
lru_object.put(4,4)
print("before getting a node ")
lru_object.print_lru()
lru_object.get(2)
print("after getting a node ")
lru_object.print_lru()
print("after appending a node with same key, that is already present in lru")
lru_object.put(3,100)
lru_object.print_lru()
Osmm
ReplyDelete