Hvad er LRU Cache?

Algoritmer til udskiftning af cache er effektivt designet til at erstatte cachen, når pladsen er fuld. Det Sidst brugt (LRU) er en af ​​disse algoritmer. Som navnet antyder, når cachehukommelsen er fuld, LRU vælger de data, der er brugt mindst for nylig, og fjerner dem for at gøre plads til de nye data. Prioriteten af ​​dataene i cachen ændres i overensstemmelse med behovet for disse data, dvs. hvis nogle data hentes eller opdateres for nylig, så vil disse datas prioritet blive ændret og tildelt den højeste prioritet, og prioriteten af ​​dataene falder, hvis den forbliver ubrugte operationer efter operationer.

Indholdsfortegnelse

• Hvad er LRU Cache?
• Operationer på LRU Cache:
• Arbejde med LRU Cache:
• Måder at implementere LRU-cache på:
• LRU-cache-implementering ved hjælp af kø og hashing:
• LRU-cache-implementering ved hjælp af dobbeltlinket liste og hashing:
• LRU-cache-implementering ved hjælp af Deque & Hashmap:
• LRU-cache-implementering ved hjælp af Stack & Hashmap:
• LRU-cache ved hjælp af tællerimplementering:
• LRU-cacheimplementering ved hjælp af Lazy Updates:
• Kompleksitetsanalyse af LRU-cache:
• Fordele ved LRU-cache:
• Ulemper ved LRU-cache:
• Real-World Anvendelse af LRU Cache:

LRU Algoritme er et standardproblem, og det kan have variationer efter behov, for eksempel i operativsystemer LRU spiller en afgørende rolle, da den kan bruges som en sideerstatningsalgoritme for at minimere sidefejl.

Operationer på LRU Cache:

• LRUCache (Kapacitet c): Initialiser LRU-cache med positiv størrelseskapacitet c.
• få (nøgle) : Returnerer værdien af ​​Key ' k' hvis det er til stede i cachen ellers returnerer det -1. Opdaterer også prioriteten af ​​data i LRU-cachen.
• put (nøgle, værdi): Opdater værdien af ​​nøglen, hvis denne nøgle findes. Ellers skal du tilføje nøgleværdi-par til cachen. Hvis antallet af nøgler overskred LRU-cachens kapacitet, skal du afvise den senest brugte nøgle.

Arbejde med LRU Cache:

Lad os antage, at vi har en LRU-cache med kapacitet 3, og vi vil gerne udføre følgende operationer:

1. Sæt (nøgle=1, værdi=A) i cachen
2. Sæt (nøgle=2, værdi=B) i cachen
3. Sæt (nøgle=3, værdi=C) i cachen
4. Hent (nøgle=2) fra cachen
5. Hent (nøgle=4) fra cachen
6. Sæt (nøgle=4, værdi=D) i cachen
7. Sæt (nøgle=3, værdi=E) i cachen
8. Hent (nøgle=4) fra cachen
9. Sæt (nøgle=1, værdi=A) i cachen

Ovenstående operationer udføres en efter en som vist på billedet nedenfor:

Detaljeret forklaring af hver operation:

1. Sæt (nøgle 1, værdi A) : Da LRU-cache har tom kapacitet=3, er der ikke behov for nogen erstatning, og vi sætter {1 : A} øverst, dvs. {1 : A} har højeste prioritet.
2. Sæt (nøgle 2, værdi B) : Da LRU-cachen har tom kapacitet=2, er der igen ikke behov for nogen udskiftning, men nu har {2 : B} den højeste prioritet og prioritet på {1 : A} reduktion.
3. Sæt (nøgle 3, værdi C) : Der er stadig 1 tom plads ledig i cachen, så indsæt {3 : C} uden nogen erstatning, bemærk nu, at cachen er fuld, og den aktuelle prioritetsrækkefølge fra højeste til laveste er {3:C}, {2:B }, {1:A}.
4. Hent (tast 2) : Returner nu værdien af ​​key=2 under denne operation, også da key=2 bruges, er den nye prioritetsrækkefølge nu {2:B}, {3:C}, {1:A}
5. Hent (nøgle 4): Bemærk, at nøgle 4 ikke er til stede i cachen, vi returnerer '-1' for denne operation.
6. Sæt (nøgle 4, værdi D) : Bemærk, at cachen er FULD, brug nu LRU-algoritmen til at bestemme, hvilken nøgle der er mindst brugt for nylig. Da {1:A} havde den mindste prioritet, skal du fjerne {1:A} fra vores cache og sætte {4:D} ind i cachen. Bemærk, at den nye prioritetsrækkefølge er {4:D}, {2:B}, {3:C}
7. Sæt (nøgle 3, værdi E) : Da key=3 allerede var til stede i cachen med værdien=C, vil denne operation ikke resultere i fjernelse af nogen nøgle, snarere vil den opdatere værdien af ​​key=3 til ' OG' . Nu bliver den nye prioritetsrækkefølge {3:E}, {4:D}, {2:B}
8. Hent (tast 4) : Returner værdien af ​​nøgle=4. Nu bliver ny prioritet {4:D}, {3:E}, {2:B}
9. Sæt (nøgle 1, værdi A) : Da vores cache er FULD, så brug vores LRU-algoritme til at bestemme, hvilken nøgle der blev brugt mindst for nylig, og da {2:B} havde den mindste prioritet, skal du fjerne {2:B} fra vores cache og sætte {1:A} i cache. Nu er den nye prioritetsrækkefølge {1:A}, {4:D}, {3:E}

Måder at implementere LRU-cache på:

LRU-cache kan implementeres på en række forskellige måder, og hver programmør kan vælge en anden tilgang. Nedenstående er dog almindeligt anvendte tilgange:

1. LRU ved hjælp af kø og hashing
2. LRU bruger Dobbelt linket liste + hashing
3. LRU ved hjælp af Deque
4. LRU ved hjælp af Stack
5. LRU bruger Modimplementering
6. LRU ved hjælp af Lazy Updates

LRU-cache-implementering ved hjælp af kø og hashing:

Vi bruger to datastrukturer til at implementere en LRU Cache.

1. Kø implementeres ved hjælp af en dobbelt-linket liste. Den maksimale størrelse af køen vil være lig med det samlede antal tilgængelige rammer (cachestørrelse). De senest brugte sider vil være tæt på forsiden, og de senest brugte sider vil være tæt på bagenden.
2. En Hash med sidenummeret som nøgle og adressen på den tilsvarende køknude som værdi.

Når der henvises til en side, kan den påkrævede side være i hukommelsen. Hvis det er i hukommelsen, skal vi fjerne listens node og bringe den foran i køen.
Hvis den påkrævede side ikke er i hukommelsen, bringer vi den i hukommelsen. Med enkle ord tilføjer vi en ny node foran i køen og opdaterer den tilsvarende nodeadresse i hashen. Hvis køen er fuld, dvs. alle rammer er fulde, fjerner vi en node fra den bagerste del af køen og tilføjer den nye node foran i køen.

Illustration:

Lad os overveje operationerne, Henviser nøgle x med i LRU-cachen: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Bemærk: Til at begynde med er der ingen side i hukommelsen.

Nedenstående billeder viser trin for trin udførelse af ovenstående operationer på LRU-cachen.

Algoritme:

• Opret en klasse LRUCache med erklære en liste af typen int, et uordnet kort af typen , og en variabel til at gemme den maksimale størrelse af cachen
• I referencefunktionen af ​​LRUCache
  • Hvis denne værdi ikke er til stede i køen, så skub denne værdi foran køen og fjern den sidste værdi, hvis køen er fuld
  • Hvis værdien allerede er til stede, så fjern den fra køen og skub den foran i køen
• I displayfunktionen print, LRUCache ved hjælp af køen starter forfra

Nedenfor er implementeringen af ​​ovenstående tilgang:

C++

>

>

C

java navngivningskonventioner

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

LRU-cache-implementering ved hjælp af dobbeltlinket liste og hashing :

Ideen er meget grundlæggende, dvs. bliv ved med at indsætte elementerne i hovedet.

• hvis elementet ikke er til stede på listen, skal du tilføje det til toppen af ​​listen
• hvis elementet er til stede på listen, skal du flytte elementet til hovedet og flytte det resterende element på listen

Bemærk, at nodens prioritet vil afhænge af afstanden mellem noden og hovedet, jo tættest noden er på hovedet, jo højere prioritet har den. Så når Cache-størrelsen er fuld, og vi skal fjerne et eller andet element, fjerner vi elementet, der støder op til halen af ​​den dobbeltforbundne liste.

LRU-cache-implementering ved hjælp af Deque & Hashmap:

Deque-datastruktur tillader indsættelse og sletning fra forsiden såvel som fra slutningen, denne egenskab muliggør implementering af LRU, da Front-element kan repræsentere højprioritetselement, mens slutelementet kan være lavprioritetselementet, dvs. Mindst nyligt brugt.

Arbejder:

1. Få Operation : Kontrollerer, om nøglen findes i cachens hash-kort, og følg nedenstående tilfælde på deque:
   • Hvis nøglen er fundet:
     • Varen anses for at være brugt for nylig, så den flyttes til forsiden af ​​deque.
     • Værdien forbundet med nøglen returneres som resultatet afget>operation.
   • Hvis nøglen ikke findes:
     • returner -1 for at angive, at en sådan nøgle ikke er til stede.
2. Put Operation: Tjek først, om nøglen allerede findes i cachens hash-kort, og følg nedenstående tilfælde på deque
   • Hvis nøglen findes:
     • Den værdi, der er knyttet til nøglen, opdateres.
     • Genstanden flyttes til forsiden af ​​deque, da den nu er den senest brugte.
   • Hvis nøglen ikke findes:
     • Hvis cachen er fuld, betyder det, at en ny genstand skal indsættes, og den mindst nyligt brugte genstand skal smides ud. Dette gøres ved at fjerne emnet fra slutningen af ​​deque og den tilsvarende indtastning fra hash-kortet.
     • Det nye nøgle-værdi-par indsættes derefter i både hash-kortet og forsiden af ​​deque for at angive, at det er det senest brugte element

LRU-cache-implementering ved hjælp af Stack & Hashmap:

Implementering af en LRU (Least Recently Used) cache ved hjælp af en stak datastruktur og hashing kan være en smule vanskelig, fordi en simpel stak ikke giver effektiv adgang til det mindst nyligt brugte element. Du kan dog kombinere en stak med et hash-kort for at opnå dette effektivt. Her er en tilgang på højt niveau til at implementere det:

1. Brug et Hash-kort : Hash-kortet gemmer nøgleværdi-parrene i cachen. Nøglerne vil afbildes til de tilsvarende noder i stakken.
2. Brug en stak : Stakken vil bevare nøglerækkefølgen baseret på deres brug. Det senest brugte element vil være i bunden af ​​stakken, og det senest brugte element vil være øverst

Denne tilgang er ikke så effektiv og bruges derfor ikke ofte.

LRU-cache ved hjælp af tællerimplementering:

Hver blok i cachen vil have sin egen LRU-tæller, hvor værdien af ​​tælleren hører til {0 til n-1} , her ' n ' repræsenterer størrelsen af ​​cachen. Blokken, der ændres under blokudskiftningen, bliver MRU-blokken, og som følge heraf ændres dens tællerværdi til n – 1. Tællerværdierne, der er større end den tilgåede bloks tællerværdi, dekrementeres med én. De resterende blokke er uændrede.

LRU-cacheimplementering ved hjælp af Lazy Updates:

Implementering af en LRU (Least Recently Used) cache ved hjælp af dovne opdateringer er en almindelig teknik til at forbedre effektiviteten af ​​cachens operationer. Dovne opdateringer involverer sporing af rækkefølgen, hvori der tilgås elementer uden øjeblikkelig opdatering af hele datastrukturen. Når der opstår en cache-miss, kan du beslutte, om du vil udføre en fuld opdatering baseret på nogle kriterier.

Kompleksitetsanalyse af LRU-cache:

• Tidskompleksitet:
  • Put() operation: O(1) dvs. den tid, der kræves til at indsætte eller opdatere nyt nøgleværdi-par, er konstant
  • Get() operation: O(1) dvs. den tid, der kræves for at få værdien af ​​en nøgle, er konstant
• Hjælpeplads: O(N) hvor N er cachens kapacitet.

Fordele ved LRU-cache:

• Hurtig adgang : Det tager O(1) tid at få adgang til dataene fra LRU-cachen.
• Hurtig opdatering : Det tager O(1) tid at opdatere et nøgleværdi-par i LRU-cachen.
• Hurtig fjernelse af senest brugte data : Det kræver O(1) at slette det, der ikke er blevet brugt for nylig.
• Ingen tæsk: LRU er mindre modtagelig for tæsk sammenlignet med FIFO, fordi den tager hensyn til sidernes brugshistorik. Den kan registrere, hvilke sider der bruges ofte og prioritere dem til hukommelsesallokering, hvilket reducerer antallet af sidefejl og disk I/O-operationer.

Ulemper ved LRU-cache:

• Det kræver stor cachestørrelse for at øge effektiviteten.
• Det kræver yderligere datastruktur at blive implementeret.
• Hardwarehjælpen er høj.
• I LRU er fejldetektion vanskelig sammenlignet med andre algoritmer.
• Det har begrænset accept.

Real-World Anvendelse af LRU Cache:

• I databasesystemer for hurtige forespørgselsresultater.
• I operativsystemer for at minimere sidefejl.
• Teksteditorer og IDE'er til at gemme ofte brugte filer eller kodestykker
• Netværksroutere og switche bruger LRU til at øge effektiviteten af ​​computernetværk
• I compiler-optimeringer
• Værktøjer til tekstforudsigelse og autofuldførelse