Ratkaisun selitys
Ajan monimutkaisuus
get (hashset): O(1) keskimääräisessä tapauksessa, O(n) pahimmassa tapauksessa
set (hashset): Vakio, O(1)
poisto päässä, kun lisätään uusi elementti (linkitetty lista): Vakio, O(1)
haku poistettaessa ja lisättäessä perään (linkitetty lista): O(n)
Kompleksisuus: O(n)
Muistin monimutkaisuus
Lineaarinen, O(n), jossa n on välimuistin koko.
Ratkaisun erittely
Välimuistitallennus (caching) on tekniikka, jonka avulla dataa tallennetaan nopeampaan tallennuspaikkaan (tavallisesti RAM-muistiin), jotta voidaan palvella tulevia pyyntöjä nopeammin. Alla on joitakin yleisiä esimerkkejä, joissa välimuistia käytetään:
- Prosessorin välimuistia käytetään lukemaan dataa nopeammin keskusmuistista (RAM-muistista).
- Välimuistia RAM-muistissa voidaan käyttää tallentamaan osa levyn datasta RAM-muistiin ja palvelemaan tulevia pyyntöjä nopeammin.
- Verkkovastaukset voidaan tallentaa välimuistiin RAM-muistiin, jotta vältytään liian monilta verkonpuheluilta.
Välimuistivarasto ei kuitenkaan yleensä ole riittävän suuri tallentamaan koko tietokokonaisuuden. Niinpä tiedot on häädettävä välimuistista aina, kun se tulee täyteen. On olemassa useita välimuistialgoritmeja välimuistin häätökäytännön toteuttamiseksi. LRU on hyvin yksinkertainen ja yleisesti käytetty algoritmi. LRU-algoritmin ydinajatuksena on häätää vanhimmat tiedot välimuistista, jotta sinne mahtuisi lisää dataa.
LRU-välimuistin toteuttamiseksi käytämme kahta tietorakennetta: hashmapia ja kahdesti linkitettyä listaa. Kaksinkertaisesti linkitetty lista auttaa häätämisjärjestyksen ylläpitämisessä ja hashmap auttaa O(1):n hakemisessa välimuistissa olevista avaimista. Tässä on LRU-välimuistin algoritmi.
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 ReturnHuomaa, että kaksinkertaisesti linkitettyä listaa käytetään pitämään kirjaa viimeksi käytetyistä elementeistä. Kaksinkertaisesti linkitetyn listan häntäpäässä oleva elementti on elementti, jota on viimeksi käytetty. Kaikki äskettäin lisätyt elementit (in put) menevät listan perään. Vastaavasti kaikki elementit, joihin on päästy käsiksi (get-operaatiossa), menevät listan perään.
