Unakasogezeaje LRU cache na O(1) get na put?

Question

Accepted Answer

**LRU (Least Recently Used) cache** inaondoa kipengele ambacho hakikuzoishi kwa muda mrefu zaidi wakati inapofikia uwezo wake. Muundo wa kawaida unachanganya **hash map** (O(1) lookup) na **orodha iliyounganisha mara mbili** (O(1) upya), ukitoa **O(1) get na put**. ## Muundo wa miundo miwili ```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) ``` ## Codes ```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` ni hash map zaidi ya orodha iliyounganisha mara mbili, sawa na muundo ulioelezewa hapo juu. | Operesheni | Muda | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Kwa nini orodha iliyounganisha mara mbili Orodha iliyounganisha mara mbili inakuruhusu **kutenganisha nodi kutoka katikati katika O(1)** (unashika `prev`/`next` yake), ambayo haiwezekani na orodha iliyounganisha mara moja au hifadhi bila ubadilishe wa O(n). ## Kwa nini inasadikiwa LRU caches ziko mbele ya miundombinu, seva za mtandao, na processor ili kuweka data moto haraka na kumbukumbu iliyokamatwa. Ulizo hili ni tatizo la kawaida kwa mahojiano ya kizazi kikubwa kwa sababu inajaribu kuchanganya miundo miwili ili *kila moja inatumia ujinga wa nyingine* — ujinga muhimu wa muundo wa mifumo.