Punerea în aplicare a unei politici de înlocuire LRU cache ajută la optimizarea utilizării memoriei prin eliminarea articolelor cel mai puțin recent accesate atunci când cache-ul atinge capacitatea sa. Acest ghid oferă pași practici pentru a dezvolta un cache LRU în diferite medii de programare.

Înțelegerea LRU Cache

Un cache LRU (cel mai puțin recent utilizat) ține evidența utilizării articolelor pentru a determina ce date să evacueze atunci când spațiul este necesar. Acesta prioritizează articolele accesate recent, asigurându-se că datele utilizate frecvent rămân disponibile.

Componentele principale ale unei cache LRU

Un dispozitiv eficient de cache LRU combină de obicei două structuri de date:

  • Oferă acces rapid la obiectele de cache.
  • Lista dublu-legată: Menține ordinea de utilizare a elementului, cu cea mai recentă în față.

Etapele de implementare

Urmați aceste etape pentru a implementa un cache LRU:

  • Inițializează harta hash și lista dublu legate.
  • Pe accesul la date, mutați elementul în partea din față a listei.
  • Dacă cache-ul depășește capacitatea, eliminați elementul de la sfârșitul listei.
  • Actualizează harta hash în mod corespunzător în timpul inserțiilor și ștergerilor.

Punerea în aplicare a eșantionului în Python

Iată un exemplu simplu de cache LRU în Python:

Notă:[ Acest cod folosește modulul colecțiilor pentru Dictul comandat, care simplifică implementarea.

din colectii importa ComandatDict

Clasa LRUCache:

Def nit

auto.cache = Dict comandat ()

auto.capacitate = capacitate

Def obține (self, cheie):

dacă cheia nu este în autocache:

Return -1

Self.cache.move to end(key)

returnează-te.cache[cheie]

Def put (self, key, value):

self.cache[cheie] = valoare

Self.cache.move to end(key)

dacă len (self.cache) > autocapacitate:

Self.cache.popitem (ultima=False)