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

caching linkedhashmap lru

39853 просмотра

3 ответа

793 Репутация автора

В чем разница между реализациями LRU и LFU- кэшей?

Я знаю, что LRU можно реализовать используя LinkedHashMap. Но как реализовать кэш LFU?

Автор: Javadroider Источник Размещён: 20.07.2013 06:49

Ответы (3)


13 плюса

41139 Репутация автора

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

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

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

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

Автор: NINCOMPOOP Размещён: 20.07.2013 06:53

3 плюса

31 Репутация автора

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

Автор: sachin rathod Размещён: 27.02.2014 10:44

63 плюса

15936 Репутация автора

Решение

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

Автор: Zorayr Размещён: 24.03.2015 05:26
Вопросы из категории :
32x32