LRU Cache

+10

Erstelle einen Cache, der höchstens capacity Schlüssel enthält. get key gibt den Wert des Schlüssels zurück oder -1, wenn er nicht im Cache gespeichert ist. put key value speichert den Wert und ersetzt dabei einen möglicherweise vorhandenen älteren Wert. Ist der Schlüssel neu und der Cache voll, wird zuerst der am längsten nicht verwendete Schlüssel entfernt. Ein get, bei dem der Schlüssel gefunden wird, und jedes put zählen als Verwendung.

Die Operation i ist ops[i] ("get" oder "put") für den Schlüssel keys[i] mit dem Wert values[i] (0 bei einem get). Führe sie der Reihe nach in einem leeren Cache aus und gib jeweils eine Zeichenfolge zurück: "null" bei einem put, bei einem get den Wert oder "-1".

Funktion

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

capacityinteger: die maximale Anzahl an Schlüsseln, die der Cache gleichzeitig enthalten kann
opsstring-array: die Operationen in der Reihenfolge, in der sie ausgeführt werden
keysinteger-array: der Schlüssel, auf den jede Operation angewendet wird
valuesinteger-array: den Wert für jedes Einfügen, 0 für jedes Abrufen
Gibt zurückstring-array: eine Antwort pro Operation, als Text

Einschränkungen

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Jedes ops[i] ist get oder put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ für ein Put und values[i] == 0 für ein Get.

Beispiele

Eingabe: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Ausgabe: ["null", "null", "10", "null", "-1", "30"]
Erklärung: Der Aufruf von get macht Schlüssel 1 zum zuletzt verwendeten, daher verdrängt put 3 Schlüssel 2: get 2 gibt "-1" zurück und get 3 gibt "30" zurück.

Eingabe: 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]
Ausgabe: ["null", "null", "null", "null", "3", "-1", "4"]
Erklärung: Der dritte put aktualisiert Schlüssel 5, der bereits im Cache ist: Es wird nichts entfernt und Schlüssel 5 wird zum zuletzt verwendeten Schlüssel. Daher entfernt put 7 Schlüssel 6, nicht Schlüssel 5.

Eingabe: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Ausgabe: ["-1", "null", "0", "null", "-1", "8"]
Erklärung: Bei Platz für einen Schlüssel verdrängt jeder neue Schlüssel den vorherigen. Das erste get schlägt in einem leeren Cache fehl; Schlüssel 0 enthält dann den tatsächlichen Wert 0, bis put 8 ihn verdrängt.

Weiterführende Frage

Wie würdest du den Cache so ändern, dass stattdessen der am seltensten verwendete Schlüssel entfernt wird, wobei bei Gleichstand der am längsten nicht verwendete Schlüssel entfernt wird, und zwar weiterhin in O(1) pro Operation?

Lösung

Ein Abruf muss einen Schlüssel schnell finden, und beim Entfernen muss der am längsten nicht verwendete Schlüssel schnell gefunden werden. Eine Hash-Map erledigt Ersteres, eine nach Verwendung geordnete Liste Letzteres. Verwende beides: Ordne jeden Schlüssel seinem Knoten in einer doppelt verketteten, nach Verwendung geordneten Liste zu.

Tabelle mit Einträgen und ihren letzten Verwendungszeiten durchsuchen

Idee

Speichere bis zu capacity Einträge in Arrays: Schlüssel, Wert und einen Zeitstempel der letzten Verwendung aus einem Zähler, der bei jeder Operation erhöht wird. Ein neuer Schlüssel in einem vollen Cache überschreibt den Eintrag mit dem kleinsten Zeitstempel, also den Schlüssel, der am längsten nicht verwendet wurde. Im ersten Beispiel hat Schlüssel 1 bei put 3 den Zeitstempel 3 und Schlüssel 2 den Zeitstempel 2, also wird Schlüssel 2 entfernt.

Bei jeder Operation werden bis zu capacity Einträge durchsucht: O(n × capacity) für n Operationen, Millionen von Vergleichen bei 3.000 Operationen auf einem Cache mit 1.500 Schlüsseln.

Algorithmus

Behalte die Arrays keys, values und used, einen Füllzähler und eine Uhr bei 0.
Jede Operation erhöht die Uhr um 1 und durchsucht die belegten Einträge nach ihrem Schlüssel.
get: Bei einem Fehlschlag gib -1 zurück; bei einem Treffer setze used auf die Uhr und gib den Wert zurück.
put: Bei einem Treffer speichere den Wert und die Uhr. Bei einem Fehlschlag schreibe Schlüssel, Wert und Uhr in einen freien Eintrag oder in den Eintrag mit dem kleinsten used-Wert.

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

Hash-Map plus doppelt verkettete Liste

Idee

Jeder Listenknoten ist mit beiden Nachbarn verknüpft. Wenn du also den Knoten zur Hand hast, kannst du ihn aus der Liste entfernen oder am Anfang einfügen, indem du vier Verknüpfungen änderst. Die Map liefert dir den Knoten, sodass keine Operation die Liste durchlaufen muss.

Ein erfolgreicher Abruf oder ein put eines zwischengespeicherten Schlüssels verschiebt den Knoten an den Anfang. Ein neuer Schlüssel in einem vollen Cache entfernt den hinteren Knoten und löscht dessen Schlüssel aus der Map. Deshalb speichert jeder Knoten seinen eigenen Schlüssel. Die Wächterknoten head und tail bleiben an den Enden, sodass beim Entfernen und Einfügen nie geprüft werden muss, ob ein Nachbar fehlt. Jede Operation besteht aus einem Lookup und einigen Änderungen an den Verknüpfungen: O(1).

Algorithmus

Verknüpfe die Wächterknoten head und tail; beginne mit einer leeren Zuordnung von Schlüsseln zu Knoten.
get key: gib -1 zurück, wenn der Schlüssel nicht in der Zuordnung enthalten ist; andernfalls verschiebe seinen Knoten hinter head und gib seinen Wert zurück.
put für einen zwischengespeicherten Schlüssel: speichere den Wert und verschiebe den Knoten hinter head.
put für einen neuen Schlüssel: Wenn die Zuordnung capacity Schlüssel enthält, entferne die Verknüpfung des Knotens vor tail und lösche dessen Schlüssel aus der Zuordnung. Füge einen neuen Knoten hinter head ein und ordne ihm den Schlüssel zu.

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

Stolperfallen und Grenzfälle

Bei einem Treffer durch get den Schlüssel nicht an den Anfang verschieben. Im ersten Beispiel würde put 3 dann Schlüssel 1 statt Schlüssel 2 entfernen.
Entfernen, bevor geprüft wird, ob der Schlüssel im Cache liegt. Bei einer Kapazität von 2 würde put 1, put 2, put 2 Schlüssel 1 entfernen.
Einen Knoten aus der Verknüpfung lösen, seinen Schlüssel aber in der Map belassen – oder umgekehrt. Die Map gibt dann einen abgetrennten Knoten zurück, und wenn man ihn verschiebt, werden die Verknüpfungen seiner alten Nachbarn beschädigt.
Einen gespeicherten Wert 0 als Fehlschlag behandeln. Im dritten Beispiel muss get 0 "0" zurückgeben.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität eines LRU-Caches?

Mit einer Hash-Map und einer doppelt verketteten Liste laufen sowohl get als auch put in O(1): eine Suche plus einige Änderungen an den Verknüpfungen. Der Speicherbedarf beträgt O(capacity), ein Knoten und ein Map-Eintrag pro Schlüssel.

Warum verwendet ein LRU-Cache eine doppelt verkettete Liste?

Der Cache verschiebt Schlüssel von beliebigen Positionen in der Reihenfolge nach vorne und entfernt den Schlüssel am Ende. Eine doppelt verkettete Liste erledigt beides mit wenigen Änderungen an den Verknüpfungen, da jeder Knoten den vorherigen Knoten kennt. Bei einer einfach verketteten Liste muss man vom Anfang aus durchlaufen, um diesen Knoten zu finden, was O(capacity) entspricht.

Kannst du einen LRU-Cache mit einem geordneten Wörterbuch erstellen?

Ja. Eine Map, die die Einfügereihenfolge beibehält, wie Pythons OrderedDict oder Javas LinkedHashMap, kann die Liste ersetzen: Verschiebe einen Schlüssel bei jeder Verwendung ans Ende und entferne Elemente vorne, weiterhin in O(1). Interviewer erwarten normalerweise, dass die Liste selbst implementiert wird.

def lruCacheOps(capacity, ops, keys, values):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

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