Vysvětlení řešení
Složitost běhu
get (hashset): O(1) v průměrném případě, O(n) v nejhorším případě
set (hashset):
odstranění v záhlaví při přidání nového prvku (spojový seznam): Konstanta, O(1)
hledání při mazání a přidávání na chvost (spojový seznam): O(n)
Složitost:
Složitost paměti
Lineární, O(n), kde n je velikost cache.
Rozdělení řešení
Caching je technika ukládání dat do rychlejšího úložiště (obvykle RAM) pro rychlejší obsluhu budoucích požadavků. Níže jsou uvedeny některé běžné příklady, kde se cache používá:
- Cache procesoru se používá k rychlejšímu čtení dat z operační paměti (RAM).
- Cache v RAM lze použít k uložení části dat z disku do RAM a rychlejšímu obsloužení budoucích požadavků.
- Odpovědi ze sítě lze uložit do cache v RAM, aby se předešlo příliš mnoha síťovým voláním.
Uložiště cache však obvykle není dostatečně velké pro uložení celé sady dat. Proto musíme data z mezipaměti evokovat, kdykoli se zaplní. Existuje řada algoritmů pro implementaci politiky evikce dat z mezipaměti. LRU je velmi jednoduchý a běžně používaný algoritmus. Základní myšlenkou algoritmu LRU je evikovat nejstarší data z mezipaměti, aby se do ní vešla další data.
Pro implementaci mezipaměti LRU používáme dvě datové struktury: hashmapu a dvojitě spojený seznam. Dvojitě propojený seznam pomáhá udržovat pořadí evikce a hashmap pomáhá s O(1) vyhledáváním klíčů keše. Zde je uveden algoritmus pro LRU cache.
If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and ReturnVšimněte si, že dvojnásobně propojený seznam slouží ke sledování prvků, ke kterým se přistupovalo naposledy. Prvek na chvostu dvojitě propojeného seznamu je prvkem s nejnovějším přístupem. Všechny nově vložené prvky (in put) jdou na chvost seznamu. Podobně každý prvek, ke kterému se přistupuje (při operaci get), jde na chvost seznamu.
