LRU Cache

Q: Peux-tu créer un cache LRU avec un dictionnaire ordonné ?

Oui. Une map qui conserve l’ordre d’insertion, comme OrderedDict de Python ou LinkedHashMap de Java, peut remplacer la liste : déplace une clé à la fin à chaque utilisation et supprime l’élément à l’avant, toujours en O(1). Les intervieweurs veulent généralement que la liste soit créée à la main.

MoyenHachage Liste chaînée

+10

Créez un cache pouvant contenir au maximum capacity clés. get key renvoie la valeur de la clé, ou -1 si elle n’est pas dans le cache. put key value stocke la valeur en remplaçant toute ancienne valeur ; si la clé est nouvelle et que le cache est plein, il évince d’abord la clé utilisée la moins récemment. Un get qui trouve sa clé, ainsi que chaque put, compte comme une utilisation.

L’opération i est ops[i] ("get" ou "put") sur la clé keys[i], avec la valeur values[i] (0 pour un get). Exécutez-les dans l’ordre sur un cache vide et renvoyez une chaîne pour chacune : "null" pour un put, la valeur ou "-1" pour un get.

Fonction

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

capacityinteger: le nombre maximal de clés que le cache peut contenir simultanément
opsstring-array: les opérations, dans l’ordre où elles sont exécutées
keysinteger-array: la clé sur laquelle chaque opération porte
valuesinteger-array: la valeur pour chaque put, 0 pour chaque get
Renvoiestring-array: une réponse par opération, sous forme de texte

Contraintes

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Chaque ops[i] est get ou put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ pour une insertion, et values[i] == 0 pour une récupération.

Exemples

Entrée: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Sortie: ["null", "null", "10", "null", "-1", "30"]
Explication: La consultation rend la clé 1 la plus récemment utilisée, donc put 3 évince la clé 2 : get 2 renvoie "-1" et get 3 renvoie "30".

Entrée: 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]
Sortie: ["null", "null", "null", "null", "3", "-1", "4"]
Explication: Le troisième appel à put met à jour la clé 5, qui est déjà en cache : rien n’est évincé et la clé 5 devient la plus récemment utilisée. Donc put 7 évince la clé 6, et non la clé 5.

Entrée: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Sortie: ["-1", "null", "0", "null", "-1", "8"]
Explication: Avec de la place pour une seule clé, chaque nouvelle clé évince la précédente. Le premier get échoue dans un cache vide ; la clé 0 contient ensuite la vraie valeur 0 jusqu’à ce que put 8 l’évince.

Pour aller plus loin

Comment modifieriez-vous le cache pour qu’il évince plutôt la clé la moins fréquemment utilisée, en départageant les égalités selon l’utilisation la moins récente, tout en conservant une complexité O(1) par opération ?

Solution

Une opération get doit trouver rapidement une clé, et une éviction doit trouver rapidement la clé la moins récemment utilisée. Une table de hachage permet de faire la première, et une liste ordonnée selon l’utilisation, la seconde. Utilise les deux : associe chaque clé à son nœud dans une liste doublement chaînée ordonnée selon l’utilisation.

Parcourir un tableau d’entrées avec les dernières heures d’utilisation

Intuition

Stockez jusqu’à capacity entrées dans des tableaux : clé, valeur et horodatage de dernière utilisation provenant d’un compteur qui augmente à chaque opération. Une nouvelle clé dans un cache plein écrase l’entrée ayant le plus petit horodatage, c’est-à-dire la clé inutilisée depuis le plus longtemps. Dans le premier exemple, lors de put 3, la clé 1 a l’horodatage 3 et la clé 2 l’horodatage 2, donc la clé 2 est supprimée.

Chaque opération parcourt jusqu’à capacity entrées : O(n × capacity) pour n opérations, soit des millions de comparaisons pour 3 000 opérations sur un cache de 1 500 clés.

Algorithme

Garde les tableaux keys, values et used, un compteur de remplissage et une horloge à 0.
Chaque opération ajoute 1 à l’horloge et parcourt les entrées remplies pour trouver sa clé.
get : en cas d’échec, renvoie -1 ; en cas de succès, définit used sur l’horloge et renvoie la valeur.
put : en cas de succès, stocke la valeur et l’horloge. En cas d’échec, écrit la clé, la valeur et l’horloge dans une entrée libre ou dans l’entrée dont used est le plus petit.

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

Table de hachage et liste doublement chaînée

Intuition

Chaque nœud de la liste est lié à ses deux voisins ; avec le nœud en main, tu peux donc le délier ou l’insérer au début en modifiant quatre liens. La map te donne le nœud, donc aucune opération ne parcourt la liste.

Un succès de get, ou un put d’une clé mise en cache, déplace le nœud au début. Une nouvelle clé dans un cache plein supprime le nœud à la fin et efface sa clé de la map, c’est pourquoi chaque nœud stocke sa propre clé. Les nœuds sentinelles head et tail restent aux extrémités, donc le délien et l’insertion n’ont jamais à vérifier si un voisin est absent. Chaque opération consiste en une recherche et quelques modifications de liens : O(1).

Algorithme

Reliez les sentinelles head et tail ; démarrez une map vide associant chaque clé à un nœud.
get key : renvoyez -1 si la clé ne figure pas dans la map ; sinon, déplacez son nœud après head et renvoyez sa valeur.
put pour une clé en cache : stockez la valeur et déplacez le nœud après head.
put pour une nouvelle clé : si la map contient capacity clés, détachez le nœud précédant tail et supprimez sa clé de la map. Insérez un nouveau nœud après head et associez-y la clé dans la map.

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

Pièges et cas limites

Ne pas déplacer une clé au début lors d’un accès réussi avec get. Dans le premier exemple, put 3 évincerait alors la clé 1, et non la clé 2.
Évincer avant de vérifier si la clé est en cache. Avec une capacité de 2, put 1, put 2, put 2 éjecteraient la clé 1.
Délier un nœud tout en laissant sa clé dans la map, ou l’inverse. La map renvoie alors un nœud détaché, et son déplacement corrompt les liens de ses anciens voisins.
Traiter un 0 stocké comme un échec de cache. Dans le troisième exemple, get 0 doit renvoyer "0".

Questions fréquentes3

Quelle est la complexité temporelle d’un cache LRU ?

Avec une table de hachage et une liste doublement chaînée, get et put s’exécutent tous deux en O(1) : une recherche et quelques modifications de liens. L’espace nécessaire est en O(capacity), avec un nœud et une entrée dans la table pour chaque clé.

Pourquoi un cache LRU utilise-t-il une liste doublement chaînée ?

Le cache déplace les clés de n’importe quel endroit de l’ordre vers le début et supprime la clé à la fin. Une liste doublement chaînée effectue les deux opérations avec quelques modifications de liens, car chaque nœud connaît le nœud qui le précède. Une liste simplement chaînée nécessite de parcourir la liste depuis la tête pour trouver ce nœud, ce qui est en O(capacité).

Peux-tu créer un cache LRU avec un dictionnaire ordonné ?

Oui. Une map qui conserve l’ordre d’insertion, comme OrderedDict de Python ou LinkedHashMap de Java, peut remplacer la liste : déplace une clé à la fin à chaque utilisation et supprime l’élément à l’avant, toujours en O(1). Les intervieweurs veulent généralement que la liste soit créée à la main.

def lruCacheOps(capacity, ops, keys, values):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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