Python · задача 8 из 10

LRU-кэш своими руками

Продвинутый 20–25 минут OrderedDictсложность операцийвытеснение

Условие

Реализуйте кэш с ограниченным размером и вытеснением наименее недавно использованного элемента. Нужны операции get и put, обе — за O(1).

Что требуется

get возвращает значение и делает элемент «свежим»
put при переполнении выбрасывает самый давно не используемый элемент
Обе операции — константное время

Пример

cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")        # 1 -> теперь "a" свежее, чем "b"
cache.put("c", 3)     # вытеснится "b"
cache.get("b")        # None

Сначала уточните

Вопросы до кода — половина оценки. Молча начать печатать хуже, чем задать два вопроса.

Что возвращать при промахе: None, исключение или значение по умолчанию?
Нужна ли потокобезопасность — будут ли обращаться из нескольких потоков?
Нужен ли TTL или ограничение только по размеру?

Показать решение Скрыть решение

Решение

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self._data = OrderedDict()

    def get(self, key, default=None):
        if key not in self._data:
            return default

        self._data.move_to_end(key)          # обращение делает элемент свежим
        return self._data[key]

    def put(self, key, value):
        if key in self._data:
            self._data.move_to_end(key)

        self._data[key] = value

        if len(self._data) > self.capacity:
            self._data.popitem(last=False)   # выбрасываем самый старый


# В проде для функций это одна строка:
# @functools.lru_cache(maxsize=128)

Почему так

Почему OrderedDict, а не dict

Нужен не просто порядок, а дешёвое перемещение элемента в конец: move_to_end — O(1)
Обычный dict с 3.7 хранит порядок вставки, но «освежить» ключ можно только через del и повторную вставку
popitem(last=False) достаёт самый старый элемент с начала — тоже O(1)

Что внутри и почему это O(1)

OrderedDict — это хеш-таблица плюс двусвязный список: словарь даёт доступ по ключу, список — порядок
Перемещение в конец меняет несколько ссылок и не зависит от размера кэша
Если попросят без OrderedDict — именно эту связку dict + двусвязный список и нужно написать руками

Почему проверка «больше capacity» после вставки

Сначала вставляем, потом при необходимости убираем один — так не нужно разбирать случай «ключ уже есть»
Вытеснить до вставки было бы ошибкой: обновление существующего ключа выбросило бы чужой элемент зря
Размер за раз может превысить предел только на единицу, поэтому одного popitem достаточно

Что спросят дальше

Спросят про потоки: OrderedDict не потокобезопасен, нужен Lock — и тогда O(1) остаётся, но появляется конкуренция
Спросят про TTL: хранить время записи рядом со значением и проверять при чтении; чистка «мусора» — отдельный вопрос
Спросят про functools.lru_cache: он именно для функций, ключ — аргументы, и они должны быть хешируемыми

Следующая задача

Разобрать лог и собрать статистику — Задача про файлы: проверяют потоковую обработку и то, не прочитаете ли вы гигабайт целиком.

Перейти