LRU Cache

Q: ¿Puedes crear una caché LRU con un diccionario ordenado?

Sí. Un mapa que mantiene el orden de inserción, como OrderedDict de Python o LinkedHashMap de Java, puede reemplazar la lista: mueve una clave al final en cada uso y expulsa desde el principio, manteniendo O(1). En las entrevistas, normalmente quieren que construyas la lista a mano.

MedioHashing Lista enlazada

+10

Construye una caché que almacene como máximo capacity claves. get key devuelve el valor de la clave, o -1 si no está en la caché. put key value almacena el valor y reemplaza cualquier valor anterior; si la clave es nueva y la caché está llena, primero expulsa la clave menos usada recientemente. Un get que encuentra su clave y cada put cuentan como un uso.

La operación i es ops[i] ("get" o "put") sobre la clave keys[i], con el valor values[i] (0 para un get). Ejecútalas en orden sobre una caché vacía y devuelve una cadena por cada una: "null" para un put, el valor o "-1" para un get.

Función

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

capacityinteger: la cantidad máxima de claves que la caché puede contener a la vez
opsstring-array: las operaciones, en el orden en que se ejecutan
keysinteger-array: la clave sobre la que trabaja cada operación
valuesinteger-array: el valor de cada put, 0 de cada get
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Cada ops[i] es get o put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ para una operación de inserción, y values[i] == 0 para una operación de obtención.

Ejemplos

Entrada: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Salida: ["null", "null", "10", "null", "-1", "30"]
Explicación: El acceso hace que la clave 1 sea la más recientemente utilizada, así que put 3 expulsa la clave 2: get 2 devuelve "-1" y get 3 devuelve "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]
Salida: ["null", "null", "null", "null", "3", "-1", "4"]
Explicación: La tercera operación put actualiza la clave 5, que ya está en caché: no se expulsa nada y la clave 5 pasa a ser la más recientemente usada. Así que put 7 expulsa la clave 6, no la clave 5.

Entrada: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Salida: ["-1", "null", "0", "null", "-1", "8"]
Explicación: Con espacio para una clave, cada clave nueva expulsa a la anterior. El primer get no encuentra nada en una caché vacía; después, la clave 0 conserva el valor real 0 hasta que put 8 la expulsa.

Para ir más allá

¿Cómo cambiarías la caché para que, en su lugar, expulse la clave menos utilizada, resolviendo los empates según el uso menos reciente, y siga siendo O(1) por operación?

Solución

Una operación get debe encontrar una clave rápidamente, y una expulsión debe encontrar rápidamente la clave menos usada recientemente. Un mapa hash resuelve lo primero; una lista ordenada según el uso, lo segundo. Usa ambos: asigna cada clave a su nodo en una lista doblemente enlazada ordenada según el uso.

Recorre una tabla de entradas con sus últimos tiempos de uso

Intuición

Almacena hasta capacity entradas en arrays: clave, valor y una marca de último uso de un contador que aumenta con cada operación. Una clave nueva en una caché llena sobrescribe la entrada con la marca más pequeña, es decir, la clave que lleva más tiempo sin usarse. En el primer ejemplo, en put 3, la clave 1 tiene la marca 3 y la clave 2 tiene la marca 2, así que se elimina la clave 2.

Cada operación recorre hasta capacity entradas: O(n × capacity) para n operaciones, millones de comparaciones con 3,000 operaciones en una caché de 1,500 claves.

Algoritmo

Mantén los arreglos keys, values y used, un contador de elementos ocupados y un reloj en 0.
Cada operación suma 1 al reloj y busca su clave entre las entradas ocupadas.
get: si no se encuentra, devuelve -1; si se encuentra, asigna el valor del reloj a used y devuelve el valor.
put: si se encuentra, almacena el valor y el valor del reloj. Si no se encuentra, escribe la clave, el valor y el valor del reloj en una entrada libre o en la entrada con el valor más pequeño 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

Tabla hash más una lista doblemente enlazada

Intuición

Cada nodo de la lista está enlazado a ambos vecinos, así que, con el nodo a mano, puedes desenlazarlo o insertarlo al principio cambiando cuatro enlaces. El mapa te proporciona el nodo, por lo que ninguna operación recorre la lista.

Un acierto de get, o un put de una clave almacenada en caché, mueve el nodo al principio. Una clave nueva en una caché llena elimina el nodo del final y borra su clave del mapa; por eso cada nodo almacena su propia clave. Los nodos centinela head y tail permanecen en los extremos, así que al desenlazar e insertar nunca hay que comprobar si falta un vecino. Cada operación consiste en una búsqueda y unos pocos cambios de enlaces: O(1).

Algoritmo

Vincula los centinelas head y tail; inicia un mapa vacío de claves a nodos.
get key: devuelve -1 si la clave no está en el mapa; de lo contrario, mueve su nodo después de head y devuelve su valor.
put de una clave almacenada en caché: guarda el valor y mueve el nodo después de head.
put de una clave nueva: si el mapa contiene capacity claves, desvincula el nodo anterior a tail y elimina su clave del mapa. Inserta un nodo nuevo después de head y asigna la clave a ese nodo en el mapa.

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

Errores comunes y casos límite

No mover una clave al frente cuando se encuentra en una operación get. En el primer ejemplo, put 3 desalojaría después la clave 1, no la clave 2.
Desalojar antes de comprobar si la clave está en caché. Con capacidad 2, put 1, put 2, put 2 expulsaría la clave 1.
Desvincular un nodo pero dejar su clave en el mapa, o viceversa. El mapa devuelve entonces un nodo desvinculado, y moverlo corrompe los enlaces de sus antiguos vecinos.
Tratar un 0 almacenado como un fallo de caché. En el tercer ejemplo, get 0 debe devolver "0".

Preguntas frecuentes3

¿Cuál es la complejidad temporal de una caché LRU?

Con un mapa hash y una lista doblemente enlazada, get y put se ejecutan en O(1): una búsqueda y unos pocos cambios de enlaces. El espacio es O(capacity), un nodo y una entrada del mapa por clave.

¿Por qué una caché LRU utiliza una lista doblemente enlazada?

La caché mueve las claves desde cualquier posición del orden hasta el principio y elimina la clave del final. Una lista doblemente enlazada hace ambas cosas con unos pocos cambios en los enlaces, porque cada nodo conoce el nodo anterior. Una lista simplemente enlazada necesita recorrer desde la cabeza para encontrar ese nodo, lo que requiere O(capacity).

¿Puedes crear una caché LRU con un diccionario ordenado?

Sí. Un mapa que mantiene el orden de inserción, como OrderedDict de Python o LinkedHashMap de Java, puede reemplazar la lista: mueve una clave al final en cada uso y expulsa desde el principio, manteniendo O(1). En las entrevistas, normalmente quieren que construyas la lista a mano.

def lruCacheOps(capacity, ops, keys, values):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #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]

Salida Esperada

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