LRU Cache
Создайте кэш, в котором хранится не более capacity ключей. get key возвращает значение ключа или -1, если ключ отсутствует в кэше. put key value сохраняет значение, заменяя предыдущее; если ключ новый, а кэш заполнен, сначала удаляется ключ, который использовался давнее всего. Успешный поиск ключа с помощью get и каждая операция put считаются использованием.
Операция i — это ops[i] ("get" или "put") для ключа keys[i] со значением values[i] (0 для get). Выполните их по порядку для пустого кэша и верните по одной строке для каждой операции: "null" для put, значение или "-1" для get.
Функция
- capacityinteger
- максимальное количество ключей, которые кэш может хранить одновременно
- opsstring-array
- операции в порядке их выполнения
- keysinteger-array
- ключ, с которым работает каждая операция
- valuesinteger-array
- значение для каждого put, 0 для каждого get
- Возвращаетstring-array
- один ответ на операцию в виде текста
Ограничения
1 ≤ capacity ≤ 30001 ≤ ops.length ≤ 3000keys.length == values.length == ops.length- Каждый элемент
ops[i]— этоgetилиput. 0 ≤ keys[i] ≤ 1090 ≤ values[i] ≤ 109для операции put, аvalues[i] == 0— для операции get.
Примеры
- Ввод
- capacity = 2ops = ["put", "put", "get", "put", "get", "get"]keys = [1, 2, 1, 3, 2, 3]values = [10, 20, 0, 30, 0, 0]
- Вывод
- ["null", "null", "10", "null", "-1", "30"]
- Пояснение
- Вызов get делает ключ 1 наиболее недавно использованным, поэтому
put 3вытесняет ключ 2:get 2возвращает"-1", аget 3возвращает"30".
- Ввод
- 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]
- Вывод
- ["null", "null", "null", "null", "3", "-1", "4"]
- Пояснение
- Третья операция
put 7обновляет ключ 5, который уже находится в кэше: ничего не вытесняется, и ключ 5 становится наиболее недавно использованным. Поэтомуput 7вытесняет ключ 6, а не ключ 5.
- Ввод
- capacity = 1ops = ["get", "put", "get", "put", "get", "get"]keys = [0, 0, 0, 8, 0, 8]values = [0, 0, 0, 8, 0, 0]
- Вывод
- ["-1", "null", "0", "null", "-1", "8"]
- Пояснение
- При наличии места только для одного ключа каждый новый ключ вытесняет предыдущий. Первый вызов get не находит ничего в пустом кэше; затем ключ 0 хранит настоящее значение 0, пока
put 8не вытеснит его.
Дополнительный вопрос
Как изменить кэш, чтобы вместо этого удалять ключ, который использовался реже всего, а при равенстве частоты — тот, который использовался давнее всего, сохраняя сложность O(1) на операцию?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Чтобы вытеснить нужный ключ, нужно знать, в каком порядке использовались ключи в последний раз. Какая структура сохраняет порядок и позволяет переместить любой элемент в начало или убрать один с конца, не сдвигая остальные?
Двусвязный список отсоединяет узел или вставляет его в начало, изменяя четыре ссылки, но только если у вас уже есть этот узел. Хеш-таблица, сопоставляющая каждому ключу его узел, позволяет получить этот узел за O(1).
Храните узел, использованный последним, в начале, а узел, использованный давнее всего, — в конце. При успешном get или любом put перемещайте узел в начало. Когда поступает новый ключ и кэш заполнен, удалите последний узел из списка, а его ключ — из отображения. Два узла-стража на концах избавят вас от необходимости проверять, пуст ли список.
Решение
Операция get должна быстро находить ключ, а операция вытеснения — быстро находить ключ, который дольше всего не использовался. Первую задачу решает хеш-таблица, вторую — список, упорядоченный по использованию. Используй оба: сопоставь каждый ключ с его узлом в двусвязном списке, упорядоченном по использованию.
Просканируйте таблицу записей с указанием времени последнего использования
Идея
Храни до capacity записей в массивах: ключ, значение и отметку времени последнего использования из счётчика, который увеличивается при каждой операции. Новый ключ в заполненном кэше заменяет запись с наименьшей отметкой времени — ту, чей ключ дольше всего не использовался. В первом примере при put 3 у ключа 1 отметка времени равна 3, а у ключа 2 — 2, поэтому удаляется ключ 2.
При каждой операции просматривается до capacity записей: O(n × capacity) для n операций — миллионы сравнений при 3 000 операциях в кэше из 1 500 ключей.
Алгоритм
- Оставь массивы
keys,valuesиused, счётчик заполненных элементов и часы со значением 0. - Каждая операция увеличивает часы на 1 и ищет ключ среди заполненных элементов.
get: при отсутствии ключа верни-1; при его наличии установиusedравным значению часов и верни значение.put: при наличии ключа сохрани значение и значение часов. Если ключа нет, запиши ключ, значение и значение часов в свободную ячейку или в ячейку с наименьшим значением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Хеш-таблица и двусвязный список
Идея
Каждый узел списка связан с обоими соседями, поэтому, имея узел, можно отвязать его или вставить в начало, изменив четыре ссылки. Карта передаёт вам узел, поэтому ни одна операция не проходит по списку.
При попадании в кэш или при добавлении уже закэшированного ключа узел перемещается в начало. Если в полном кэше появляется новый ключ, удаляется последний узел и его ключ удаляется из карты, поэтому каждый узел хранит собственный ключ. Узлы-сторожи head и tail остаются на концах, поэтому при отвязывании и вставке не нужно проверять, отсутствует ли сосед. Каждая операция состоит из одного поиска и нескольких изменений ссылок: O(1).
Алгоритм
- Свяжите фиктивные узлы
headиtail; создайте пустое отображение ключей на узлы. get key: верните-1, если ключа нет в отображении; в противном случае переместите его узел послеheadи верните его значение.putдля кэшированного ключа: сохраните значение и переместите узел послеhead.putдля нового ключа: если отображение содержитcapacityключей, отсоедините узел передtailи удалите его ключ из отображения. Вставьте новый узел послеheadи свяжите с ним ключ в отображении.
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
Ловушки и крайние случаи
- Не перемещать ключ в начало при успешном вызове get. В первом примере
put 3вытеснит ключ 1, а не ключ 2. - Вытеснять элемент до проверки, кэширован ли ключ. При ёмкости 2 последовательность
put 1,put 2,put 2вытеснит ключ 1. - Отвязать узел, но оставить его ключ в отображении, или наоборот. Тогда отображение вернёт отсоединённый узел, и его перемещение повредит связи с его прежними соседями.
- Считать сохранённый 0 промахом. В третьем примере
get 0должен вернуть"0".
Частые вопросы3
Какова временная сложность кэша LRU?
С хеш-таблицей и двусвязным списком операции get и put выполняются за O(1): один поиск и несколько изменений связей. Требуемая память — O(capacity): один узел и одна запись в таблице на каждый ключ.
Почему в кэше LRU используется двусвязный список?
Кэш перемещает ключи из любого места в порядке в начало и удаляет ключ с конца. Двусвязный список выполняет обе операции за несколько изменений ссылок, потому что каждый узел знает узел перед ним. В односвязном списке нужно пройти от головы, чтобы найти этот узел, что занимает O(capacity).
Можешь создать кэш LRU с помощью упорядоченного словаря?
Да. Словарь, сохраняющий порядок вставки, например OrderedDict в Python или LinkedHashMap в Java, может заменить список: при каждом использовании перемещайте ключ в конец, а удаляйте элемент из начала — всё так же за O(1). На собеседованиях обычно ожидают, что список будет реализован вручную.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def lruCacheOps(capacity, ops, keys, values):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
capacity = 2 ops = ["put", "put", "get", "put", "get", "get"] keys = [1, 2, 1, 3, 2, 3] values = [10, 20, 0, 30, 0, 0]
Ожидаемый вывод
["null", "null", "10", "null", "-1", "30"]