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

Рассмотрим постоянный поток запросов кеша с объемом кеша 3, см. Ниже:

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

Если мы просто рассмотрим кеш Least Recently Used (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) использует эту информацию, отслеживая, сколько раз запрос кэша использовался в его алгоритме удаления.

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

Взгляните на этот ресурс

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

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

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