Wat is LRU-cache?

Algoritmen voor cachevervanging zijn efficiënt ontworpen om de cache te vervangen wanneer de ruimte vol is. De Minst recent gebruikt (LRU) is een van die algoritmen. Zoals de naam al doet vermoeden wanneer het cachegeheugen vol is, LRU kiest de gegevens die het minst recentelijk zijn gebruikt en verwijdert deze om ruimte te maken voor de nieuwe gegevens. De prioriteit van de gegevens in de cache verandert afhankelijk van de behoefte aan die gegevens, d.w.z. als bepaalde gegevens onlangs worden opgehaald of bijgewerkt, wordt de prioriteit van die gegevens gewijzigd en toegewezen aan de hoogste prioriteit, en neemt de prioriteit van de gegevens af als deze blijft ongebruikte bewerkingen na bewerkingen.

Inhoudsopgave

• Wat is LRU-cache?
• Bewerkingen op LRU-cache:
• Werking van LRU-cache:
• Manieren om LRU-cache te implementeren:
• LRU-cache-implementatie met behulp van wachtrij en hashing:
• LRU-cache-implementatie met behulp van dubbel gekoppelde lijst en hashing:
• LRU-cache-implementatie met Deque & Hashmap:
• LRU-cache-implementatie met behulp van Stack & Hashmap:
• LRU-cache met behulp van Counter Implementation:
• LRU-cache-implementatie met behulp van Lazy Updates:
• Complexiteitsanalyse van LRU-cache:
• Voordelen van LRU-cache:
• Nadelen van LRU-cache:
• Real-World toepassing van LRU-cache:

LRU algoritme is een standaardprobleem en kan afhankelijk van de behoefte variëren, bijvoorbeeld in besturingssystemen LRU speelt een cruciale rol omdat het kan worden gebruikt als algoritme voor paginavervanging om paginafouten te minimaliseren.

hoe Java te upgraden

Bewerkingen op LRU-cache:

• LRUCache (capaciteit c): Initialiseer LRU-cache met een positieve capaciteit C.
• krijgen (sleutel) : Retourneert de waarde van Sleutel ‘ k’ als het aanwezig is in de cache, retourneert het anders -1. Werkt ook de prioriteit van gegevens in de LRU-cache bij.
• zet (sleutel, waarde): Werk de waarde van de sleutel bij als die sleutel bestaat. Voeg anders het sleutel-waardepaar toe aan de cache. Als het aantal sleutels de capaciteit van de LRU-cache overschrijdt, verwijder dan de minst recent gebruikte sleutel.

Werking van LRU-cache:

Laten we aannemen dat we een LRU-cache met capaciteit 3 ​​hebben en dat we de volgende bewerkingen willen uitvoeren:

1. Plaats (sleutel=1, waarde=A) in de cache
2. Plaats (sleutel=2, waarde=B) in de cache
3. Plaats (sleutel=3, waarde=C) in de cache
4. Haal (sleutel=2) uit de cache
5. Haal (sleutel=4) uit de cache
6. Plaats (sleutel=4, waarde=D) in de cache
7. Plaats (sleutel=3, waarde=E) in de cache
8. Haal (sleutel=4) uit de cache
9. Plaats (sleutel=1, waarde=A) in de cache

De bovenstaande bewerkingen worden één voor één uitgevoerd, zoals weergegeven in de onderstaande afbeelding:

Gedetailleerde uitleg van elke bewerking:

1. Zet (sleutel 1, waarde A) : Omdat de LRU-cache een lege capaciteit = 3 heeft, is vervanging niet nodig en plaatsen we {1: A} bovenaan, d.w.z. {1: A} heeft de hoogste prioriteit.
2. Zet (sleutel 2, waarde B) : Omdat de LRU-cache een lege capaciteit = 2 heeft, is er opnieuw geen vervanging nodig, maar nu heeft de {2: B} de hoogste prioriteit en wordt de prioriteit van {1: A} verlaagd.
3. Zet (sleutel 3, waarde C) : Er is nog steeds 1 lege ruimte vrij in de cache, plaats daarom {3 : C} zonder enige vervanging. Merk op dat de cache nu vol is en de huidige prioriteitsvolgorde van hoog naar laag is {3:C}, {2:B }, {1:A}.
4. Verkrijg (sleutel 2) : Retourneer nu de waarde van key=2 tijdens deze bewerking, ook omdat key=2 wordt gebruikt, is de nieuwe prioriteitsvolgorde nu {2:B}, {3:C}, {1:A}
5. Verkrijg (sleutel 4): Merk op dat sleutel 4 niet aanwezig is in de cache, we retourneren ‘-1’ voor deze bewerking.
6. Zet (sleutel 4, waarde D) : Merk op dat de cache VOLLEDIG is. Gebruik nu het LRU-algoritme om te bepalen welke sleutel het minst recentelijk is gebruikt. Omdat {1:A} de minste prioriteit had, verwijdert u {1:A} uit onze cache en plaatst u {4:D} in de cache. Merk op dat de nieuwe prioriteitsvolgorde {4:D}, {2:B}, {3:C} is
7. Zet (sleutel 3, waarde E) : Omdat key=3 al aanwezig was in de cache met waarde=C, zal deze bewerking dus niet resulteren in het verwijderen van een sleutel, maar zal de waarde van key=3 worden bijgewerkt naar ‘ EN' . De nieuwe prioriteitsvolgorde wordt nu {3:E}, {4:D}, {2:B}
8. Verkrijg (sleutel 4) : Retourneert de waarde van key=4. De nieuwe prioriteit wordt nu {4:D}, {3:E}, {2:B}
9. Zet (sleutel 1, waarde A) : Omdat onze cache VOL is, gebruikt u ons LRU-algoritme om te bepalen welke sleutel het minst recentelijk is gebruikt, en aangezien {2:B} de minste prioriteit had, verwijdert u {2:B} uit onze cache en plaatst u {1:A} in de cache. De nieuwe prioriteitsvolgorde is nu {1:A}, {4:D}, {3:E}

Manieren om LRU-cache te implementeren:

LRU-cache kan op verschillende manieren worden geïmplementeerd, en elke programmeur kan een andere aanpak kiezen. Hieronder vindt u echter veelgebruikte benaderingen:

1. LRU met behulp van wachtrij en hashing
2. LRU gebruikt Dubbel gekoppelde lijst + hashing
3. LRU met behulp van Deque
4. LRU met behulp van Stack
5. LRU gebruikt Tegenimplementatie
6. LRU gebruikt Lazy Updates

LRU-cache-implementatie met behulp van wachtrij en hashing:

We gebruiken twee datastructuren om een ​​LRU-cache te implementeren.

1. Wachtrij wordt geïmplementeerd met behulp van een dubbelgekoppelde lijst. De maximale grootte van de wachtrij is gelijk aan het totale aantal beschikbare frames (cachegrootte). De meest recent gebruikte pagina's bevinden zich aan de voorkant en de minst recent gebruikte pagina's aan de achterkant.
2. Een hasj met het paginanummer als sleutel en het adres van het corresponderende wachtrijknooppunt als waarde.

Wanneer naar een pagina wordt verwezen, bevindt de gewenste pagina zich mogelijk in het geheugen. Als het zich in het geheugen bevindt, moeten we het knooppunt van de lijst loskoppelen en naar de voorkant van de wachtrij brengen.
Als de gewenste pagina niet in het geheugen aanwezig is, brengen wij die in het geheugen. In eenvoudige woorden: we voegen een nieuw knooppunt toe aan de voorkant van de wachtrij en werken het overeenkomstige knooppuntadres in de hash bij. Als de wachtrij vol is, dat wil zeggen dat alle frames vol zijn, verwijderen we een knooppunt aan de achterkant van de wachtrij en voegen we het nieuwe knooppunt aan de voorkant van de wachtrij toe.

Illustratie:

Laten we eens kijken naar de operaties, Verwijst sleutel X met in de LRU-cache: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Opmerking: Aanvankelijk bevindt er zich geen pagina in het geheugen.

Onderstaande afbeeldingen tonen de stapsgewijze uitvoering van de bovenstaande bewerkingen op de LRU-cache.

Algoritme:

• Creëer een klasse LRUCache met een lijst van het type int, een ongeordende kaart van het type en een variabele om de maximale grootte van de cache op te slaan
• In de verwijzingsfunctie van LRUCache
  • Als deze waarde niet aanwezig is in de wachtrij, duwt u deze waarde voor de wachtrij en verwijdert u de laatste waarde als de wachtrij vol is
  • Als de waarde al aanwezig is, verwijdert u deze uit de wachtrij en plaatst u deze vooraan in de wachtrij
• In de weergavefunctie print gebruikt de LRUCache de wachtrij vanaf de voorkant

Hieronder vindt u de implementatie van de bovenstaande aanpak:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

LRU-cache-implementatie met behulp van dubbel gekoppelde lijst en hashing :

Het idee is heel eenvoudig, d.w.z. blijf de elementen aan de kop invoegen.

• als het element niet aanwezig is in de lijst, voeg het dan toe aan de kop van de lijst
• als het element aanwezig is in de lijst, verplaats het element dan naar de kop en verplaats het resterende element van de lijst

Merk op dat de prioriteit van het knooppunt zal afhangen van de afstand van dat knooppunt tot het hoofd: hoe dichter het knooppunt zich bij het hoofd bevindt, hoe hoger de prioriteit die het heeft. Dus wanneer de cachegrootte vol is en we een element moeten verwijderen, verwijderen we het element dat grenst aan de staart van de dubbel gekoppelde lijst.

LRU-cache-implementatie met Deque & Hashmap:

Deque-datastructuur maakt invoeging en verwijdering van zowel de voorkant als het einde mogelijk. Deze eigenschap maakt de implementatie van LRU mogelijk omdat het Front-element een element met een hoge prioriteit kan vertegenwoordigen, terwijl het eindelement het element met een lage prioriteit kan zijn, dat wil zeggen het minst recent gebruikt.

Werkend:

1. Operatie ophalen : Controleert of de sleutel bestaat in de hashkaart van de cache en volgt de onderstaande gevallen op de deque:
   • Als de sleutel wordt gevonden:
     • Het item wordt beschouwd als recent gebruikt en wordt daarom naar de voorkant van de deque verplaatst.
     • De waarde die aan de sleutel is gekoppeld, wordt geretourneerd als resultaat van deget>operatie.
   • Als de sleutel niet wordt gevonden:
     • return -1 om aan te geven dat een dergelijke sleutel niet aanwezig is.
2. Zet bediening: Controleer eerst of de sleutel al bestaat in de hashkaart van de cache en volg de onderstaande gevallen op de deque
   • Als de sleutel bestaat:
     • De waarde die aan de sleutel is gekoppeld, wordt bijgewerkt.
     • Het item is naar de voorkant van de deque verplaatst, omdat het nu het meest recentelijk is gebruikt.
   • Als de sleutel niet bestaat:
     • Als de cache vol is, betekent dit dat er een nieuw item moet worden ingevoegd en dat het minst recentelijk gebruikte item moet worden verwijderd. Dit wordt gedaan door het item aan het einde van de deque en de bijbehorende vermelding van de hashkaart te verwijderen.
     • Het nieuwe sleutel-waarde-paar wordt vervolgens ingevoegd in zowel de hash-kaart als de voorkant van de deque om aan te geven dat dit het meest recent gebruikte item is

LRU-cache-implementatie met behulp van Stack & Hashmap:

Het implementeren van een LRU-cache (Least Recent Used) met behulp van een stapelgegevensstructuur en hashen kan een beetje lastig zijn, omdat een eenvoudige stapel geen efficiënte toegang biedt tot het minst recent gebruikte item. Om dit efficiënt te bereiken, kunt u een stapel echter combineren met een hashkaart. Hier is een aanpak op hoog niveau om het te implementeren:

1. Gebruik een hashkaart : De hash-kaart slaat de sleutel-waardeparen van de cache op. De sleutels worden toegewezen aan de overeenkomstige knooppunten in de stapel.
2. Gebruik een stapel : De stapel handhaaft de volgorde van de sleutels op basis van hun gebruik. Het minst recent gebruikte item staat onderaan de stapel en het meest recent gebruikte item bovenaan

Deze aanpak is niet zo efficiënt en wordt daarom niet vaak gebruikt.

LRU-cache met behulp van Counter Implementation:

Elk blok in de cache heeft zijn eigen LRU-teller waartoe de waarde van de teller behoort {0 tot n-1} , hier ' N ‘ vertegenwoordigt de grootte van de cache. Het blok dat tijdens blokvervanging wordt gewijzigd, wordt het MRU-blok en als gevolg daarvan wordt de tellerwaarde ervan gewijzigd in n – 1. De tellerwaarden die groter zijn dan de tellerwaarde van het benaderde blok worden met één verlaagd. De overige blokken zijn ongewijzigd.

LRU-cache-implementatie met behulp van Lazy Updates:

Het implementeren van een LRU-cache (Least Recent Used) met behulp van luie updates is een veelgebruikte techniek om de efficiëntie van de cachebewerkingen te verbeteren. Bij luie updates wordt de volgorde gevolgd waarin items worden geopend, zonder onmiddellijk de volledige gegevensstructuur bij te werken. Wanneer er een cachemisser optreedt, kunt u op basis van enkele criteria beslissen of u wel of niet een volledige update wilt uitvoeren.

Complexiteitsanalyse van LRU-cache:

• Tijdcomplexiteit:
  • Put()-bewerking: O(1), d.w.z. de tijd die nodig is om een ​​nieuw sleutel-waardepaar in te voegen of bij te werken, is constant
  • Get()-bewerking: O(1), d.w.z. de tijd die nodig is om de waarde van een sleutel te verkrijgen, is constant
• Hulpruimte: O(N) waarbij N de capaciteit van de cache is.

Voordelen van LRU-cache:

• Snelle toegang : Het kost O(1) tijd om toegang te krijgen tot de gegevens uit de LRU-cache.
• Snelle update : Het kost O(1) tijd om een ​​sleutel-waardepaar in de LRU-cache bij te werken.
• Snelle verwijdering van de minst recent gebruikte gegevens : Er is O(1) nodig om datgene te verwijderen wat niet recentelijk is gebruikt.
• Geen geselen: LRU is minder gevoelig voor pak slaag vergeleken met FIFO, omdat het rekening houdt met de gebruiksgeschiedenis van pagina's. Het kan detecteren welke pagina's vaak worden gebruikt en deze prioriteren voor geheugentoewijzing, waardoor het aantal paginafouten en schijf-I/O-bewerkingen wordt verminderd.

Nadelen van LRU-cache:

• Het vereist een grote cachegrootte om de efficiëntie te vergroten.
• Er moet een aanvullende gegevensstructuur worden geïmplementeerd.
• Hardwareondersteuning is hoog.
• Bij LRU is foutdetectie moeilijk in vergelijking met andere algoritmen.
• Het heeft een beperkte aanvaardbaarheid.

Real-World toepassing van LRU-cache:

• In databasesystemen voor snelle queryresultaten.
• In besturingssystemen om paginafouten te minimaliseren.
• Teksteditors en IDE's om veelgebruikte bestanden of codefragmenten op te slaan
• Netwerkrouters en -switches gebruiken LRU om de efficiëntie van een computernetwerk te vergroten
• Bij compileroptimalisaties
• Hulpmiddelen voor tekstvoorspelling en automatisch aanvullen