LFU-кэш: вытеснение по частоте и реализация за O(1)

Коротко

LFU (Least Frequently Used) выбрасывает элемент, к которому обращались реже всего, в отличие от LRU, который смотрит на давность.

LFU против LRU

Разница в предположении о будущем.

LRU считает: если к данным обращались недавно, обратятся снова. Реагирует на изменения быстро.

LFU считает: если к данным обращались часто, обратятся снова. Лучше держит стабильно популярные элементы.

Показательный пример — последовательное сканирование большой таблицы. LRU вытеснит из кэша всё полезное, потому что новые страницы «свежее». LFU устоит: у популярных страниц счётчик высокий, а у просканированных — по единице.

Обратная ситуация — смена популярности. Элемент, набравший тысячу обращений месяц назад, будет висеть в LFU-кэше вечно, даже если больше не нужен. LRU выкинет его сразу.

Наивная реализация и её проблема

Очевидный подход — хранить счётчик у каждого ключа и при вытеснении искать минимум. Но поиск минимума по всем ключам стоит O(n).

Использовать кучу тоже неудобно: при каждом обращении счётчик меняется, а куча не умеет быстро обновлять приоритет произвольного элемента.

Нужна структура, дающая O(1) на обе операции.

Решение: списки по частотам

Идея в трёх частях:

1. Словарь key → (значение, частота).
2. Словарь частота → двусвязный список ключей с этой частотой.
3. Переменная min_freq — минимальная присутствующая частота.

min_freq = 1

частота 1: [ключ D] ⇄ [ключ C]      ← вытесняем отсюда, с конца
частота 2: [ключ B]
частота 5: [ключ A]

При обращении к ключу мы перемещаем его из списка частоты f в список частоты f+1. Обе операции с двусвязным списком — O(1).

Внутри одной частоты порядок соответствует давности, поэтому при равных частотах вытесняется самый давний — то есть LRU как разрешение ничьих.

Реализация

В Python удобно использовать OrderedDict как двусвязный список с O(1) удалением по ключу.

from collections import defaultdict, OrderedDict


class LFUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.values = {}                        # key -> value
        self.counts = {}                        # key -> частота
        self.buckets = defaultdict(OrderedDict)  # частота -> ключи по порядку
        self.min_freq = 0

    def _touch(self, key) -> None:
        """Переносим ключ на частоту выше."""
        freq = self.counts[key]
        del self.buckets[freq][key]

        if not self.buckets[freq]:
            del self.buckets[freq]
            if self.min_freq == freq:
                self.min_freq += 1      # опустевшая частота была минимальной

        self.counts[key] = freq + 1
        self.buckets[freq + 1][key] = None

    def get(self, key):
        if key not in self.values:
            return -1
        self._touch(key)
        return self.values[key]

    def put(self, key, value) -> None:
        if self.capacity <= 0:
            return

        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return

        if len(self.values) >= self.capacity:
            # вытесняем самый давний из наименее частых
            evicted, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.values[evicted]
            del self.counts[evicted]

        self.values[key] = value
        self.counts[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1               # новый элемент всегда с частотой 1


cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1  → частота ключа 1 стала 2
cache.put(3, 3)        # вытесняем ключ 2 (частота 1)
print(cache.get(2))    # -1
print(cache.get(3))    # 3

Два тонких места

min_freq = 1 при вставке. Новый элемент всегда имеет частоту 1, значит минимум становится единицей. Забыть эту строку — самая частая ошибка: вытеснение начнёт искать в несуществующем списке.

Увеличение min_freq при опустошении списка. Когда мы переносим последний элемент с минимальной частоты выше, минимум сдвигается ровно на единицу. Не на произвольное значение — потому что элемент перешёл именно на freq + 1, и меньше него ничего не осталось.

Проблема застревания и как её решают

Главный практический недостаток LFU — элемент с большим счётчиком остаётся в кэше, даже когда перестал быть нужен. Реальные системы применяют затухание.

Старение счётчиков. Периодически делим все частоты пополам. Старые заслуги обесцениваются, свежие обращения весят больше.

Окно. Считаем частоту не за всё время, а за последний интервал.

TinyLFU — современный подход, используемый в кэше Caffeine для Java. Частоты хранятся приближённо в Count-Min Sketch (это экономит память), к ним применяется затухание, а свежие элементы получают защитное окно. Гибрид W-TinyLFU показывает лучший hit rate, чем чистые LRU и LFU.

Что выбрать на практике

LRU — по умолчанию. Проще, предсказуемее, хорошо работает на большинстве нагрузок.

LFU — когда есть чёткое ядро популярных данных и много разовых запросов: CDN, кэш популярных товаров, справочники.

Гибриды (W-TinyLFU, ARC) — в системах, где hit rate критичен и есть ресурсы на сложную реализацию.

Важно: разница между алгоритмами вытеснения обычно даёт единицы процентов hit rate. Увеличение размера кэша почти всегда даёт больше. Оптимизировать алгоритм стоит, только когда память упёрлась в потолок.

Частые ошибки

Поиск минимальной частоты перебором. Превращает O(1) в O(n) и обесценивает всю конструкцию.

Забытая установка min_freq = 1 при вставке.

Неудаление опустевших списков. Утечка памяти и риск обратиться к пустому списку при вытеснении.

Использование кучи. Обновление приоритета произвольного элемента в куче стоит O(n) на поиск — не подходит.

Игнорирование ничьих. При равных частотах нужен понятный критерий; естественный выбор — LRU внутри частоты.

Что запомнить

• LFU вытесняет наименее часто используемый элемент, LRU — наиболее давний.
• O(1) достигается словарём частот и двусвязными списками ключей внутри каждой частоты.
• При вставке min_freq всегда сбрасывается в 1.
• При опустошении минимального списка min_freq увеличивается ровно на единицу.
• Главная слабость — застревание устаревших популярных элементов; лечится затуханием счётчиков.