A implementação de uma política de substituição de cache LRU ajuda a otimizar o uso da memória removendo os itens menos acessados quando o cache atinge sua capacidade. Este guia fornece passos práticos para desenvolver um cache LRU em vários ambientes de programação.

Compreender a 'Cache' da LRU

Uma cache LRU (Lest Recently Used) mantém o controle do uso do item para determinar quais dados devem ser despejados quando o espaço é necessário. Ele prioriza itens acessados recentemente, garantindo que os dados frequentemente usados permaneçam disponíveis.

Componentes Principais de uma Cache LRU

Um cache LRU eficaz tipicamente combina duas estruturas de dados:

  • Hash Map: Fornece acesso rápido a itens de cache.
  • Lista duplamente ligada: Mantém a ordem de uso do item, com a mais recente na frente.

Etapas de Implementação

Siga estes passos para implementar um cache LRU:

  • Inicialize o mapa de hash e duplamente a lista vinculada.
  • No acesso aos dados, mova o item para a frente da lista.
  • Se a cache exceder a capacidade, remova o item no final da lista.
  • Atualizar o mapa de hash de acordo durante inserções e exclusões.

Implementação de Amostras em Python

Aqui está um exemplo simples de uma cache LRU em Python:

Nota: Este código usa o módulo de coleções para OrdenadoDict, que simplifica a implementação.

«```python

a partir de coleções importar OrdenedDict

classe LRUCache:

def init (auto, capacidade):

self.cache = OrderedDict()

auto.capacidade = capacidade

Def get(self, chave):

se a chave não estiver em autocache:

retorno - 1

self.cache.move to end( chave)

retornar self.cache[key]

def put(self, chave, valor):

self.cache[key] = valor

self.cache.move to end( chave)

se len(self.cache) > auto.capacidade:

self.cache.popitem(last=False)

«``