Conas a dhéanann tú cache LRU a dhearadh le O(1) get agus put?

Question

Accepted Answer

**Cache LRU (Least Recently Used)** a bhíonn ann a bhagairt ar an mír nach raibh rochtain air don ghníomhaireacht is faide nuair a bhíonn sé ag socrú ar toilleadh. Cuimsíonn an dearadh clasaiceach **léarscáil hash** (O(1) cuardach) agus **liosta dhúbailte nasctha** (O(1) athord), ag tabhairt **O(1) get agus put**. ## 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 ``` `OrderedDict` is itself a hash map plus a doubly linked list, exactly the structure described above. | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## Why the doubly linked list Ligann liosta dhúbailte nasctha duit **nód a bhaint ar foluain ó lár an liosta in O(1)** (tá `prev`/`next` aici), rud atá dodhéanta le liosta aon-nasctha nó array gan athrú O(n). ## Cén fáth a bhíonn sé tábhachtach Suíonn caches LRU os comhair bunachar sonraí, freastalaithe gréasáin, agus CPUs chun sonraí te a choinneáil gasta agus cuimhne theorantach. Is príomhshampla den agallamh sinsearach an fhadhb seo toisc go dtástáil sé ar dhá struchtúr a chomhcheangal ionas go *fúitear locht an duine eile* — scil bhunúsach sa dhearadh córais.