LRU cache înseamnă Least Recently Used Cache (memoria cache utilizată cel mai recent). care evacuează intrarea utilizată cel mai recent. Deoarece scopul cache-ului este de a oferi o modalitate rapidă și eficientă de recuperare a datelor, acesta trebuie să îndeplinească anumite cerințe.
Câteva dintre cerințe sunt
- Dimensiunea fixă: Memoria cache trebuie să aibă anumite limite pentru a limita utilizarea memoriei.
- Acces rapid: Operațiunea de inserare și consultare a memoriei cache trebuie să fie rapidă, de preferință în timp O(1).
- Înlocuirea intrărilor în cazul în care se atinge limita de memorie: O memorie cache ar trebui să dispună de un algoritm eficient pentru a evacua intrarea atunci când memoria este plină.
În cazul cache-ului LRU, evacuăm intrarea cea mai puțin utilizată recent, astfel încât trebuie să ținem evidența intrărilor utilizate recent, a intrărilor care nu au fost utilizate de mult timp și a celor care au fost utilizate recent. în plus, operațiunea de căutare și inserție ar trebui să fie suficient de rapidă.
Când ne gândim la o căutare O(1), structura de date evidentă care ne vine în minte este HashMap. HashMap asigură o inserție și o căutare O(1), dar HashMap nu dispune de un mecanism de urmărire a intrărilor care au fost interogate recent și care nu.
Pentru a urmări acest lucru avem nevoie de o altă structură de date care să asigure o inserție, ștergere și actualizare rapidă, în cazul LRU folosim Doubly Linkedlist. Motivul pentru care am ales Doublely LinkList este O(1) de ștergere, actualizare și inserție dacă avem adresa nodului pe care trebuie efectuată această operațiune.
Așa că implementarea noastră a cache-ului LRU va avea HashMap și Doubly LinkedList. În care HashMap va conține cheile și adresele nodurilor din Doubly LinkedList. Iar Doubly LinkedList va conține valorile cheilor.
Cum trebuie să ținem evidența intrărilor utilizate recent, vom folosi o abordare inteligentă. Vom elimina elementul din partea de jos și vom adăuga un element la începutul LinkedList-ului și, ori de câte ori este accesată o intrare, aceasta va fi mutată în partea de sus. astfel încât intrările utilizate recent vor fi în partea de sus, iar cele mai puțin utilizate vor fi în partea de jos.
Să implementăm memoria cache LRU.
Sper să se explice de la sine codul și tutorialul.
.