LRU Cache Menggunakan Python

Teori LRU

LRU atau Least Recently Used akan membuang item yang paling jarang digunakan terlebih dahulu. Jadi tujuan akhirnya adalah cache yang berisi item yang sering digunakan.

Contoh sederhana penggunaanya adalah ketika kita mengetik alamat web pada browser. Browser akan mencari item berdasarkan alamat yang diketikan dan mencari dalam cache, link mana yang paling sering digunakan.

Pendekatan LRU Cache yang akan kita lakukan adalah menggunakan double linked list dan hash table untuk mempercepat proses pencarian cache.

Double Linked List

Double linked list adalah dimana setiap node memiliki referensi untuk prev dan next node. Head adalah node pertama dalam list, sementara tail adalah node terakhir dalam list.

Untuk melacak item dalam linked list, digunakan age bits, makin sering suatu item digunakan, makin besar nilai age bits.

Ketika cache penuh, kita perlu membuang item yang paling jarang digunakan. Pendekatan lain adalah, item yang lebih dekat dengan head diutamakan.

Ketika suata item diinput, ada kemungkinan item tersebut sudah ada didalam linked list. Kita perlu mencari item tersebut dan melakukan update. Saat melakukan pencarian, operasi ini memerlukan O(N) time complexity. Oleh karena itu kita gunakan hash table untuk mempersingkat waktu menjadi O(1).

Agar lebih jelas, berikut simulasi LRU Cache, menggunakan skenario alamat URL. Dimana ukuran cache adalah 5.

Setiap node pada linked list harus diberi ID yang akan digunakan pada hashtable.

Misalnya kita masuk ke URL A, dengan ID 0, sebelum melakukan insert kedalam linked list, kita periksa dahulu dalam hash table, jika tersedia dalam hash table, dilakukan update, jika tidak maka dilakukan insert.

Kemudian, misalnya URL B diakses. Sama seperti proses sebelumnya, periksa dalam hash table, jika sudah ada dilakukan proses update, jika belum dilakukan proses insert.

Contoh berikutnya, alamat C diakses. Dapat diperhatikan, proses insert di head. Karena sesuai nama algoritma Least Recently Used, atau yang paling jarang digunakan, jadi makin kebelakang makin jarang digunakan.

Untuk singkat cerita, kita linked list sudah terisi semua, seperti gambar dibawah. Saat ini cache sudah penuh.

Jika Kita mengakses URL F, maka item terakhir harus dibuang, shift node ke kanan, lalu insert node F di head.

Simulasi berikutnya yang mungkin terjadi adalah, mengakses URL yang sudah pernah di insert, katakanlah URL D. Ketika kita periksa pada hash table, URL D sudah ada, maka kita perlu melakukan update dengan memindahkan node D ke head. Lalu shift node lainnya ke kanan.

Implementasi LRU Cache Dalam Python

Berikut contoh implementasi LRU cache dalam Python

#capacity of the cache (how many items it can store)
CAPACITY = 4

#we implement the cache with doubly linked lists - this is the node class
class Node:

	def __init__(self,id,data):
		self.id = id
		self.data = data
		self.previous_node = None
		self.next_node = None

#we implement the cache with doubly linked lists		
class DoublyLinkedList:

	def __init__(self):
		self.head = None
		self.tail = None

class LRUCache:

	def __init__(self):
		self.actual_size = 0
		#we store integer node id - Node pairs: this is how we can find a node in O(1)
		self.dictionary = {}
		self.linked_list = DoublyLinkedList()
	
	def put(self,id,data):
	
		#update the node if already exists (we have to check whether the dict is empty first)
		if id in self.dictionary:
			node = self.dictionary[id]
			node.data = data
			#update the node to be the head (cache feature)
			self.update(node)
			return
		
		#the data is not present in the cache so insert
		node = Node(id,data)
		
		#we have to insert into the cache + set it to be the head node
		if self.actual_size < CAPACITY:
			self.actual_size = self.actual_size + 1
			self.add(node)
		else:
			#the cache is full: we have to remove the last item + insert the new one
			self.remove_tail()
			self.add(node)
	
	#add node to the head	
	def add(self,node):
		
		#the node will be the new head: so update accordingly
		node.next_node = self.linked_list.head
		#it is the first node: no previous node
		node.previous_node = None
		
		#we have to update the previous head: point to the new head (which is the node)
		if self.linked_list.head:
			self.linked_list.head.previous_node = node
		
		#update the head node		
		self.linked_list.head = node
		
		#if there is 1 node in the list: it is the head as well as the tail
		if not self.linked_list.tail:
			self.linked_list.tail = node
		
		#we have to update the dictionary with the node !!!		
		self.dictionary[node.id] = node
	
	#remove last item (least frequently used)
	def remove_tail(self):
	
		#get node from the dictionary
		last_node = self.dictionary[self.linked_list.tail.id]
		#new tail node is the previous node (because we remove the actual one)
		self.linked_list.tail = self.linked_list.tail.previous_node
		
		#set the next node to be a NULL: because it is the right-most item
		if self.linked_list.tail:
			self.linked_list.tail.next_node = None
		
		#avoid obsolete references		
		last_node = None
	
	#get the item with ID id + move to the head because we've visited this item
	def get(self,id):
	
		#the dictionary does not contain the item [O(1) running time!!!]
		if not self.dictionary[id]:
			return None
		
		#the dictionary contains the item		
		node = self.dictionary[id]
		#move to the head (frequently visited items must be close to the head)
		self.update(node)
		
		return node
	
	#move the given node to the front (head)
	def update(self,node):
	
		#doubly linked list: we can get the previous node and the next node
		previous_node = node.previous_node
		next_node = node.next_node
		
		#so it is a middle node (not the head) in the list
		if previous_node:
			previous_node.next_node = next_node
		else: #we know that this is the head (first node)
			self.linked_list.head = next_node
		
		#so not the last node		
		if next_node:
			next_node.previous_node = previous_node
		else: #we know it is the last node
			self.linked_list.tail = previous_node
		
		#we have to move the node to the front
		self.add(node)
	
	def show(self):
	
		actual_node = self.linked_list.head
		
		#consider all the nodes in the linked list
		while actual_node:
			print("%s->"%actual_node.data)
			actual_node = actual_node.next_node
	
if __name__ == "__main__":
	
	cache = LRUCache()
		
	cache.put(0, 'A')
	cache.put(1, 'B')
	cache.put(2, 'C')
	cache.put(3, 'D')
	cache.put(4, 'E')
	cache.put(5, 'F')
	cache.put(6, 'G')
		
	cache.show()	
		
	print("Getting node: ",cache.get(6).data)
	cache.show()
	print()
		
	print("Getting node: ",cache.get(3).data)
	cache.show()
	print()
	
	print("Getting node: ",cache.get(4).data)
	cache.show()
Sharing is caring:

Leave a Comment