Реализуйте LRU-кэш на N элементов, в котором get и put работают за O(1)
Проверила команда Сопровод · Обновлено
Короткий ответ
Храните данные в OrderedDict: он помнит порядок ключей и переносит ключ в конец за O(1). В get при попадании вызывайте move_to_end(key), чтобы ключ стал самым свежим. В put записывайте значение, переносите ключ в конец и, если элементов стало больше N, удаляйте самый давний через popitem(last=False). Без OrderedDict то же дают словарь и двусвязный список.
Почему этот вопрос задают
Здесь сходятся структуры данных и стандартная библиотека: нужно собрать класс под жесткое ограничение по сложности. На уровне Senior следом спрашивают про потоки, крайние случаи и устройство без готовых классов.
Условие задачи
Сервис аптечной сети показывает карточки препаратов и держит в памяти кэш на N карточек. Реализуйте класс LRUCache(capacity) с методами get(key) и put(key, value), оба за O(1). get возвращает карточку или None, если ее нет. При переполнении put вытесняет карточку, к которой дольше всех не обращались. Проверьте класс на емкости 2 и шести операциях из таблицы.
Как подойти к решению
- Возьмите
OrderedDict: порядок ключей в нем и будет порядком свежести - Переносите ключ в конец через
move_to_endпри каждом чтении и записи - Удаляйте первый ключ через
popitem(last=False), когда размер превысил емкость - Проверьте сценарий, где
getспасает ключ от вытеснения
Решение
Шаг 3 освежил ключ 101, поэтому на шаге 4 вытеснен 102, и get(102) вернул None. В конце в кэше 103 и 101, самый свежий справа. Поиск по хешу, перенос в конец и удаление с начала у OrderedDict идут за O(1), память O(N).
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key in self.data:
self.data.move_to_end(key)
return self.data.get(key)
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
cache = LRUCache(2)
cache.put(101, "Парацетамол 500 мг")
cache.put(102, "Ибупрофен 200 мг")
print(cache.get(101))
cache.put(103, "Цетиризин 10 мг")
print(cache.get(102), cache.get(101), list(cache.data))Парацетамол 500 мг None Парацетамол 500 мг [103, 101]
Что спросят следом
Как сделать такой кэш без
OrderedDict?Что изменится, если кэшем пользуются несколько потоков?
Почему бы не взять
functools.lru_cache?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«
getтолько читает, порядок трогать не нужно»Чтение и есть использование. Без
move_to_endвgetкэш вытеснит самую популярную карточку, как только она окажется первой по времени записи«Удалю самый давний ключ через
popitem()»Без аргумента
popitemуOrderedDictудаляет последний, самый свежий ключ. Передайтеlast=False, чтобы удалить первый«Обычный
dictс Python 3.7 тоже хранит порядок, возьму его»Порядок вставки он хранит, но метода
move_to_endу него нет: перенос пишут какd[key] = d.pop(key), первый ключ берут черезnext(iter(d)). Это работает, и все жеOrderedDictвыражает намерение явно«
putсуществующего ключа просто перезапишет значение»Перезапись должна еще и освежить ключ. Вызывайте
move_to_endпосле записи в обоих случаях, тогда одна ветка кода покрывает и новый, и существующий ключ
Сигналы для интервьюера
Сильный ответ
Уточняет, считать ли емкость в карточках или в байтах, а после решения сам спрашивает, будут ли кэшем пользоваться несколько потоков
Тревожный сигнал
Хранит порядок в обычном списке ключей и удаляет из него через remove, не замечая, что это O(N)
Красный флаг
Предлагает при каждом get пересортировать все ключи по времени обращения и при этом называет такое решение O(1)
Как еще могут спросить
- Как реализовать LRU cache на Python?
- Напишите кэш, который вытесняет давно не используемые элементы
- Какую структуру данных взять для LRU-кэша, чтобы операции шли за O(1)?
- Реализуйте класс
LRUCacheс методамиgetиput











