Implementere en LRU-bufferutskiftingspolicy hjelper optimalisere minnebruken ved å fjerne de minst nylig tilgjengelige elementene når cache når sin kapasitet. Denne guiden gir praktiske skritt for å utvikle en LRU-buffer i ulike programmeringsmiljøer.

Forstå LRU Cache

En LRU-buffer (minst nylig brukt) holder oversikt over bruken av elementene for å bestemme hvilke data som skal avvikles når det trengs plass. Den prioriterer nylig tilgjengelige elementer, og sikrer at ofte brukte data forblir tilgjengelige.

Kjernekomponenter i en LRU-cache

En effektiv LRU cache kombinerer vanligvis to datastrukturer:

  • Hash Map: gir rask tilgang til cache-elementer.
  • Doubly Linked List: opprettholder rekkefølgen av bruk av element, med den siste foran.

Implementasjonstrinn

Følg disse trinnene for å implementere en LRU-buffer:

  • Initier hash-kartet og doubly-lenkelisten.
  • Når du har tilgang til data, kan du flytte elementet til fremsiden av listen.
  • Hvis cacheen overstiger kapasiteten, fjerner du elementet på slutten av listen.
  • Oppdater hash-kartet i henhold til dette under innsettinger og slettinger.

Prøve Implementasjon i Python

Her er et enkelt eksempel på en LRU-buffer i Python:

Note: Denne koden bruker samlingsmodulen for OrderedDict, som forenkler implementeringen.

«`python

fra samlinger import Bestillet

klasse LRUCache:

def init (selv, kapasitet):

self.cache = BestilledDict()

selv.kapasitet = kapasitet

Def get(selv, nøkkel):

hvis nøkkelen ikke er i self.cache:

retur -1

self.cache.move to end(nøkkel)

Tilbake self.cache[nøkkel]

def sett( seg selv, nøkkel, verdi):

self.cache[nøkkel] = verdi

self.cache.move to end(nøkkel)

hvis len( self.cache) > self.ability:

self.cache.popitem(last=False)

«««