LRU (Least Recently Used) кэш — структура данных, используемая для временного хранения ограниченного набора данных с целью улучшения производительности. При добавлении нового элемента, если кэш полон, он вытесняет наименее недавно использованный элемент.
Принцип работы:
- Каждый раз при доступе к элементу (чтение или запись), этот элемент помечается как "недавно использованный" и перемещается в начало списка или структуры, представляющей порядок использования.
- При переполнении кэша удаляется элемент из "хвоста" — тот, к которому обращались дольше всего.
Реализация часто использует комбинацию словаря (для быстрого доступа по ключу) и двусвязного списка (для поддержания порядка использования).
Пример в Python (functools.lru_cache):
python
Преимущества:
- Ускорение доступа к часто используемым данным.
- Эффективное использование ограниченной памяти кэша.
Недостатки:
- Может быть неэффективен для данных с равномерным или случайным доступом.
- Накладные расходы на поддержание порядка использования.