Jaka jest różnica między LRU i LFU

Question

Jaka jest różnica między LRU i LFU

Jaka jest różnica między LRU A LFU implementacjami pamięci podręcznej?

Wiem, że LRU można zaimplementować za pomocą LinkedHashMap. Ale jak zaimplementować pamięć podręczną LFU?

30

caching lru linkedhashmap

Author: ROMANIA_engineer, 2013-07-20

Source

3 answers

LRU jest algorytmem eksmisji pamięci podręcznej o nazwie najmniej ostatnio używaną pamięć podręczną .

Spójrz na ten zasób

LFU jest algorytmem eksmisji pamięci podręcznej zwanym najmniej często używanym cache .

Wymaga trzech struktur danych. Jedną z nich jest tabela hash, która jest używana do buforowania klucza / wartości tak, że podanym kluczem możemy pobrać wpis bufora w O(1). Druga to podwójnie powiązana lista dla każdej częstotliwości dostępu. Maksymalna częstotliwość wynosi ograniczone do rozmiaru pamięci podręcznej, aby uniknąć tworzenia coraz większej liczby wpisów listy częstotliwości. Jeśli mamy pamięć podręczną o maksymalnym rozmiarze 4, skończymy z 4 różnymi częstotliwościami. Każda częstotliwość będzie miała podwójnie połączoną listę, aby śledzić wpisy pamięci podręcznej należące do danej częstotliwości. Trzecią strukturą danych byłoby jakoś powiązanie tych list częstotliwości. Może to być tablica lub inna powiązana lista, dzięki czemu po uzyskaniu dostępu do wpisu pamięci podręcznej można go łatwo awansować do następnej częstotliwości lista w czasie O (1).

11

Author: NINCOMPOOP,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-07-20 06:53:45

Główna różnica polega na tym, że w LRU sprawdzamy tylko, na której stronie jest ostatnio używana stara w czasie niż inne strony, tzn. sprawdzamy tylko na podstawie ostatnio używanych stron. Ale w LFU sprawdzamy starą stronę, jak również częstotliwość tej strony i jeśli częstotliwość strony jest lager niż stara strona nie możemy go usunąć, a jeśli wszystkie stare strony mają taką samą częstotliwość, to weź ostatnią metodę FIFO. i usunąć stronę....

2

Author: sachin rathod,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-02-27 10:44:45

score 33 · Accepted Answer

Rozważmy stały strumień żądań pamięci podręcznej o pojemności 3, patrz poniżej:

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

Jeśli weźmiemy pod uwagę ostatnio używany bufor (LRU) z implementacją HashMap + podwójnie połączoną listą Z O(1) czasem eksmisji i o(1) czasem ładowania, będziemy mieli następujące elementy buforowane podczas przetwarzania żądań buforowania, jak wspomniano powyżej.

[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!

Patrząc na ten przykład, łatwo widać, że możemy zrobić lepiej-biorąc pod uwagę wyższe oczekiwane szansa na uzyskanie A w przyszłości, nie powinniśmy go eksmitować, nawet jeśli był najmniej ostatnio używany.

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

Least Frequently Used (LFU) cache wykorzystuje te informacje, śledząc, ile razy żądanie cache zostało użyte w algorytmie eksmisji.