Что такое LRU-кэш?

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

Принцип работы:

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

Реализация часто использует комбинацию словаря (для быстрого доступа по ключу) и двусвязного списка (для поддержания порядка использования).

Пример в Python (functools.lru_cache):

# Импорт декоратора
from functools import lru_cache

# Декоратор ограничения кэша до 128 последних вызовов
@lru_cache(maxsize=128)
def fibonacci(n):
  # Рекурсивная функция Фибоначчи с кэшированием
  if n < 2:
    return n
  return fibonacci(n-1) + fibonacci(n-2)

# Вызовы функции
fibonacci(10)

Преимущества:

• Ускорение доступа к часто используемым данным.
• Эффективное использование ограниченной памяти кэша.

Недостатки:

• Может быть неэффективен для данных с равномерным или случайным доступом.
• Накладные расходы на поддержание порядка использования.