Kuinka suunnittelet LRU-välimuistin O(1) get ja put -operaatioilla?

Question

Accepted Answer

**LRU (Least Recently Used) -välimuisti** poistaa kohteen, johon ei ole käyty käsiksi pisimpään aikaan, kun se saavuttaa kapasiteetin. Klassinen suunnittelu yhdistää **hash-kartan** (O(1) haku) ja **kaksoisinkilistan** (O(1) uudelleenjärjestys), mikä antaa **O(1) get ja put**. ## Kahden rakenteen suunnittelu ```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) ``` ## Koodi ```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` on itsessään hash-kartta plus kaksoisinkilistat, täsmälleen edellä kuvattu rakenne. | Operaatio | Aika | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Miksi kaksoisinkilistat Kaksoisinkilistat antavat sinulla **irrottaa solmu keskeltä O(1):ssa** (sinulla on sen `prev`/`next`), mikä on mahdotonta yksinkertaisella inkilistalla tai taulukolla ilman O(n) siirtoa. ## Miksi se on tärkeää LRU-välimuistit sijaitsevat tietokantojen, verkkopalvelimien ja CPU:iden edessä, jotta kuuma data pysyisi nopeana ja muisti rajoitettuna. Tämä ongelma on klassinen senior-haastattelussa, koska se testaa kahden rakenteen yhdistämistä siten, että *jokainen kattaa toisen heikkouden* - avaintaidossa järjestelmän suunnittelussa.