Структуры данных
LRU Cache: Умное кеширование
Цели урока
- Понять зачем нужен кеш и стратегии вытеснения
- Освоить идею: HashMap + Doubly Linked List
- Реализовать LRU Cache с O(1) операциями
- Узнать про Python lru_cache
Предварительные знания
- Хеш-таблицы
- Связные списки
Каждый браузер, каждая база данных, каждый процессор используют кеш. И на каждом втором собеседовании спрашивают: 'Реализуйте LRU Cache'. Давайте разберём это раз и навсегда!
- Redis - кеширование данных веб-приложений
- CPU L1/L2/L3 cache - кеш памяти процессора
- Browser cache - кеширование страниц и ресурсов
- CDN - кеширование контента ближе к пользователям
Оптимальный алгоритм Белади и LRU как практическое приближение
В 1966 году Ласло Белади, работавший в IBM, изучал замещение страниц для виртуальной памяти и описал оптимальный алгоритм: вытеснять ту страницу, которая дольше всего не понадобится в будущем. Эта политика даёт минимально возможную долю промахов, но требует знания будущего, поэтому напрямую её реализовать нельзя. Белади также обнаружил контринтуитивный результат, известный сегодня как аномалия Белади: при FIFO добавление памяти иногда увеличивает число page faults. Поскольку оптимальный алгоритм на практике невозможен, LRU стал ведущим приближением: вместо предсказания будущего он ставит на то, что недавнее прошлое его предсказывает. Наименее недавно использованный элемент это лучшая ставка на то, что скоро не понадобится. Сегодня LRU работает в кешах процессоров, в вытеснении Redis и в кеше страниц операционной системы, а интервью-версия задачи известна как LeetCode #146.
Зачем нужен кеш?
**Кеш** - быстрое хранилище для часто используемых данных.
- **CPU Cache** - быстрая память рядом с процессором
- **Redis/Memcached** - кеш для веб-приложений
- **CDN** - кеш статики ближе к пользователю
- **Browser Cache** - локально сохранённые ресурсы
**Проблема:** память ограничена. Когда кеш полон, что удалять?
LRU означает:
Идея: Hash + Doubly Linked List
Нужны две операции за O(1):
- **get(key):** получить значение + пометить как 'только что использовано'
- **put(key, val):** добавить/обновить + вытеснить старое если полон
**Решение:** комбинация двух структур!
- **HashMap:** key -> node, для O(1) доступа
- **Doubly Linked List:** порядок использования, O(1) перемещение
Почему нужен Doubly Linked List, а не обычный?
Реализация LRU Cache
При get(key) что происходит с узлом?
Пример работы
Python: `from functools import lru_cache` - встроенный декоратор для мемоизации функций!
LRU-кеш вытесняет элемент, к которому давно не обращались. Значит, 'популярные' элементы никогда не вытесняются
LRU вытесняет давно не использованный элемент - но популярность не защищает от вытеснения при цикличном доступе. Паттерн 'сканирование' (sequential access) вытеснит весь кеш даже для горячих данных
LRU оптимален для временной локальности, но проигрывает при цикличных обращениях к данным, большим по размеру кеша
В примере выше, после put(3,3) какой элемент будет вытеснен следующим?
LRU Cache
- LRU = Least Recently Used (вытесняем давно неиспользованное)
- HashMap: O(1) поиск по ключу
- Doubly Linked List: O(1) добавление/удаление
- get и put за O(1)
- Python: @lru_cache для мемоизации
Вопросы для размышления
- Реализация LRU на HashMap + двусвязный список работает за O(1). Как изменится сложность, если нужна поддержка TTL (time-to-live) для каждого ключа?
Итоги раздела
Освоены ключевые структуры данных! От массивов до LRU Cache - теперь есть инструменты для решения любых алгоритмических задач.
- Хеш-таблицы — Основа быстрого доступа в LRU Cache
Связанные уроки
- ds-06-hash-intro — Хеш-таблица даёт O(1) доступ к элементам кэша по ключу
- ds-02-linked-lists — Двусвязный список хранит порядок недавности за O(1)
- db-26-caching — Кэширующие слои баз данных используют вытеснение в стиле LRU
- os-08-virtual-memory — Вытеснение страниц в ОС использует ту же идею LRU
- sd-07-caching — Кэширование в системном дизайне опирается на политики вроде LRU
- arch-09-cache