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 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()