Løsning Forklaring
Runtime kompleksitet
get (hashset): O(1) i det gennemsnitlige tilfælde, O(n) i det værste tilfælde
set (hashset):: O(1) i det gennemsnitlige tilfælde, O(n) i det værste tilfælde
set (hashset): Konstant, O(1)
sletning i hovedet, når der tilføjes et nyt element (linked list): Konstant, O(1)
søgning ved sletning og tilføjelse til hale (linked list): O(n)
Kompleksitet: O(n)
Kompleksitet: O(n)
Hukommelseskompleksitet
Linear, O(n), hvor n er størrelsen af cachen.
Løsningsopdeling
Caching er en teknik til at lagre data i et hurtigere lager (normalt RAM) for at kunne betjene fremtidige anmodninger hurtigere. Nedenfor er nogle almindelige eksempler, hvor cache bruges:
- En processorcache bruges til at læse data hurtigere fra hovedhukommelsen (RAM).
- Cache i RAM kan bruges til at gemme en del af diskdata i RAM og betjene fremtidige anmodninger hurtigere.
- Netværkssvar kan caches i RAM for at undgå for mange netværksopkald.
Cachelageret er dog normalt ikke stort nok til at gemme det fulde datasæt. Så vi er nødt til at fjerne data fra cachen, når den bliver fuld. Der findes en række caching-algoritmer til at implementere en politik til fjernelse af cache-data. LRU er meget enkel og en almindeligt anvendt algoritme. LRU-algoritmens kernekoncept er at fjerne de ældste data fra cachen for at få plads til flere data.
For at implementere en LRU-cache bruger vi to datastrukturer: en hashmap og en dobbeltkoblet liste. En dobbeltkoblet liste hjælper med at opretholde udvisningsrækkefølgen, og en hashmap hjælper med O(1)-opslag af cachede nøgler. Her følger algoritmen for 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 ReturnIf 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 ReturnBemærk, at den dobbeltkædede liste bruges til at holde styr på de senest tilgåede elementer. Elementet i halen af den dobbeltkædede liste er det senest tilgåede element. Alle nyligt indsatte elementer (i put) går til listens hale. På samme måde kommer ethvert element, hvortil der er adgang (ved get-operationen), til listens hale.
