Vad är LRU Cache?

Algoritmer för cacheersättning är effektivt utformade för att ersätta cachen när utrymmet är fullt. De Senast använda (LRU) är en av dessa algoritmer. Som namnet antyder när cacheminnet är fullt, LRU väljer den data som har använts minst nyligen och tar bort den för att göra utrymme för den nya datan. Prioriteten för datan i cachen ändras i enlighet med behovet av den datan, dvs om vissa data hämtas eller uppdateras nyligen så skulle prioriteten för den datan ändras och tilldelas högsta prioritet, och prioriteten för datan minskar om den kvarstår oanvända operationer efter operationer.

Innehållsförteckning

• Vad är LRU Cache?
• Operationer på LRU-cache:
• LRU-cache fungerar:
• Sätt att implementera LRU-cache:
• LRU-cacheimplementering med hjälp av Queue och Hashing:
• LRU-cacheimplementering med dubbellänkad lista och hashing:
• LRU-cache-implementering med Deque & Hashmap:
• LRU-cache-implementering med Stack & Hashmap:
• LRU-cache med hjälp av Counter Implementation:
• LRU-cacheimplementering med hjälp av Lazy Updates:
• Komplexitetsanalys av LRU-cache:
• Fördelar med LRU-cache:
• Nackdelar med LRU-cache:
• Real-World Application av LRU Cache:

LRU Algoritm är ett standardproblem och det kan ha variationer efter behov, till exempel i operativsystem LRU spelar en avgörande roll eftersom den kan användas som en sidbytesalgoritm för att minimera sidfel.

Operationer på LRU-cache:

• LRUCache (Kapacitet c): Initiera LRU-cache med positiv storlekskapacitet c.
• få (nyckel) : Returnerar värdet på Key ' k' om den finns i cachen annars returnerar den -1. Uppdaterar även dataprioriteten i LRU-cachen.
• put (nyckel, värde): Uppdatera nyckelns värde om den nyckeln finns. Annars lägger du till nyckel-värdepar i cachen. Om antalet nycklar överskrider kapaciteten för LRU-cachen, avvisa den senast använda nyckeln.

LRU-cache fungerar:

Låt oss anta att vi har en LRU-cache med kapacitet 3, och vi skulle vilja utföra följande operationer:

1. Lägg (nyckel=1, värde=A) i cachen
2. Lägg (nyckel=2, värde=B) i cachen
3. Lägg (nyckel=3, värde=C) i cachen
4. Hämta (nyckel=2) från cachen
5. Hämta (nyckel=4) från cachen
6. Lägg (nyckel=4, värde=D) i cachen
7. Lägg (nyckel=3, värde=E) i cachen
8. Hämta (nyckel=4) från cachen
9. Lägg (nyckel=1, värde=A) i cachen

Ovanstående operationer utförs en efter en som visas i bilden nedan:

Detaljerad förklaring av varje operation:

1. Sätt (nyckel 1, värde A) : Eftersom LRU-cachen har tom kapacitet=3, behövs ingen ersättning och vi sätter {1 : A} överst, dvs. {1 : A} har högsta prioritet.
2. Sätt (nyckel 2, värde B) : Eftersom LRU-cachen har tom kapacitet=2, finns det återigen inget behov av någon ersättning, men nu har {2 : B} högsta prioritet och prioritet av {1 : A}-minskning.
3. Sätt (nyckel 3, värde C) : Det finns fortfarande 1 tomt utrymme ledigt i cachen, lägg därför {3 : C} utan någon ersättning, märk nu att cachen är full och den nuvarande prioritetsordningen från högsta till lägsta är {3:C}, {2:B }, {1:A}.
4. Hämta (nyckel 2) : Returnera nu värdet på key=2 under denna operation, eftersom key=2 används, är den nya prioritetsordningen nu {2:B}, {3:C}, {1:A}
5. Hämta (nyckel 4): Observera att nyckel 4 inte finns i cachen, vi returnerar '-1' för denna operation.
6. Sätt (nyckel 4, värde D) : Observera att cachen är FULL, använd nu LRU-algoritmen för att avgöra vilken nyckel som senast användes. Eftersom {1:A} hade minst prioritet, ta bort {1:A} från vår cache och placera {4:D} i cachen. Observera att den nya prioritetsordningen är {4:D}, {2:B}, {3:C}
7. Sätt (nyckel 3, värde E) : Eftersom key=3 redan fanns i cachen med värdet=C, så kommer denna operation inte att resultera i att någon nyckel tas bort, snarare kommer den att uppdatera värdet på key=3 till ' OCH' . Nu kommer den nya prioritetsordningen att bli {3:E}, {4:D}, {2:B}
8. Hämta (nyckel 4) : Returnera värdet för nyckel=4. Nu kommer ny prioritet att bli {4:D}, {3:E}, {2:B}
9. Sätt (nyckel 1, värde A) : Eftersom vår cache är FULL, så använd vår LRU-algoritm för att avgöra vilken nyckel som användes senast, och eftersom {2:B} hade minst prioritet, ta bort {2:B} från vår cache och lägg in {1:A} i cache. Nu är den nya prioritetsordningen {1:A}, {4:D}, {3:E}

Sätt att implementera LRU-cache:

LRU-cache kan implementeras på en mängd olika sätt, och varje programmerare kan välja ett annat tillvägagångssätt. Men nedan är vanliga metoder:

1. LRU använder Queue och Hashing
2. LRU använder Dubbelt länkad lista + hashing
3. LRU använder Deque
4. LRU använder Stack
5. LRU använder Motimplementering
6. LRU använder Lazy Updates

LRU-cacheimplementering med hjälp av Queue och Hashing:

Vi använder två datastrukturer för att implementera en LRU-cache.

1. Kö implementeras med hjälp av en dubbellänkad lista. Den maximala storleken på kön kommer att vara lika med det totala antalet tillgängliga ramar (cachestorlek). De senast använda sidorna kommer att vara nära framsidan och de senast använda sidorna kommer att vara nära baksidan.
2. En Hash med sidnumret som nyckel och adressen till motsvarande könod som värde.

När en sida refereras kan den önskade sidan finnas i minnet. Om det finns i minnet måste vi ta bort noden på listan och föra den längst fram i kön.
Om den önskade sidan inte finns i minnet tar vi med den i minnet. Med enkla ord lägger vi till en ny nod längst fram i kön och uppdaterar motsvarande nodadress i hashen. Om kön är full, det vill säga alla ramar är fulla, tar vi bort en nod från den bakre delen av kön och lägger till den nya noden längst fram i kön.

Illustration:

Låt oss överväga operationerna, Hänvisar nyckel x med i LRU-cachen: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Notera: Till en början finns ingen sida i minnet.

Nedan bilder visar steg för steg exekvering av ovanstående operationer på LRU-cachen.

Algoritm:

• Skapa en klass LRUCache med deklarera en lista av typen int, en oordnad karta av typen , och en variabel för att lagra den maximala storleken på cachen
• I referensfunktionen för LRUCache
  • Om detta värde inte finns i kön, skjut det här värdet framför kön och ta bort det sista värdet om kön är full
  • Om värdet redan finns, ta bort det från kön och skjut det längst fram i kön
• I displayfunktionen skriver ut LRUCache med hjälp av kön som börjar framifrån

Nedan är implementeringen av ovanstående tillvägagångssätt:

C++

strängformatering java

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

LRU-cache-implementering med dubbellänkad lista och hashing :

Tanken är väldigt grundläggande, d.v.s. fortsätt att sätta in elementen vid huvudet.

• om elementet inte finns i listan, lägg till det i huvudet på listan
• om elementet finns i listan, flytta elementet till huvudet och flytta det återstående elementet i listan

Observera att nodens prioritet kommer att bero på nodens avstånd från huvudet, ju närmast noden är huvudet, högre prioritet har den. Så när Cache-storleken är full och vi behöver ta bort något element, tar vi bort elementet intill svansen av den dubbelt länkade listan.

LRU-cache-implementering med Deque & Hashmap:

Deque-datastrukturen tillåter infogning och radering från fronten såväl som från slutet, den här egenskapen möjliggör implementering av LRU eftersom frontelementet kan representera högprioritetselement medan slutelementet kan vara lågprioritetselementet, d.v.s. minst nyligen använt.

Arbetssätt:

1. Få Operation : Kontrollerar om nyckeln finns i cachens hashkarta och följ nedanstående fall på deque:
   • Om nyckel hittas:
     • Objektet anses vara nyligen använt, så det flyttas till framsidan av deque.
     • Värdet som är associerat med nyckeln returneras som ett resultat avget>drift.
   • Om nyckeln inte hittas:
     • returnera -1 för att indikera att ingen sådan nyckel finns.
2. Put Operation: Kontrollera först om nyckeln redan finns i cachens hashkarta och följ nedanstående fall på dequen
   • Om nyckel finns:
     • Värdet som är kopplat till nyckeln uppdateras.
     • Objektet flyttas till framsidan av dequet eftersom det nu är det senast använda.
   • Om nyckeln inte finns:
     • Om cachen är full betyder det att ett nytt föremål måste infogas och det senast använda föremålet måste vräkas. Detta görs genom att ta bort objektet från slutet av dequen och motsvarande post från hashkartan.
     • Det nya nyckel-värdeparet infogas sedan i både hashkartan och framsidan av dequen för att indikera att det är det senast använda föremålet

LRU-cache-implementering med Stack & Hashmap:

Att implementera en LRU (Last Recently Used) cache med hjälp av en stackdatastruktur och hash kan vara lite knepigt eftersom en enkel stack inte ger effektiv åtkomst till det senast använda objektet. Du kan dock kombinera en stack med en hashkarta för att uppnå detta effektivt. Här är en metod på hög nivå för att implementera det:

1. Använd en Hash-karta : Hashkartan lagrar nyckel-värdeparen i cachen. Nycklarna kommer att mappas till motsvarande noder i stacken.
2. Använd en stack : Stacken kommer att behålla ordningen på nycklar baserat på deras användning. Det senast använda föremålet kommer att vara längst ner i stapeln, och det senast använda föremålet kommer att vara överst

Detta tillvägagångssätt är inte så effektivt och används därför inte ofta.

nätverk och typer

LRU-cache med hjälp av Counter Implementation:

Varje block i cachen kommer att ha sin egen LRU-räknare där värdet på räknaren tillhör {0 till n-1} , här' n ' representerar storleken på cachen. Blocket som ändras under blockersättningen blir MRU-blocket, och som ett resultat ändras dess räknarvärde till n – 1. Räknarvärdena som är större än det åtkomliga blockets räknarvärde minskas med ett. De återstående blocken är oförändrade.

LRU-cacheimplementering med hjälp av Lazy Updates:

Att implementera en LRU (Least Recently Used) cache med lata uppdateringar är en vanlig teknik för att förbättra effektiviteten i cachens operationer. Lata uppdateringar innebär att spåra i vilken ordning objekt nås utan att omedelbart uppdatera hela datastrukturen. När en cachemiss inträffar kan du sedan bestämma om du vill utföra en fullständig uppdatering eller inte baserat på vissa kriterier.

Komplexitetsanalys av LRU-cache:

• Tidskomplexitet:
  • Put() operation: O(1) d.v.s. tiden som krävs för att infoga eller uppdatera nytt nyckel-värdepar är konstant
  • Get() operation: O(1) dvs tiden som krävs för att få värdet på en nyckel är konstant
• Hjälputrymme: O(N) där N är cachens kapacitet.

Fördelar med LRU-cache:

• Snabb åtkomst : Det tar O(1) tid att komma åt data från LRU-cachen.
• Snabb uppdatering : Det tar O(1) tid att uppdatera ett nyckel-värdepar i LRU-cachen.
• Snabb borttagning av senast använda data : Det tar O(1) att ta bort det som inte har använts nyligen.
• Ingen smäll: LRU är mindre mottaglig för thrashing jämfört med FIFO eftersom den tar hänsyn till sidornas användningshistorik. Den kan upptäcka vilka sidor som används ofta och prioritera dem för minnesallokering, vilket minskar antalet sidfel och disk I/O-operationer.

Nackdelar med LRU-cache:

• Det kräver stor cachestorlek för att öka effektiviteten.
• Det kräver ytterligare datastruktur för att implementeras.
• Hårdvaruhjälpen är hög.
• I LRU är feldetektering svårt jämfört med andra algoritmer.
• Det har begränsad acceptans.

Real-World Application av LRU Cache:

• I databassystem för snabba frågeresultat.
• I operativsystem för att minimera sidfel.
• Textredigerare och IDE:er för att lagra ofta använda filer eller kodavsnitt
• Nätverksroutrar och switchar använder LRU för att öka effektiviteten i datornätverk
• I kompilatoroptimeringar
• Verktyg för textprediktion och autokomplettering