Lançado · em melhoria
Algorithm
Um cache LRU descarta a entrada usada há mais tempo quando enche; um mapa hash e uma lista duplamente encadeada deixam get e put em O(1).
Um cache LRU (least recently used, usado menos recentemente) é um cache de capacidade fixa que, quando fica cheio, remove a entrada que está há mais tempo sem uso. Ele se apoia na localidade temporal, isto é, no fato de que dados usados há pouco tendem a ser usados de novo em breve, e, diferente do FIFO, atualiza a posição da entrada a cada leitura. A implementação padrão combina um mapa hash, que encontra o nó de cada chave, com uma lista duplamente encadeada que guarda a ordem de uso, de modo que get e put levam O(1) em média.
O LRU aparece, exato ou aproximado, em quase todas as camadas de um sistema: caches de CPU, cache de páginas do sistema operacional, buffer pools de bancos de dados, políticas de remoção do Redis, CDNs e caches de navegador. As bibliotecas padrão também o oferecem, como functools.lru_cache e OrderedDict no Python ou LinkedHashMap no Java. Como junta mapa hash e lista encadeada em um único projeto, também é uma pergunta clássica em entrevistas de programação.
Comece pelas diferenças entre políticas de remoção como FIFO, LRU, LFU e TTL e pelo conceito de taxa de acerto, e depois acompanhe à mão uma sequência curta de requisições. Em seguida, implemente o cache você mesmo com um dicionário e uma lista duplamente encadeada com nós sentinela, e compare com versões de biblioteca como OrderedDict e LinkedHashMap. Por fim, resolva problemas práticos: segurança entre threads, invalidação de cache e combinação com tempo de expiração.
Cada get ou put bem-sucedido move a entrada para a ponta mais recente; quando falta espaço, a entrada da outra ponta é removida.
O mapa encontra direto o nó de uma chave, e a lista desliga e reinsere nós em O(1) para manter a ordem.
get e put alteram só um número constante de ponteiros, então levam tempo constante em média; o espaço cresce com a capacidade.
Sistemas reais costumam usar CLOCK, pseudo-LRU, LRU por amostragem, 2Q ou W-TinyLFU para reduzir custos ou resistir a varreduras grandes.
Um dict liga chaves a nós, e uma lista duplamente encadeada entre as sentinelas head e tail guarda a ordem de uso. get move o nó para a frente; put remove o nó logo antes de tail quando o cache está cheio. Ao rodar python lru_cache.py, "b" é removido e a saída é None 1 3.
lru_cache.py
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> Node
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key, default=None):
node = self.map.get(key)
if node is None:
return default
self._unlink(node) # touch: move to the front
self._push_front(node)
return node.value
def put(self, key, value):
if self.capacity <= 0:
return
node = self.map.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) >= self.capacity: # evict the least recently used
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the most recent
cache.put("c", 3) # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c")) # None 1 3
python lru_cache.pySeis capítulos que levam você da instalação aos conceitos essenciais de Cache LRU.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Cache LRU.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.