Kaip suprojektuoti LRU talpyklą su O(1) get ir put?

Question

Accepted Answer

**LRU (Least Recently Used) talpykla** iš talpyklos pašalina elementą, kuris buvo naudojamas seniausia, kai ji pasiekia pajėgumą. Klasikinis dizainas sujungia **hash map** (O(1) paieška) su **doubly linked list** (O(1) pergrupavimas), suteikdamas **O(1) get ir put**. ## Dviejų struktūrų dizainas ```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 ``` `OrderedDict` yra pati hash map ir doubly linked list, tiksliai tokia struktūra, kaip aprašyta aukščiau. | Operacija | Laikas | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Kodėl doubly linked list Douubly linked list leidžia jums **atjungti mazgą iš vidurio O(1)** (turite jo `prev`/`next`), kuri su single linked list arba masyvu be O(n) poslinkio neįmanoma. ## Kodėl tai svarbu LRU talpyklos sėdi priešais duomenų bazes, žiniatinklio serverius ir CPU, kad karšti duomenys būtų greitesni ir atmintis ribota. Ši problema yra standartinė vyresnio lygio pokalbio tema, nes ji bando sujungti dvi struktūras taip, kad *vienos žalumas būtų padengtas kitos* — pagrindinį sistemos projektavimo įgūdį.