LFU

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

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

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

Кэш LFU хранит не только информацию, но и счетчик — отдельную переменную, в которой содержится частота обращений к элементу. При каждом обращении счетчик увеличивается на единицу. Если место в кэше заканчивается, из него вытесняется элемент с самым низким значением. А если элементов несколько, вытеснение происходит по принципу FIFO (first in, first out) — удаляется самый старший.

Особенности алгоритма

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

Но вместе с информацией приходится хранить счетчик, значение которого постоянно увеличивается. Кэш расходует все больше памяти с каждой итерацией и быстро становится объемным. Элементы могут храниться в кэше очень долго. Их возраст не учитывается. Даже если к данным часто обращались много лет назад, они все равно не будут удалены.

Поэтому в чистом виде LFU используют редко. Обычно алгоритм модифицируют под те или иные задачи.