Hogyan tervezel egy LRU cache-t O(1) get és put művelettel?

Question

Accepted Answer

Egy **LRU (Least Recently Used) cache** eltávolítja azt az elemet, amelyre a leghosszabb ideje nem fértek hozzá, amikor elérte a kapacitását. A klasszikus tervezés egy **hash map** (O(1) lookup) és egy **kétirányú összekapcsolt lista** (O(1) átrendezés) kombinációja, amely **O(1) get és put** teljesítményt nyújt. ## The two-structure design ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Code ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` Az `OrderedDict` önmagában egy hash map és egy kétirányú összekapcsolt lista, pontosan az fenti struktúra. | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Why the doubly linked list Egy kétirányú összekapcsolt lista lehetővé teszi egy csomópont **O(1) alatt történő leválasztását a középből** (megtartod annak `prev`/`next` hivatkozásait), ami egy egyirányú összekapcsolt listánál vagy tömbben O(n) eltoláson nélkül lehetetlen. ## Miért fontos ez Az LRU cache-ek az adatbázisok, webkiszolgálók és CPU-k előtt helyezkednek el, hogy a forró adatokat gyorsnak és a memóriát korlátnak tartsák. Ez a probléma általános a senior interjúkban, mert tesztel két struktúra kombinálását úgy, hogy *az egyik hiánya a másik által fedezve legyen* — ez egy kulcsfontosságú rendszertervezési készség.