Belajar Data Structure - LRU Cache & LFU Cache
LRU dan LFU cache adalah dua strategi eviction yang paling umum digunakan. Di episode ini kalian memahami LRU dengan doubly-linked list dan hash map untuk O(1) get/put, LFU dengan bucket-based eviction untuk least frequently used, serta mempraktikkan implementasi LRU cache dari nol.
#Pendahuluan
Setelah di episode 21 kita memahami bloom filter dan count-min sketch — struktur data probabilistik — pada episode ini kita mempelajari LRU cache dan LFU cache, dua strategi eviction yang paling umum digunakan dalam caching systems. Cache adalah lapisan penyimpanan cepat di depan penyimpanan lambat, dan ketika cache penuh, kita perlu strategi untuk memutuskan elemen mana yang harus dikeluarkan.
LRU (Least Recently Used) dan LFU (Least Frequently Used) menjawab pertanyaan yang berbeda: LRU bertanya "kapan terakhir kali ini dipakai?", sementara LFU bertanya "seberapa sering ini dipakai?". Pemilihan antara keduanya tergantung pada pola akses aplikasi kalian.
#LRU Cache
#Konsep
LRU cache mengeluarkan elemen yang paling lama tidak diakses. Dua struktur data digabungkan:
- Doubly-linked list: menjaga urutan akses (paling baru di depan, paling lama di belakang)
- Hash map: mapping key → node di linked list untuk akses O(1)
#Implementasi dari Nol
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.value
return -1
def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._add_to_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]#Kompleksitas
- Get: O(1)
- Put: O(1)
- Space: O(capacity)
#LFU Cache
#Konsep
LFU cache mengeluarkan elemen yang paling jarang diakses. Lebih kompleks dari LRU: memerlukan frequency counter dan bucket-based eviction.
#Strategi Bucket-Based
Setiap frequency memiliki bucket sendiri. Ketika akses bertambah, elemen pindah ke bucket frequency berikutnya. Ketika cache penuh, hapus dari bucket frequency terendah (dan jika ada lebih dari satu, hapus yang paling lama).
#Implementasi Sederhana
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.freq = defaultdict(OrderedDict)
self.min_freq = 0
def get(self, key):
if key not in self.cache:
return -1
value, f = self.cache[key]
del self.freq[f][key]
if not self.freq[f]:
del self.freq[f]
if self.min_freq == f:
self.min_freq += 1
self.freq[f + 1][key] = value
self.cache[key] = (value, f + 1)
return value
def put(self, key, value):
if self.capacity == 0:
return
if key in self.cache:
self.get(key)
self.cache[key] = (value, self.cache[key][1])
return
if len(self.cache) >= self.capacity:
del_key, _ = self.freq[self.min_freq].popitem(last=False)
if not self.freq[self.min_freq]:
del self.freq[self.min_freq]
del self.cache[del_key]
self.min_freq = 1
self.freq[1][key] = value
self.cache[key] = (value, 1)#Perbandingan LRU vs LFU
| Aspek | LRU | LFU |
|---|---|---|
| Eviction | Least recently used | Least frequently used |
| Implementasi | Lebih sederhana | Lebih kompleks |
| Scan resistance | Rendah | Tinggi |
| Overhead | Pointer per node | Frequency counter + buckets |
| Use case | Web cache, CDN | Database buffer, CDN |
#Scan Resistance
LRU rentan terhadap scan: akses sekali ke banyak elemen baru bisa mengeluarkan elemen populer dari cache. LFU lebih tahan karena frequency menunjukkan pola jangka panjang.
#Praktik: LRU Cache untuk API Response
lru = LRUCache(3)
lru.put("user:1", "Alice")
lru.put("user:2", "Bob")
lru.put("user:3", "Charlie")
print(lru.get("user:1"))
lru.put("user:4", "Diana")
print(lru.get("user:2"))Note
Python functools.lru_cache adalah decorator built-in yang mengimplementasikan LRU caching untuk fungsi. Gunakan ini untuk memoization fungsi tanpa perlu implementasi manual. Contoh: @lru_cache(maxsize=128).
#Penutup
Inti yang harus dibawa pulang:
- LRU: doubly-linked list + hash map → O(1) get/put, evicts least recently used.
- LFU: frequency counter + buckets → evicts least frequently used, lebih kompleks.
- LRU rentan scan; LFU lebih tahan tetapi overhead lebih tinggi.
- Aplikasi: web cache, CDN, database buffer, API response caching.
- Python
functools.lru_cacheuntuk memoization fungsi.
Di episode 23 selanjutnya kita akan membahas suffix array dan suffix tree — dua struktur data untuk pattern matching pada string. Suffix array adalah array terurut semua suffix, suffix tree adalah trie dari semua suffix. Keduanya powerful untuk full-text search dan DNA sequence analysis. Ini adalah episode terakhir di Fase 5: Struktur Lanjutan & Khusus!