Lösning Förklaring
Runtime Complexity
get (hashset): O(1) i genomsnitt, O(n) i värsta fall
set (hashset): Konstant, O(1)
nedtagning i huvudet när ett nytt element läggs till (länkad lista): Konstant, O(1)
sökning för att ta bort och lägga till i slutet (länkad lista): Konstant, O(1)
sökning för att ta bort och lägga till i slutet (länkad lista): O(n)
Komplexitet: O(n)
Minneskomplexitet
Linjärt, O(n) där n är storleken på cacheminnet.
Lösningsuppdelning
Caching är en teknik för att lagra data i ett snabbare lagringsutrymme (vanligen RAM) för att kunna tillgodose framtida förfrågningar snabbare. Nedan följer några vanliga exempel där cache används:
- En processors cache används för att läsa data snabbare från huvudminnet (RAM).
- Cache i RAM kan användas för att lagra en del av diskdata i RAM och betjäna framtida förfrågningar snabbare.
- Nätverkssvar kan cachas i RAM för att undvika alltför många nätverksanrop.
Cache-lagret är dock vanligtvis inte tillräckligt stort för att lagra hela datasetet. Vi måste därför rensa ut data från cacheminnet när det blir fullt. Det finns ett antal cachingalgoritmer för att genomföra en policy för cacheutvisning. LRU är en mycket enkel och vanligt förekommande algoritm. LRU-algoritmens huvudkoncept är att ta bort de äldsta uppgifterna från cacheminnet för att få plats med fler uppgifter.
För att genomföra en LRU-cache använder vi två datastrukturer: en hashmap och en dubbelt länkad lista. En dubbelt länkad lista hjälper till att upprätthålla utvisningsordningen och en hashmap hjälper till med O(1)-sökning av nycklar i cacheminnet. Här följer algoritmen för 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 ReturnNotera att den dubbelt länkade listan används för att hålla reda på de senast åtkomna elementen. Elementet i slutet av den dubbelt länkade listan är det senast åtkomna elementet. Alla nyinsatta element (i put) går till slutet av listan. På samma sätt hamnar alla element som nås (vid en get-operation) i slutet av listan.
