Hva er LRU Cache?

Buffererstatningsalgoritmer er effektivt utformet for å erstatte hurtigbufferen når plassen er full. De Minst nylig brukt (LRU) er en av disse algoritmene. Som navnet antyder når hurtigbufferminnet er fullt, LRU velger dataene som er minst nylig brukt og fjerner dem for å gi plass til de nye dataene. Prioriteten til dataene i hurtigbufferen endres i henhold til behovet for disse dataene, dvs. hvis noen data hentes eller oppdateres nylig, vil prioriteten til disse dataene bli endret og tildelt den høyeste prioritet, og prioriteten til dataene reduseres hvis den forblir ubrukte operasjoner etter operasjoner.

Innholdsfortegnelse

• Hva er LRU Cache?
• Operasjoner på LRU Cache:
• Arbeid med LRU Cache:
• Måter å implementere LRU Cache:
• LRU-bufferimplementering ved bruk av kø og hashing:
• LRU-bufferimplementering ved hjelp av dobbeltlenkede liste og hashing:
• LRU-bufferimplementering ved hjelp av Deque & Hashmap:
• LRU-bufferimplementering ved bruk av Stack & Hashmap:
• LRU-buffer ved bruk av Counter-implementering:
• LRU-bufferimplementering ved hjelp av Lazy Updates:
• Kompleksitetsanalyse av LRU Cache:
• Fordeler med LRU-cache:
• Ulemper med LRU-cache:
• Real-World-applikasjon av LRU Cache:

LRU Algoritme er et standardproblem, og det kan ha variasjoner etter behov, for eksempel i operativsystemer LRU spiller en avgjørende rolle siden den kan brukes som en sideerstatningsalgoritme for å minimere sidefeil.

Operasjoner på LRU Cache:

• LRUCache (Kapasitet c): Initialiser LRU-cache med positiv størrelseskapasitet c.
• få (nøkkel) : Returnerer verdien av Key ' k' hvis den er til stede i cachen ellers returnerer den -1. Oppdaterer også prioriteten til data i LRU-cachen.
• put (nøkkel, verdi): Oppdater verdien til nøkkelen hvis denne nøkkelen eksisterer. Ellers legger du til nøkkelverdi-paret i hurtigbufferen. Hvis antallet nøkler overskred kapasiteten til LRU-hurtigbufferen, avvis den sist brukte nøkkelen.

Arbeid med LRU Cache:

La oss anta at vi har en LRU-cache med kapasitet 3, og vi ønsker å utføre følgende operasjoner:

1. Sett (nøkkel=1, verdi=A) inn i hurtigbufferen
2. Sett (nøkkel=2, verdi=B) inn i hurtigbufferen
3. Sett (nøkkel=3, verdi=C) inn i hurtigbufferen
4. Hent (nøkkel=2) fra hurtigbufferen
5. Få (tast=4) fra hurtigbufferen
6. Sett (nøkkel=4, verdi=D) inn i hurtigbufferen
7. Sett (nøkkel=3, verdi=E) inn i hurtigbufferen
8. Få (tast=4) fra hurtigbufferen
9. Sett (nøkkel=1, verdi=A) inn i hurtigbufferen

Ovennevnte operasjoner utføres etter hverandre som vist på bildet nedenfor:

Detaljert forklaring av hver operasjon:

1. Sett (nøkkel 1, verdi A) : Siden LRU-cachen har tom kapasitet=3, er det ikke behov for noen erstatning, og vi setter {1 : A} øverst, dvs. {1 : A} har høyeste prioritet.
2. Sett (nøkkel 2, verdi B) : Siden LRU-hurtigbufferen har tom kapasitet=2, er det igjen ikke behov for noen erstatning, men nå har {2 : B} høyest prioritet og prioritet på {1 : A}-reduksjon.
3. Sett (nøkkel 3, verdi C) : Fortsatt er det 1 tom plass ledig i hurtigbufferen, legg derfor inn {3 : C} uten noen erstatning, legg merke til at hurtigbufferen er full og gjeldende prioritetsrekkefølge fra høyeste til laveste er {3:C}, {2:B }, {1:A}.
4. Hent (nøkkel 2) : Nå, returner verdien av key=2 under denne operasjonen, også siden key=2 brukes, er den nye prioritetsrekkefølgen nå {2:B}, {3:C}, {1:A}
5. Hent (nøkkel 4): Legg merke til at nøkkel 4 ikke er til stede i hurtigbufferen, vi returnerer '-1' for denne operasjonen.
6. Sett (nøkkel 4, verdi D) : Legg merke til at cachen er FULL, bruk nå LRU-algoritmen for å bestemme hvilken nøkkel som er minst nylig brukt. Siden {1:A} hadde minst prioritet, fjern {1:A} fra bufferen og legg {4:D} inn i bufferen. Legg merke til at den nye prioriterte rekkefølgen er {4:D}, {2:B}, {3:C}
7. Sett (nøkkel 3, verdi E) : Siden nøkkel=3 allerede var til stede i hurtigbufferen med verdi=C, vil denne operasjonen ikke resultere i fjerning av noen nøkkel, snarere vil den oppdatere verdien av nøkkel=3 til ' OG' . Nå vil den nye prioritetsrekkefølgen bli {3:E}, {4:D}, {2:B}
8. Hent (nøkkel 4) : Returner verdien til nøkkel=4. Nå vil ny prioritet bli {4:D}, {3:E}, {2:B}
9. Sett (nøkkel 1, verdi A) : Siden hurtigbufferen vår er FULL, så bruk LRU-algoritmen vår for å finne ut hvilken nøkkel som ble brukt minst nylig, og siden {2:B} hadde minst prioritet, fjern {2:B} fra hurtigbufferen og sett {1:A} inn i cache. Nå er den nye prioriterte rekkefølgen {1:A}, {4:D}, {3:E}

Måter å implementere LRU Cache:

LRU-cache kan implementeres på en rekke måter, og hver programmerer kan velge en annen tilnærming. Nedenfor er imidlertid vanlige tilnærminger:

1. LRU bruker Queue og Hashing
2. LRU bruker Dobbeltkoblet liste + hashing
3. LRU bruker Deque
4. LRU bruker Stack
5. LRU bruker Motimplementering
6. LRU bruker Lazy Updates

LRU-bufferimplementering ved bruk av kø og hashing:

Vi bruker to datastrukturer for å implementere en LRU Cache.

1. Kø implementeres ved hjelp av en dobbeltlenket liste. Maksimal størrelse på køen vil være lik det totale antallet tilgjengelige rammer (cache-størrelse). De sist brukte sidene vil være nær frontenden, og de minst nylig brukte sidene vil være nær bakenden.
2. En Hash med sidenummeret som nøkkel og adressen til den tilsvarende kønoden som verdi.

Når det refereres til en side, kan den nødvendige siden være i minnet. Hvis det er i minnet, må vi koble fra noden på listen og bringe den foran i køen.
Hvis den nødvendige siden ikke er i minnet, tar vi den med i minnet. Med enkle ord legger vi til en ny node foran i køen og oppdaterer den tilsvarende nodeadressen i hashen. Hvis køen er full, det vil si at alle rammene er fulle, fjerner vi en node fra baksiden av køen, og legger til den nye noden foran i køen.

Illustrasjon:

La oss vurdere operasjonene, Refererer nøkkel x med i LRU-cachen: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Merk: Til å begynne med er det ingen side i minnet.

Bildene nedenfor viser trinnvis utførelse av operasjonene ovenfor på LRU-cachen.

Algoritme:

• Lag en klasse LRUCache med erklære en liste av typen int, et uordnet kart av typen , og en variabel for å lagre maksimal størrelse på hurtigbufferen
• I referansefunksjonen til LRUCache
  • Hvis denne verdien ikke er til stede i køen, skyv denne verdien foran køen og fjern den siste verdien hvis køen er full
  • Hvis verdien allerede er til stede, fjern den fra køen og skyv den foran i køen
• I displayfunksjonen skrive ut, LRUCache ved hjelp av køen starter fra forsiden

Nedenfor er implementeringen av tilnærmingen ovenfor:

C++

>

>

C

android versjonshistorikk

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

LRU-cache-implementering ved hjelp av Doubly Linked List og Hashing :

Ideen er veldig grunnleggende, dvs. fortsett å sette inn elementene på hodet.

• hvis elementet ikke er til stede i listen, legg det til øverst på listen
• hvis elementet er til stede i listen, flytt elementet til hodet og flytt det gjenværende elementet i listen

Merk at nodens prioritet vil avhenge av avstanden til noden fra hodet, jo nærmest noden er hodet, jo høyere prioritet har den. Så når Cache-størrelsen er full og vi trenger å fjerne et element, fjerner vi elementet ved siden av halen på den dobbeltkoblede listen.

LRU cache-implementering ved hjelp av Deque & Hashmap:

Deque-datastrukturen tillater innsetting og sletting fra fronten så vel som slutten, denne egenskapen tillater implementering av LRU mulig da Front-elementet kan representere høyprioritetselement mens sluttelementet kan være lavprioritetselementet, dvs. Minst nylig brukt.

Arbeider:

1. Få operasjon : Sjekker om nøkkelen finnes i hurtigbufferens hash-kart og følg tilfellene nedenfor på deque:
   • Hvis nøkkelen blir funnet:
     • Varen anses som nylig brukt, så den flyttes til forsiden av dekket.
     • Verdien knyttet til nøkkelen returneres som et resultat avget>operasjon.
   • Hvis nøkkelen ikke blir funnet:
     • returner -1 for å indikere at ingen slik nøkkel er til stede.
2. Sett operasjon: Sjekk først om nøkkelen allerede eksisterer i cachens hash-kart og følg sakene nedenfor på dequen
   • Hvis nøkkelen finnes:
     • Verdien knyttet til nøkkelen oppdateres.
     • Gjenstanden flyttes til forsiden av dekket siden den nå er den sist brukte.
   • Hvis nøkkelen ikke finnes:
     • Hvis hurtigbufferen er full, betyr det at et nytt element må settes inn, og det minst nylig brukte elementet må kastes ut. Dette gjøres ved å fjerne elementet fra slutten av dequen og den tilsvarende oppføringen fra hash-kartet.
     • Det nye nøkkelverdi-paret settes deretter inn i både hash-kartet og forsiden av dequen for å indikere at det er det sist brukte elementet

LRU-bufferimplementering ved bruk av Stack & Hashmap:

Implementering av en LRU (Least Recently Used) cache ved å bruke en stabeldatastruktur og hashing kan være litt vanskelig fordi en enkel stabel ikke gir effektiv tilgang til det minst nylig brukte elementet. Du kan imidlertid kombinere en stabel med et hash-kart for å oppnå dette effektivt. Her er en tilnærming på høyt nivå for å implementere den:

1. Bruk et Hash-kart : Hash-kartet vil lagre nøkkelverdi-parene til hurtigbufferen. Nøklene vil kartlegges til de tilsvarende nodene i stabelen.
2. Bruk en stabel : Stabelen vil opprettholde rekkefølgen på nøkler basert på bruken. Det minst nylig brukte elementet vil være nederst i stabelen, og det sist brukte elementet vil være øverst

Denne tilnærmingen er ikke så effektiv og brukes derfor ikke ofte.

LRU-buffer ved bruk av Counter-implementering:

Hver blokk i cachen vil ha sin egen LRU-teller hvor verdien til telleren hører til {0 til n-1} , her ' n ' representerer størrelsen på cachen. Blokken som endres under utskifting av blokk blir MRU-blokken, og som et resultat endres dens tellerverdi til n – 1. Tellerverdiene som er større enn den åpnede blokkens tellerverdi, reduseres med én. De resterende blokkene er uendret.

LRU-bufferimplementering ved hjelp av Lazy Updates:

Implementering av en LRU (Least Recently Used) cache ved hjelp av late oppdateringer er en vanlig teknikk for å forbedre effektiviteten til cachens operasjoner. Late oppdateringer innebærer å spore rekkefølgen som elementer er tilgjengelig uten umiddelbart å oppdatere hele datastrukturen. Når en cache-miss oppstår, kan du bestemme om du vil utføre en full oppdatering basert på noen kriterier.

Kompleksitetsanalyse av LRU Cache:

• Tidskompleksitet:
  • Put()-operasjon: O(1) dvs. tiden som kreves for å sette inn eller oppdatere nytt nøkkelverdi-par er konstant
  • Get() operasjon: O(1) dvs. tiden som kreves for å få verdien til en nøkkel er konstant
• Hjelpeplass: O(N) hvor N er kapasiteten til hurtigbufferen.

Fordeler med LRU-cache:

• Rask tilgang : Det tar O(1) tid å få tilgang til dataene fra LRU-cachen.
• Rask oppdatering : Det tar O(1) tid å oppdatere et nøkkelverdi-par i LRU-cachen.
• Rask fjerning av minst nylig brukte data : Det tar O(1) å slette det som ikke har vært nylig brukt.
• Ingen tøffing: LRU er mindre utsatt for thrashing sammenlignet med FIFO fordi den tar hensyn til brukshistorikken til sider. Den kan oppdage hvilke sider som brukes ofte og prioritere dem for minneallokering, noe som reduserer antall sidefeil og disk I/O-operasjoner.

Ulemper med LRU-cache:

• Det krever stor hurtigbufferstørrelse for å øke effektiviteten.
• Det krever ytterligere datastruktur for å bli implementert.
• Maskinvarehjelpen er høy.
• I LRU er feildeteksjon vanskelig sammenlignet med andre algoritmer.
• Det har begrenset aksept.

Real-World-applikasjon av LRU Cache:

• I databasesystemer for raske søkeresultater.
• I operativsystemer for å minimere sidefeil.
• Tekstredigerere og IDE-er for å lagre ofte brukte filer eller kodebiter
• Nettverksrutere og -svitsjer bruker LRU for å øke effektiviteten til datanettverk
• I kompilatoroptimaliseringer
• Verktøy for tekstprediksjon og autofullføring