Kas yra LRU talpykla?

Talpyklos keitimo algoritmai yra efektyviai sukurti taip, kad pakeistų talpyklą, kai vieta pilna. The Neseniai naudotas (LRU) yra vienas iš tų algoritmų. Kaip rodo pavadinimas, kai talpyklos atmintis yra pilna, LRU parenka duomenis, kurie buvo neseniai naudojami, ir pašalina juos, kad būtų vietos naujiems duomenims. Duomenų prioritetas talpykloje keičiasi atsižvelgiant į tų duomenų poreikį, t. y. jei kai kurie duomenys būtų paimti arba atnaujinti neseniai, tų duomenų prioritetas būtų pakeistas ir priskiriamas aukščiausiam prioritetui, o duomenų prioritetas mažėja, jei lieka nepanaudotos operacijos po operacijų.

Turinys

• Kas yra LRU talpykla?
• Operacijos LRU talpykloje:
• LRU talpyklos veikimas:
• LRU talpyklos diegimo būdai:
• LRU talpyklos diegimas naudojant eilę ir maišą:
• LRU talpyklos diegimas naudojant dvigubai susietą sąrašą ir maišą:
• LRU talpyklos diegimas naudojant Deque & Hashmap:
• LRU talpyklos diegimas naudojant Stack & Hashmap:
• LRU talpykla naudojant Counter Implementation:
• LRU talpyklos diegimas naudojant „Lazy Updates“:
• LRU talpyklos sudėtingumo analizė:
• LRU talpyklos privalumai:
• LRU talpyklos trūkumai:
• Realus LRU talpyklos taikymas:

LRU algoritmas yra standartinė problema ir jis gali keistis pagal poreikį, pavyzdžiui, operacinėse sistemose LRU vaidina lemiamą vaidmenį, nes gali būti naudojamas kaip puslapio pakeitimo algoritmas, siekiant sumažinti puslapio gedimus.

Operacijos LRU talpykloje:

• LRUCache (c talpa): Inicijuoti LRU talpyklą su teigiamo dydžio talpa c.
• gauti (raktą) : grąžina rakto reikšmę k' jei jis yra talpykloje, kitu atveju jis grąžina -1. Taip pat atnaujinamas LRU talpykloje esančių duomenų prioritetas.
• įdėti (raktas, vertė): Atnaujinkite rakto reikšmę, jei toks raktas yra, Kitu atveju pridėkite rakto ir vertės porą prie talpyklos. Jei raktų skaičius viršijo LRU talpyklos talpą, atmeskite neseniai naudotą raktą.

LRU talpyklos veikimas:

Tarkime, kad turime 3 talpos LRU talpyklą ir norėtume atlikti šias operacijas:

1. Įdėkite (key=1, value=A) į talpyklą
2. Įdėkite (raktas = 2, vertė = B) į talpyklą
3. Įdėkite (key=3, value=C) į talpyklą
4. Gaukite (key=2) iš talpyklos
5. Gaukite (key=4) iš talpyklos
6. Įdėkite (key=4, value=D) į talpyklą
7. Įdėkite (key=3, value=E) į talpyklą
8. Gaukite (key=4) iš talpyklos
9. Įdėkite (key=1, value=A) į talpyklą

Aukščiau nurodytos operacijos atliekamos viena po kitos, kaip parodyta paveikslėlyje žemiau:

Išsamus kiekvienos operacijos paaiškinimas:

1. Įdėti (1 raktas, vertė A) : Kadangi LRU talpyklos talpa yra tuščia = 3, nereikia keisti ir mes įdedame {1 : A} viršuje, t. y. {1 : A} turi aukščiausią prioritetą.
2. Įdėkite (2 raktas, B vertė) : Kadangi LRU talpyklos talpa tuščia = 2, vėl nereikia keisti, bet dabar {2 : B} turi aukščiausią prioritetą, o prioritetas {1 : A} sumažėja.
3. Įdėti (3 raktas, vertė C) : Vis dar yra 1 laisva vieta talpykloje, todėl įdėkite {3 : C} be jokių pakeitimų, pastebėkite, kad dabar talpykla pilna ir dabartinė prioritetų tvarka nuo aukščiausio iki mažiausio yra {3:C}, {2:B }, {1:A}.
4. Gaukite (2 raktas) : Dabar šios operacijos metu grąžinkite rakto = 2 reikšmę, taip pat kadangi naudojamas raktas = 2, dabar nauja prioritetų tvarka yra {2:B}, {3:C}, {1:A}
5. Gaukite (4 raktas): Stebėkite, kad 4 klavišo talpykloje nėra, šiai operacijai grąžiname „-1“.
6. Įdėti (4 raktas, reikšmė D) : Stebėkite, ar talpykla pilna, dabar naudokite LRU algoritmą, kad nustatytumėte, kuris raktas buvo naudojamas mažiausiai neseniai. Kadangi {1:A} turėjo mažiausią prioritetą, pašalinkite {1:A} iš talpyklos ir įdėkite {4:D} į talpyklą. Atkreipkite dėmesį, kad nauja prioriteto tvarka yra {4:D}, {2:B}, {3:C}
7. Įdėti (3 raktas, vertė E) : Kadangi key=3 jau buvo talpykloje su value=C, todėl ši operacija nepašalins jokio rakto, o atnaujins key=3 reikšmę į „ IR' . Dabar nauja prioriteto tvarka taps {3:E}, {4:D}, {2:B}
8. Gaukite (4 klavišas) : grąžina rakto reikšmę = 4. Dabar naujas prioritetas taps {4:D}, {3:E}, {2:B}
9. Įdėti (1 raktas, vertė A) : Kadangi mūsų talpykla PILNA, todėl naudokite mūsų LRU algoritmą, kad nustatytumėte, kuris raktas buvo naudojamas mažiausiai neseniai, o kadangi {2:B} turėjo mažiausią prioritetą, pašalinkite {2:B} iš talpyklos ir įdėkite {1:A} į talpykla. Dabar nauja prioriteto tvarka yra {1:A}, {4:D}, {3:E}

LRU talpyklos diegimo būdai:

LRU talpykla gali būti įdiegta įvairiais būdais, ir kiekvienas programuotojas gali pasirinkti skirtingą metodą. Tačiau toliau pateikiami dažniausiai naudojami metodai:

1. LRU naudojant eilę ir maišą
2. LRU naudojant Dvigubai susietas sąrašas + maiša
3. LRU naudojant Deque
4. LRU naudojant Stack
5. LRU naudojant Skaitiklio įgyvendinimas
6. LRU naudojant Lazy Updates

LRU talpyklos diegimas naudojant eilę ir maišą:

Mes naudojame dvi duomenų struktūras, kad įdiegtume LRU talpyklą.

1. Eilė yra įgyvendinamas naudojant dvigubai susietą sąrašą. Didžiausias eilės dydis bus lygus bendram galimų kadrų skaičiui (talpyklos dydžiui). Paskutiniai naudoti puslapiai bus šalia priekinės dalies, o rečiausiai naudoti puslapiai bus netoli galinės dalies.
2. A Hašas su puslapio numeriu kaip raktu ir atitinkamo eilės mazgo adresu kaip reikšmė.

Kai pateikiama nuoroda į puslapį, reikiamas puslapis gali būti atmintyje. Jei jis yra atmintyje, turime atskirti sąrašo mazgą ir perkelti jį į eilės priekį.
Jei reikiamo puslapio atmintyje nėra, įnešame jį į atmintį. Paprastais žodžiais tariant, eilės priekyje pridedame naują mazgą ir atnaujiname atitinkamo mazgo adresą maišoje. Jei eilė pilna, t.y. visi kadrai pilni, pašaliname mazgą iš eilės galo, o naują mazgą įtraukiame į eilės priekį.

Iliustracija:

Apsvarstykime operacijas, Nurodo Raktas x su LRU talpykloje: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Pastaba: Iš pradžių atmintyje nėra puslapio.

Toliau pateiktuose vaizduose žingsnis po žingsnio parodytas aukščiau nurodytų operacijų vykdymas LRU talpykloje.

Algoritmas:

• Sukurkite klasę LRUCache su deklaruodami int tipo sąrašą, netvarkingą tipo žemėlapį , ir kintamasis, skirtas saugoti maksimalų talpyklos dydį
• LRUCache nuoroda funkcijoje
  • Jei šios reikšmės eilėje nėra, stumkite šią reikšmę prieš eilę ir pašalinkite paskutinę reikšmę, jei eilė pilna
  • Jei reikšmė jau yra, pašalinkite ją iš eilės ir įstumkite į eilės priekį
• Ekrano funkcijoje spausdinama LRUCache naudojant eilę pradedant nuo priekio

Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:

C++

Linux paleisti cmd

>

>

C

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

LRU talpyklos diegimas naudojant dvigubai susietą sąrašą ir maišą :

Idėja yra labai paprasta, t. y. toliau įterpkite elementus prie galvos.

• jei elemento sąraše nėra, pridėkite jį prie sąrašo pradžios
• jei elementas yra sąraše, perkelkite elementą į antraštę ir perkelkite likusį sąrašo elementą

Atkreipkite dėmesį, kad mazgo prioritetas priklausys nuo to mazgo atstumo nuo galvos, kuo mazgas arčiausiai galvos, tuo aukštesnis jo prioritetas. Taigi, kai talpyklos dydis yra pilnas ir mums reikia pašalinti kurį nors elementą, pašaliname elementą, esantį šalia dvigubai susieto sąrašo uodegos.

LRU talpyklos diegimas naudojant Deque & Hashmap:

Deque duomenų struktūra leidžia įterpti ir ištrinti iš priekio ir galo, ši savybė leidžia įgyvendinti LRU, nes priekinis elementas gali būti aukšto prioriteto elementas, o galutinis elementas gali būti žemo prioriteto elementas, t. y. Neseniai naudotas.

Dirba:

1. Gaukite operaciją : patikrina, ar raktas yra talpyklos maišos žemėlapyje, ir laikykitės toliau pateiktų atvejai:
   • Jei raktas rastas:
     • Daiktas laikomas neseniai naudotu, todėl jis perkeliamas į deko priekį.
     • Su raktu susijusi reikšmė grąžinama kaip rezultatasget>operacija.
   • Jei raktas nerastas:
     • grąžinkite -1, nurodydami, kad tokio rakto nėra.
2. Įdėjimo operacija: Pirmiausia patikrinkite, ar raktas jau yra talpyklos maišos žemėlapyje, ir vadovaukitės toliau pateiktais atvejais
   • Jei raktas yra:
     • Su raktu susijusi vertė atnaujinama.
     • Elementas perkeltas į deko priekinę dalį, nes dabar jis naudotas vėliausiai.
   • Jei rakto nėra:
     • Jei talpykla pilna, tai reiškia, kad reikia įdėti naują elementą, o rečiausiai naudotą prekę – iškeldinti. Tai atliekama pašalinant elementą iš dektos pabaigos ir atitinkamą įrašą iš maišos žemėlapio.
     • Tada naujoji rakto-reikšmių pora įterpiama ir į maišos žemėlapį, ir į deque priekinę dalį, kad būtų pažymėta, kad tai vėliausiai naudotas elementas

LRU talpyklos diegimas naudojant Stack & Hashmap:

LRU (mažiausiai naudotos) talpyklos įdiegimas naudojant dėklo duomenų struktūrą ir maišą gali būti šiek tiek sudėtingas, nes paprastas dėklas nesuteikia veiksmingos prieigos prie mažiausiai neseniai naudoto elemento. Tačiau galite derinti krūvą su maišos žemėlapiu, kad tai pasiektumėte efektyviai. Štai aukšto lygio metodas, kaip jį įgyvendinti:

1. Naudokite maišos žemėlapį : maišos žemėlapyje bus saugomos talpyklos raktų ir reikšmių poros. Raktai bus susieti su atitinkamais krūvos mazgais.
2. Naudokite krūvą : dėklas išlaikys raktų tvarką pagal jų naudojimą. Neseniai naudotas daiktas bus krūvos apačioje, o paskutinis naudotas – viršuje

Šis metodas nėra toks efektyvus, todėl nenaudojamas dažnai.

konvertuoti eilutę į sveikąjį skaičių Java

LRU talpykla naudojant Counter Implementation:

Kiekvienas talpyklos blokas turės savo LRU skaitiklį, kuriam priklauso skaitiklio reikšmė nuo 0 iki n-1} , čia n “ reiškia talpyklos dydį. Blokas, kuris keičiamas bloko keitimo metu, tampa MRU bloku, todėl jo skaitiklio reikšmė pakeičiama į n – 1. Skaitiklio reikšmės, didesnės už gauto bloko skaitiklio reikšmę, sumažinamos vienu. Likę blokai nepakeisti.

LRU talpyklos diegimas naudojant „Lazy Updates“:

LRU (mažiausiai naudotos) talpyklos įdiegimas naudojant tingius naujinimus yra įprastas būdas pagerinti talpyklos operacijų efektyvumą. Tingi atnaujinimai apima sekimo tvarką, kuria pasiekiami elementai, nedelsiant neatnaujinant visos duomenų struktūros. Kai įvyksta talpyklos praleidimas, pagal tam tikrus kriterijus galite nuspręsti, ar atlikti visą atnaujinimą, ar ne.

LRU talpyklos sudėtingumo analizė:

• Laiko sudėtingumas:
  • „Put()“ operacija: O(1), ty laikas, reikalingas naujai rakto-reikšmių porai įterpti arba atnaujinti, yra pastovus
  • Get() operacija: O(1), ty laikas, reikalingas rakto vertei gauti, yra pastovus
• Pagalbinė erdvė: O(N) kur N yra talpyklos talpa.

LRU talpyklos privalumai:

• Greita prieiga : Norint pasiekti duomenis iš LRU talpyklos, reikia O(1) laiko.
• Greitas atnaujinimas : Atnaujinti rakto-reikšmių porą LRU talpykloje užtrunka O(1) laiko.
• Greitas mažiausiai naudotų duomenų pašalinimas : Reikia O(1) ištrinti tai, kas neseniai nebuvo naudojama.
• Jokio daužymo: LRU yra mažiau jautrus daužymui, palyginti su FIFO, nes atsižvelgia į puslapių naudojimo istoriją. Jis gali aptikti, kurie puslapiai yra dažnai naudojami, ir suteikti jiems pirmenybę atminties paskirstymui, taip sumažinant puslapių klaidų skaičių ir disko įvesties/išvesties operacijas.

LRU talpyklos trūkumai:

• Norint padidinti efektyvumą, reikia didelio talpyklos dydžio.
• Tam reikia įdiegti papildomą duomenų struktūrą.
• Aparatinės įrangos pagalba yra didelė.
• LRU klaidų aptikimas yra sudėtingas, palyginti su kitais algoritmais.
• Jis turi ribotą priimtinumą.

Realus LRU talpyklos taikymas:

• Duomenų bazių sistemose, kad gautumėte greitus užklausų rezultatus.
• Operacinėse sistemose, kad sumažintumėte puslapio klaidas.
• Teksto redaktoriai ir IDE, skirti saugoti dažnai naudojamus failus ar kodo fragmentus
• Tinklo maršrutizatoriai ir komutatoriai naudoja LRU, kad padidintų kompiuterių tinklo efektyvumą
• Kompiliatoriaus optimizavime
• Teksto numatymo ir automatinio užbaigimo įrankiai