LRU Cache

Q: Você consegue criar um cache LRU com um dicionário ordenado?

Sim. Um mapa que mantém a ordem de inserção, como o OrderedDict do Python ou o LinkedHashMap do Java, pode substituir a lista: mova uma chave para o final a cada uso e remova a do início, ainda em O(1). Em entrevistas, geralmente esperam que você implemente a lista manualmente.

MédioHashing Lista ligada

+10

Crie um cache que armazene no máximo capacity chaves. get key retorna o valor da chave ou -1 se ela não estiver no cache. put key value armazena o valor, substituindo qualquer valor anterior; se a chave for nova e o cache estiver cheio, primeiro remove a chave menos recentemente usada. Um get que encontra sua chave e cada put contam como um uso.

A operação i é ops[i] ("get" ou "put") na chave keys[i], com o valor values[i] (0 para um get). Execute-as em ordem em um cache vazio e retorne uma string para cada uma: "null" para um put, o valor ou "-1" para um get.

Função

lruCacheOps(capacity: integer, ops: string-array, keys: integer-array, values: integer-array) → string-array

capacityinteger: o número máximo de chaves que o cache pode armazenar ao mesmo tempo
opsstring-array: as operações, na ordem em que são executadas
keysinteger-array: a chave na qual cada operação atua
valuesinteger-array: o valor para cada put, 0 para cada get
Retornastring-array: uma resposta por operação, como texto

Restrições

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Cada ops[i] é get ou put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ para uma operação de put, e values[i] == 0 para uma operação de get.

Exemplos

Entrada: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Saída: ["null", "null", "10", "null", "-1", "30"]
Explicação: O get torna a chave 1 a mais recentemente usada, então put 3 remove a chave 2: get 2 retorna "-1" e get 3 retorna "30".

Entrada: capacity = 2ops = ["put", "put", "put", "put", "get", "get", "get"]keys = [5, 6, 5, 7, 5, 6, 7]values = [1, 2, 3, 4, 0, 0, 0]
Saída: ["null", "null", "null", "null", "3", "-1", "4"]
Explicação: A terceira operação de inserção atualiza a chave 5, que já está em cache: nada é removido, e a chave 5 se torna a mais recentemente usada. Portanto, put 7 remove a chave 6, não a chave 5.

Entrada: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Saída: ["-1", "null", "0", "null", "-1", "8"]
Explicação: Com espaço para uma chave, cada nova chave expulsa a anterior. O primeiro get não encontra nada em um cache vazio; a chave 0 então mantém o valor real 0 até que put 8 a expulse.

Para ir além

Como você alteraria o cache para remover a chave menos frequentemente usada em vez disso, desempatar pela menos recentemente usada e ainda manter as operações em O(1)?

Solução

Uma busca precisa encontrar uma chave rapidamente, e uma remoção por substituição precisa encontrar rapidamente a chave menos usada recentemente. Um mapa de hash faz a primeira coisa; uma lista mantida na ordem de uso faz a segunda. Use ambos: mapeie cada chave para seu nó em uma lista duplamente ligada, ordenada por uso.

Examine uma tabela de entradas com os horários do último uso

Intuição

Armazene até capacity entradas em arrays: chave, valor e uma marca de último uso de um contador que aumenta a cada operação. Uma nova chave em um cache cheio sobrescreve a entrada com a menor marca, a chave que ficou sem uso por mais tempo. No primeiro exemplo, em put 3, a chave 1 tem marca 3 e a chave 2 tem marca 2, então a chave 2 sai.

Cada operação percorre até capacity entradas: O(n × capacity) para n operações, milhões de comparações com 3.000 operações em um cache de 1.500 chaves.

Algoritmo

Mantenha os arrays keys, values e used, um contador de preenchimento e um relógio em 0.
Cada operação adiciona 1 ao relógio e percorre as entradas preenchidas procurando sua chave.
get: se não encontrar, retorne -1; se encontrar, defina used como o relógio e retorne o valor.
put: se encontrar, armazene o valor e o relógio. Se não encontrar, grave a chave, o valor e o relógio em uma entrada livre ou na entrada com o menor valor de used.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        # Entry i holds keys[i] -> values[i] and was last used at time used[i].
        self.keys = [0] * capacity
        self.values = [0] * capacity
        self.used = [0] * capacity
        self.size = 0
        self.time = 0

    def _find(self, key):
        for i in range(self.size):
            if self.keys[i] == key:
                return i
        return -1

    def get(self, key):
        self.time += 1
        i = self._find(key)
        if i == -1:
            return -1
        self.used[i] = self.time
        return self.values[i]

    def put(self, key, value):
        self.time += 1
        i = self._find(key)
        if i == -1:
            if self.size < self.capacity:
                i = self.size
                self.size += 1
            else:
                # Full: scan for the entry used longest ago and take its place.
                i = 0
                for j in range(1, self.capacity):
                    if self.used[j] < self.used[i]:
                        i = j
            self.keys[i] = key
        self.values[i] = value
        self.used[i] = self.time

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Mapa de hash mais uma lista duplamente encadeada

Intuição

Cada nó da lista se conecta aos dois vizinhos, então, com o nó em mãos, você pode removê-lo da lista ou inseri-lo no início alterando quatro ligações. O mapa fornece o nó, então nenhuma operação percorre a lista.

Um acesso bem-sucedido ou uma inserção de uma chave em cache move o nó para o início. Uma nova chave em um cache cheio remove o nó do final e exclui sua chave do mapa, por isso cada nó armazena sua própria chave. Os nós sentinela head e tail permanecem nas extremidades, então a remoção e a inserção nunca precisam verificar se falta um vizinho. Cada operação consiste em uma busca e algumas alterações de ligações: O(1).

Algoritmo

Conecte os sentinelas da lista head e tail; inicie um mapa vazio de chaves para nós.
get key: retorne -1 se a chave não estiver no mapa; caso contrário, mova o nó para depois de head e retorne seu valor.
put de uma chave armazenada em cache: armazene o valor e mova o nó para depois de head.
put de uma nova chave: se o mapa contiver capacity chaves, desvincule o nó antes de tail e exclua sua chave do mapa. Insira um novo nó depois de head e mapeie a chave para ele.

class ListNode:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}            # key -> its node in the list
        # Sentinels: head.next is the most recently used node,
        # tail.prev the least recently used one.
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
        else:
            if len(self.nodes) == self.capacity:
                # Full: drop the least recently used node.
                oldest = self.tail.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]
            node = ListNode(key, value)
            self.nodes[key] = node
        self._push_front(node)

def lruCacheOps(capacity, ops, keys, values):
    cache = LRUCache(capacity)
    result = []
    for op, key, value in zip(ops, keys, values):
        if op == "put":
            cache.put(key, value)
            result.append("null")
        else:
            result.append(str(cache.get(key)))
    return result

Armadilhas e casos extremos

Não mover uma chave para o início quando ocorre um acerto em get. No primeiro exemplo, put 3 então removeria a chave 1, não a chave 2.
Remover um item antes de verificar se a chave está em cache. Com capacidade 2, put 1, put 2, put 2 removeria a chave 1.
Desvincular um nó, mas deixar sua chave no mapa, ou o contrário. O mapa então retorna um nó desvinculado, e movê-lo corrompe os vínculos com seus antigos vizinhos.
Tratar um 0 armazenado como uma ausência. No terceiro exemplo, get 0 deve retornar "0".

Perguntas frequentes3

Qual é a complexidade de tempo de um cache LRU?

Com um mapa hash e uma lista duplamente encadeada, get e put são executados em O(1): uma busca mais algumas alterações nos links. O espaço é O(capacity), um nó e uma entrada no mapa por chave.

Por que um cache LRU usa uma lista duplamente encadeada?

O cache move as chaves de qualquer posição da ordem para o início e descarta a chave no final. Uma lista duplamente encadeada faz as duas coisas com algumas alterações nos links, porque cada nó conhece o nó anterior. Uma lista simplesmente encadeada precisa percorrer a lista a partir do início para encontrar esse nó, o que é O(capacity).

Você consegue criar um cache LRU com um dicionário ordenado?

Sim. Um mapa que mantém a ordem de inserção, como o OrderedDict do Python ou o LinkedHashMap do Java, pode substituir a lista: mova uma chave para o final a cada uso e remova a do início, ainda em O(1). Em entrevistas, geralmente esperam que você implemente a lista manualmente.

def lruCacheOps(capacity, ops, keys, values):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

capacity = 2
ops = ["put", "put", "get", "put", "get", "get"]
keys = [1, 2, 1, 3, 2, 3]
values = [10, 20, 0, 30, 0, 0]

Saída Esperada

["null", "null", "10", "null", "-1", "30"]