Een LRU cache-vervangingsbeleid implementeren helpt het geheugengebruik te optimaliseren door de minst recent geopende items te verwijderen wanneer de cache zijn capaciteit bereikt. Deze gids biedt praktische stappen om een LRU-cache te ontwikkelen in verschillende programmeeromgevingen.

Begrijpen LRU-cache

Een LRU (Last Recent Used) cache houdt het gebruik van items bij om te bepalen welke gegevens moeten worden verwijderd wanneer ruimte nodig is. Het geeft prioriteit aan recent geopende items, zodat veelgebruikte gegevens beschikbaar blijven.

Kerncomponenten van een LRU-cache

Een effectieve LRU-cache combineert meestal twee datastructuren:

  • Hash Map: Biedt snelle toegang tot cache items.
  • Dubbele Linked List: Behoudt de volgorde van het gebruik van het item, met de meest recente aan de voorzijde.

Uitvoering

Volg deze stappen om een LRU-cache te implementeren:

  • Initialiseer de hash-kaart en dubbel gekoppelde lijst.
  • Bij toegang tot gegevens, verplaats het item naar de voorkant van de lijst.
  • Als de cache de capaciteit overschrijdt, verwijder dan het item aan het einde van de lijst.
  • Update de hash-kaart dienovereenkomstig tijdens invoegen en verwijderen.

Voorbeeldimplementatie in Python

Hier is een eenvoudig voorbeeld van een LRU cache in Python:

Opmerking: Deze code gebruikt de collectiesmodule voor GeordendDicht, die de implementatie vereenvoudigt.

uit collecties import Bestelde schijf

klasse LRUcache:

def init (zelf, capaciteit):

self.cache = GeordendDoct()

zelf.capaciteit = capaciteit

def get(zelf, sleutel):

als de sleutel niet in self.cache staat:

terug -1

self.cache.move to end(key)

zelf.cache[sleutel] teruggeven

def putself, key, value):

self.cache[key] = waarde

self.cache.move to end(key)

als len(zelf.cache) > zelf.capaciteit:

self.cache.popitem(last=False)