LRU-cache staat voor Least Recently Used Cache. die het minst recent gebruikte item uitzet. Cache is bedoeld om snel en efficiënt gegevens op te halen. Het moet aan bepaalde eisen voldoen.
Enkele van de eisen zijn
- Vaste grootte: Cache moet enkele grenzen hebben om geheugengebruik te beperken.
- Snelle toegang: Cache Insert en lookup operatie moet snel zijn, bij voorkeur O(1) tijd.
- Vervangen van Entry in geval , geheugen limiet is bereikt: Een cache moet een efficiënt algoritme hebben om de entry te verwijderen wanneer het geheugen vol is.
In het geval van LRU cache verwijderen we de minst recent gebruikte entry, dus we moeten bijhouden welke entries recent gebruikt zijn, entries die niet lang gebruikt zijn en welke recent gebruikt zijn. plus lookup en insertion operaties moeten snel genoeg zijn.
Wanneer we denken aan O(1) lookup, is de voor de hand liggende datastructuur die in ons hoofd opkomt HashMap. HashMap biedt O(1) invoegen en opzoeken, maar HashMap heeft geen mechanisme om bij te houden welke invoer onlangs is opgevraagd en welke niet.
Om dit bij te houden hebben we een andere gegevensstructuur nodig die snel invoegen, verwijderen en bijwerken biedt, in het geval van LRU gebruiken we de dubbele gekoppelde lijst. De reden voor het kiezen van dubbele LinkList is O(1) verwijderen , bijwerken en invoegen als we het adres van Node waarop deze operatie moet worden uitgevoerd.
Dus onze implementatie van LRU cache zal HashMap en Doubly LinkedList hebben. Waarin de HashMap de sleutels en het adres van de Nodes van de Doubly LinkedList bevat. En de Doubly LinkedList de waarden van de sleutels bevat.
Om de recent gebruikte items bij te houden, gebruiken we een slimme aanpak. We verwijderen het element onderaan en voegen het toe aan het begin van de LinkedList. Telkens wanneer een item wordt geopend, wordt het naar boven verplaatst, zodat de recent gebruikte items bovenaan staan en de minst gebruikte onderaan.
Laat de LRU Cache implementeren.
Ik hoop dat de code en handleiding voor zichzelf spreken.