Что такое LRU cache?

LRU (Least Recently Used) кэш — это популярная стратегия управления кэшем, которая ограничивает количество хранимых элементов. Когда кэш заполняется и нужно добавить новый элемент, удаляется тот, к которому обращались раньше всех остальных. Это основано на предположении, что недавно использованные данные с большей вероятностью понадобятся снова в ближайшем будущем.

Как это работает

Основная идея — поддерживать порядок элементов по времени последнего использования. При каждом обращении (чтении или записи) элемент перемещается в начало списка как "самый недавний". Когда кэш переполняется, элемент с конца списка ("самый старый") удаляется.

Типичная реализация

Для эффективной работы (O(1) на операции) используют комбинацию:

• Хэш-таблица (Map): для быстрого доступа к элементу по ключу.
• Двусвязный список: для поддержания порядка элементов от самого недавнего к самому старому.

Пример кода на Python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Перемещаем ключ в конец (как самый недавний)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Обновляем значение и перемещаем
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Удаляем первый (самый старый) элемент
            self.cache.popitem(last=False)

# Использование
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 1
cache.put(3, 3)      # Вытеснит ключ 2
print(cache.get(2))  # -1 (не найден)

Где применяется

LRU-кэши широко используются в системах, где важно ограничить использование памяти и предсказать, какие данные понадобятся:

• Кэширование веб-страниц и DNS-записей.
• Базы данных (например, InnoDB buffer pool).
• Операционные системы для кэширования страниц памяти.
• Фреймворки (например, в Django для кэширования).

Вывод: LRU-кэш стоит применять, когда нужно эффективно управлять ограниченным кэшем с простой и предсказуемой политикой вытеснения, основанной на времени последнего доступа. Он особенно полезен в сценариях, где доступ к данным имеет временную локальность (недавно использованные данные часто запрашиваются снова).