В чем разница между LRU и LFU

Ответ 1

Рассмотрим постоянный поток запросов кеша с емкостью кэша 3, см. ниже:

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

Если мы просто рассмотрим кеш Наименее недавно использованный (LRU) с реализацией двукратного связывания HashMap + с O (1) временем выселения и временем загрузки O (1), у нас будет следующее элементы кэшируются при обработке запросов кэширования, как указано выше.

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better! 

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

A - 12
B - 2
C - 2
D - 1

Кэш наименее часто используемых (LFU) использует эту информацию, отслеживая, сколько раз запрос кеша использовался в алгоритме выселения.

Ответ 2

LRU - это алгоритм выключения кэша, называемый наименее используемым кешем.

Посмотрите на ресурс

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

Для этого требуется три структуры данных. Один из них представляет собой хеш-таблицу, которая используется для кэширования ключа/значений, поэтому, учитывая ключ, мы можем получить запись кэша в точке O (1). Второй - двойной список для каждой частоты доступа. Максимальная частота ограничена размером кеша, чтобы избежать создания все большего количества записей в списке частот. Если у нас есть кеш максимального размера 4, то мы получим 4 разных частоты. Каждая частота будет иметь двойной связанный список, чтобы отслеживать записи кэша, принадлежащие этой конкретной частоте. Третьей структурой данных было бы как-то связать эти списки частот. Это может быть либо массив, либо другой связанный список, так что при доступе к записи в кэш-память его можно легко продвинуть в следующий список частот за время O (1).

Ответ 3

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