LRU Cache

Q: Czy potrafisz zbudować pamięć podręczną LRU z uporządkowanym słownikiem?

Tak. Mapa, która zachowuje kolejność wstawiania, taka jak OrderedDict w Pythonie lub LinkedHashMap w Javie, może zastąpić listę: przenoś klucz na koniec przy każdym użyciu i usuwaj elementy z początku, nadal w O(1). Osoby prowadzące rozmowę kwalifikacyjną zwykle oczekują, że lista zostanie zbudowana ręcznie.

ŚrednieHaszowanie Lista wiązana

+10

Zbuduj pamięć podręczną, która przechowuje najwyżej capacity kluczy. get key zwraca wartość klucza lub -1, jeśli nie znajduje się on w pamięci podręcznej. put key value zapisuje wartość, zastępując wcześniejszą; jeśli klucz jest nowy, a pamięć podręczna jest pełna, najpierw usuwa klucz, który był używany najdawniej. Odczyt, który znajduje klucz, oraz każde zapisanie liczą się jako użycie.

Operacja i to ops[i] ("get" lub "put") dla klucza keys[i], z wartością values[i] (0 dla odczytu). Wykonaj je po kolei na pustej pamięci podręcznej i zwróć po jednym ciągu znaków dla każdej: "null" dla zapisu, wartość lub "-1" dla odczytu.

Funkcja

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

capacityinteger: maksymalna liczba kluczy, które pamięć podręczna może przechowywać jednocześnie
opsstring-array: operacje, w kolejności ich wykonywania
keysinteger-array: klucz, na którym działa każda operacja
valuesinteger-array: wartość dla każdego put, 0 dla każdego get
Zwracastring-array: jedna odpowiedź na operację, jako tekst

Ograniczenia

1 ≤ capacity ≤ 3000
1 ≤ ops.length ≤ 3000
keys.length == values.length == ops.length
Każde ops[i] to get albo put.
0 ≤ keys[i] ≤ 10⁹
0 ≤ values[i] ≤ 10⁹ dla operacji put oraz values[i] == 0 dla operacji get.

Przykłady

Wejście: capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
Wyjście: ["null", "null", "10", "null", "-1", "30"]
Wyjaśnienie: Operacja get sprawia, że klucz 1 jest ostatnio używany, więc put 3 usuwa klucz 2: get 2 zwraca "-1", a get 3 zwraca "30".

Wejście: 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]
Wyjście: ["null", "null", "null", "null", "3", "-1", "4"]
Wyjaśnienie: Trzecie wywołanie put aktualizuje klucz 5, który jest już w pamięci podręcznej: nic nie zostaje usunięte, a klucz 5 staje się ostatnio używany. Dlatego put 7 usuwa klucz 6, a nie klucz 5.

Wejście: capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
Wyjście: ["-1", "null", "0", "null", "-1", "8"]
Wyjaśnienie: Przy miejscu na jeden klucz każdy nowy klucz usuwa poprzedni. Pierwsze pobranie kończy się brakiem trafienia w pustej pamięci podręcznej; klucz 0 przechowuje następnie rzeczywistą wartość 0, aż put 8 ją usunie.

Pytanie dodatkowe

Jak zmienić pamięć podręczną tak, aby zamiast tego usuwała klucz używany najrzadziej, a remisy rozstrzygała na korzyść klucza używanego najdawniej, zachowując złożoność O(1) dla każdej operacji?

Rozwiązanie

Operacja get musi szybko znaleźć klucz, a eksmisja — szybko znaleźć klucz używany najdawniej. Pierwsze zadanie wykonuje mapa mieszająca, drugie — lista uporządkowana według użycia. Użyj obu: przypisz każdy klucz do jego węzła na dwukierunkowej liście połączonej, uporządkowanej według użycia.

Skanuj tabelę wpisów z czasem ostatniego użycia

Intuicja

Przechowuj w tablicach maksymalnie capacity wpisów: klucz, wartość i znacznik ostatniego użycia z licznika zwiększanego przy każdej operacji. Nowy klucz w pełnej pamięci podręcznej zastępuje wpis z najmniejszym znacznikiem — klucz, który najdłużej nie był używany. W pierwszym przykładzie przy put 3 klucz 1 ma znacznik 3, a klucz 2 ma znacznik 2, więc usuwany jest klucz 2.

Każda operacja skanuje maksymalnie capacity wpisów: O(n × capacity) dla n operacji; przy 3 000 operacjach na pamięci podręcznej zawierającej 1 500 kluczy oznacza to miliony porównań.

Algorytm

Zachowuj tablice keys, values i used, licznik wypełnionych pozycji oraz zegar ustawiony na 0.
Każda operacja zwiększa zegar o 1 i przeszukuje wypełnione pozycje w poszukiwaniu swojego klucza.
get: w przypadku braku zwróć -1; w przypadku trafienia ustaw used na wartość zegara i zwróć wartość.
put: w przypadku trafienia zapisz wartość i wartość zegara. W przypadku braku wpisz klucz, wartość i wartość zegara do wolnej pozycji albo do pozycji o najmniejszej wartości 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

Tablica mieszająca i lista dwukierunkowa

Intuicja

Każdy węzeł listy jest połączony z oboma sąsiadami, więc mając węzeł pod ręką, możesz go odłączyć lub wstawić na początku, zmieniając cztery połączenia. Mapa wskazuje węzeł, więc żadna operacja nie przechodzi przez listę.

Trafienie podczas pobierania lub zapis klucza znajdującego się już w pamięci podręcznej przenosi węzeł na początek. Dodanie nowego klucza do pełnej pamięci podręcznej usuwa ostatni węzeł i jego klucz z mapy, dlatego każdy węzeł przechowuje własny klucz. Węzły wartownicze head i tail pozostają na końcach, więc odłączanie i wstawianie nigdy nie wymaga sprawdzania, czy brakuje sąsiada. Każda operacja to jedno wyszukanie i kilka zmian połączeń: O(1).

Algorytm

Połącz wartowniki head i tail; rozpocznij od pustej mapy kluczy i węzłów.
get key: zwróć -1, jeśli klucza nie ma w mapie; w przeciwnym razie przenieś jego węzeł za head i zwróć jego wartość.
put dla klucza w pamięci podręcznej: zapisz wartość i przenieś węzeł za head.
put dla nowego klucza: jeśli mapa zawiera capacity kluczy, odłącz węzeł przed tail i usuń jego klucz z mapy. Wstaw nowy węzeł za head i przypisz mu klucz w mapie.

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

Pułapki i przypadki brzegowe

Nieprzenoszenie klucza na początek po trafieniu przy pobieraniu. W pierwszym przykładzie put 3 usunęłoby wtedy klucz 1, a nie klucz 2.
Usuwanie elementu przed sprawdzeniem, czy klucz znajduje się w pamięci podręcznej. Przy pojemności 2 sekwencja put 1, put 2, put 2 usunęłaby klucz 1.
Odłączanie węzła, ale pozostawianie jego klucza w mapie, lub odwrotnie. Mapa zwraca wtedy odłączony węzeł, a przeniesienie go uszkadza powiązania z jego dawnymi sąsiadami.
Traktowanie zapisanego 0 jako braku trafienia. W trzecim przykładzie get 0 musi zwrócić "0".

Najczęstsze pytania3

C jaka jest złożoność czasowa pamięci podręcznej LRU?

Dzięki mapie haszującej i dwukierunkowej liście wiązanej operacje get i put działają w czasie O(1): jedno wyszukiwanie i kilka zmian powiązań. Złożoność pamięciowa wynosi O(capacity): jeden węzeł i jeden wpis w mapie na klucz.

Dlaczego pamięć podręczna LRU używa listy dwukierunkowej?

Pamięć podręczna przenosi klucze z dowolnego miejsca w kolejności na początek i usuwa klucz z końca. Lista dwukierunkowa wykonuje obie te operacje za pomocą kilku zmian odsyłaczy, ponieważ każdy węzeł zna poprzedzający go węzeł. W przypadku listy jednokierunkowej trzeba przejść od początku, aby znaleźć ten węzeł, co zajmuje O(capacity).

Czy potrafisz zbudować pamięć podręczną LRU z uporządkowanym słownikiem?

Tak. Mapa, która zachowuje kolejność wstawiania, taka jak OrderedDict w Pythonie lub LinkedHashMap w Javie, może zastąpić listę: przenoś klucz na koniec przy każdym użyciu i usuwaj elementy z początku, nadal w O(1). Osoby prowadzące rozmowę kwalifikacyjną zwykle oczekują, że lista zostanie zbudowana ręcznie.

def lruCacheOps(capacity, ops, keys, values):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

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