LRU Cache

Q: Riesci a creare una cache LRU con un dizionario ordinato?

Sì. Una mappa che mantiene l’ordine di inserimento, come OrderedDict di Python o LinkedHashMap di Java, può sostituire la lista: sposta una chiave alla fine a ogni utilizzo ed espelli quella in testa, sempre in O(1). Di solito chi conduce il colloquio si aspetta che la lista sia realizzata a mano.

MedioHashing Lista concatenata

+10

Costruisci una cache che contenga al massimo capacity chiavi. get key restituisce il valore della chiave oppure -1 se non è memorizzata nella cache. put key value memorizza il valore, sostituendo quello precedente; se la chiave è nuova e la cache è piena, rimuove prima la chiave meno usata di recente. Un get che trova la propria chiave e ogni put contano come utilizzi.

L’operazione i è ops[i] ("get" o "put") sulla chiave keys[i], con valore values[i] (0 per un get). Esegui le operazioni nell’ordine indicato su una cache vuota e restituisci una stringa per ciascuna: "null" per un put, il valore o "-1" per un get.

Funzione

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

capacityinteger: il numero massimo di chiavi che la cache può contenere contemporaneamente
opsstring-array: le operazioni, nell’ordine in cui vengono eseguite
keysinteger-array: la chiave su cui opera ciascuna operazione
valuesinteger-array: il valore per ogni put, 0 per ogni get
Restituiscestring-array: una risposta per operazione, come testo

Vincoli

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Ogni ops[i] è get oppure put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ per un'operazione put, e values[i] == 0 per un'operazione get.

Esempi

Input: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Output: ["null", "null", "10", "null", "-1", "30"]
Spiegazione: La chiamata a get rende la chiave 1 quella usata più di recente, quindi put 3 elimina la chiave 2: get 2 restituisce "-1" e get 3 restituisce "30".

Input: 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]
Output: ["null", "null", "null", "null", "3", "-1", "4"]
Spiegazione: Il terzo inserimento aggiorna la chiave 5, che è già nella cache: non viene rimosso nulla e la chiave 5 diventa quella usata più di recente. Quindi put 7 rimuove dalla cache la chiave 6, non la chiave 5.

Input: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Output: ["-1", "null", "0", "null", "-1", "8"]
Spiegazione: Con spazio per una sola chiave, ogni nuova chiave rimuove quella precedente. La prima operazione get non trova nulla in una cache vuota; la chiave 0 contiene quindi il valore reale 0 finché put 8 non la rimuove.

Per approfondire

Come modificheresti la cache per espellere invece la chiave meno usata di frequente, risolvendo i pareggi a favore di quella usata meno di recente, sempre in O(1) per operazione?

Soluzione

Una lettura deve trovare rapidamente una chiave, mentre un’espulsione deve trovare rapidamente la chiave meno usata di recente. Una mappa hash fa la prima cosa, una lista ordinata in base all’uso fa la seconda. Usale entrambe: associa ogni chiave al suo nodo in una lista doppiamente concatenata ordinata in base all’uso.

Scansiona una tabella di voci con i rispettivi orari dell’ultimo utilizzo

Intuizione

Memorizza fino a capacity voci negli array: chiave, valore e un timestamp dell’ultimo utilizzo ricavato da un contatore che aumenta a ogni operazione. Una nuova chiave in una cache piena sovrascrive la voce con il timestamp più piccolo, cioè la chiave rimasta inutilizzata più a lungo. Nel primo esempio, con put 3, la chiave 1 ha timestamp 3 e la chiave 2 ha timestamp 2, quindi viene eliminata la chiave 2.

Ogni operazione esegue una scansione di un massimo di capacity voci: O(n × capacity) per n operazioni, milioni di confronti con 3,000 operazioni su una cache di 1,500 chiavi.

Algoritmo

Mantieni gli array keys, values e used, un conteggio degli elementi riempiti e un orologio impostato a 0.
Ogni operazione aggiunge 1 all'orologio e cerca la propria chiave tra gli elementi riempiti.
get: in caso di mancata corrispondenza, restituisci -1; in caso di corrispondenza, imposta used sull'orologio e restituisci il valore.
put: in caso di corrispondenza, memorizza il valore e l'orologio. In caso di mancata corrispondenza, scrivi la chiave, il valore e l'orologio in un elemento libero oppure nell'elemento con il valore used più piccolo.

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

Tabella hash e lista doppiamente concatenata

Intuizione

Ogni nodo della lista è collegato a entrambi i vicini, quindi, avendo il nodo a disposizione, puoi scollegarlo oppure inserirlo in testa modificando quattro collegamenti. La mappa ti fornisce il nodo, quindi nessuna operazione scorre la lista.

Una richiesta soddisfatta dalla cache, o un inserimento di una chiave già presente nella cache, sposta il nodo in testa. Quando una nuova chiave viene inserita in una cache piena, viene rimosso il nodo in fondo e la relativa chiave viene eliminata dalla mappa: ecco perché ogni nodo memorizza la propria chiave. I nodi sentinella head e tail rimangono alle estremità, quindi le operazioni di scollegamento e inserimento non devono mai verificare se manca un vicino. Ogni operazione consiste in una ricerca e alcune modifiche ai collegamenti: O(1).

Algoritmo

Collega i sentinella head e tail; avvia una mappa vuota da chiavi a nodi.
get key: restituisci -1 se la chiave non è nella mappa; altrimenti sposta il suo nodo dopo head e restituisci il suo valore.
put di una chiave memorizzata nella cache: memorizza il valore e sposta il nodo dopo head.
put di una nuova chiave: se la mappa contiene capacity chiavi, scollega il nodo prima di tail ed elimina la sua chiave dalla mappa. Inserisci un nuovo nodo dopo head e associa la chiave a esso nella mappa.

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

Trappole e casi limite

Non spostare una chiave in testa quando viene trovata con get. Nel primo esempio, put 3 espellerebbe quindi la chiave 1, non la chiave 2.
Espellere una chiave prima di verificare se è memorizzata nella cache. Con capacità 2, put 1, put 2, put 2 eliminerebbero la chiave 1.
Scollegare un nodo lasciando però la sua chiave nella mappa, o viceversa. La mappa restituisce quindi un nodo scollegato e spostarlo corrompe i collegamenti con i nodi vicini originali.
Considerare uno 0 memorizzato come un'assenza. Nel terzo esempio, get 0 deve restituire "0".

Domande frequenti3

Qual è la complessità temporale di una cache LRU?

Con una mappa hash e una lista doppiamente concatenata, get e put richiedono entrambi O(1): una ricerca più alcune modifiche ai collegamenti. Lo spazio è O(capacity), con un nodo e una voce nella mappa per ogni chiave.

Perché una cache LRU usa una lista doppiamente concatenata?

La cache sposta le chiavi da qualsiasi punto dell’ordine all’inizio e rimuove la chiave in fondo. Una lista doppiamente concatenata fa entrambe le cose con poche modifiche ai collegamenti, perché ogni nodo conosce il nodo che lo precede. Una lista semplicemente concatenata richiede una scansione dalla testa per trovare quel nodo, con complessità O(capacity).

Riesci a creare una cache LRU con un dizionario ordinato?

Sì. Una mappa che mantiene l’ordine di inserimento, come OrderedDict di Python o LinkedHashMap di Java, può sostituire la lista: sposta una chiave alla fine a ogni utilizzo ed espelli quella in testa, sempre in O(1). Di solito chi conduce il colloquio si aspetta che la lista sia realizzata a mano.

def lruCacheOps(capacity, ops, keys, values):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

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