LRU-välimuisti on lyhenne sanoista Least Recently Used Cache (vähiten hiljattain käytetty välimuisti), joka häätää viimeksi käytetyn merkinnän. Koska välimuistin tarkoitus on tarjota nopea ja tehokas tapa hakea tietoja, sen on täytettävä tietyt vaatimukset.
Joitakin vaatimuksia ovat
- Kiinteä koko:
- Nopea pääsy:
- Kirjauksen korvaaminen, jos muistiraja saavutetaan:
Jos kyseessä on LRU-välimuisti, häädämme vähiten hiljattain käytetyn merkinnän, joten meidän on pidettävä kirjaa hiljattain käytetyistä merkinnöistä, merkinnöistä, joita ei ole käytetty pitkään aikaan ja joita on käytetty hiljattain. Lisäksi haku- ja lisäysoperaation pitäisi olla riittävän nopea.
Kun ajattelemme O(1) hakuaikaa, ilmeinen tietorakenne, joka tulee mieleemme, on HashMap. HashMap tarjoaa O(1) lisäyksen ja haun. mutta HashMapissa ei ole mekanismia, jolla voidaan seurata, mitä merkintää on kysytty hiljattain ja mitä ei.
Tämän seuraamiseksi tarvitsemme toisen tietorakenteen, joka tarjoaa nopean lisäyksen, poiston ja päivityksen, LRU:n tapauksessa käytämme Doubly Linkedlistia. Syy tuplalinkkilistan valintaan on O(1) poisto , päivitys ja lisäys, jos meillä on sen solmun osoite, jolle tämä operaatio on suoritettava.
Siten LRU-välimuistin toteutuksessamme on HashMap ja Doubly LinkedList. Jossa HashMap pitää Doubly LinkedListin solmujen avaimet ja osoitteet. Ja Doubly LinkedList pitää hallussaan avainten arvot.
Koska meidän on seurattava hiljattain käytettyjä merkintöjä, käytämme fiksua lähestymistapaa. Poistamme elementin alareunasta ja lisäämme elementin LinkedListin alkuun, ja aina kun jotain merkintää käytetään, se siirretään yläreunaan, jotta viimeksi käytetyt merkinnät ovat yläreunassa ja vähiten käytetyt alareunassa.
Toteutetaan LRU-välimuisti.
Toivon, että koodi ja opetusohjelma on itsestään selvä.