A LRU gyorsítótár a Least Recently Used Cache (Legutóbb használt gyorsítótár) rövidítése, amely a legkevésbé használt bejegyzést kilakoltatja. Mivel a gyorsítótár célja az adatok gyors és hatékony lekérdezésének biztosítása, bizonyos követelményeknek kell megfelelnie.
A követelmények közül néhány
- Fixed Size:
- Gyors hozzáférés:
- A bejegyzés cseréje abban az esetben, ha a memóriahatár elérte a határt:
A cache-nek hatékony algoritmussal kell rendelkeznie a bejegyzés kilakoltatására, amikor a memória betelik.
Az LRU cache esetében a legkevésbé frissen használt bejegyzést kilakoltatjuk, így nyomon kell követnünk a frissen használt bejegyzéseket, a hosszú ideje nem használt bejegyzéseket és a nemrég használt bejegyzéseket. plusz a keresési és beszúrási műveletnek elég gyorsnak kell lennie.
Amikor O(1) keresésre gondolunk, nyilvánvaló adatstruktúra jut eszünkbe, a HashMap. A HashMap O(1) beszúrást és keresést biztosít. de a HashMap nem rendelkezik olyan mechanizmussal, amely nyomon követi, hogy melyik bejegyzést kérdezték le nemrég és melyiket nem.
Ezek nyomon követéséhez egy másik adatszerkezetre van szükségünk, amely gyors beszúrást ,törlést és frissítést biztosít, az LRU esetében a Doubly Linkedlist-et használjuk. A Doubly LinkList választásának oka az O(1) törlés , frissítés és beszúrás, ha megvan annak a Node-nak a címe, amelyen ezt a műveletet végre kell hajtani.
Az LRU cache implementációnk tehát HashMap és Doubly LinkedList lesz. Amelyben a HashMap fogja tartani a kulcsokat és a Doubly LinkedList csomópontjainak címét . És a Doubly LinkedList fogja tartani a kulcsok értékeit.
Mivel nyomon kell követnünk a nemrég használt bejegyzéseket, egy okos megközelítést fogunk használni. Eltávolítjuk az elemet alulról és hozzáadjuk az elemet a LinkedList elejére, és amikor bármelyik bejegyzéshez hozzáférünk, az a tetejére kerül. így a legutóbb használt bejegyzések a tetején, a legkevésbé használtak pedig az alján lesznek.
Végrehajtjuk az LRU Cache-t.
Remélem, a kód és a bemutató önmagyarázó.