Wyjaśnienie rozwiązania
Runtime Complexity
get (hashset): O(1) w średnim przypadku, O(n) w najgorszym przypadku
set (hashset): Constant, O(1)
deletion at head when adding a new element (linked list): Stała, O(1)
szukanie przy usuwaniu i dodawaniu do ogona (linked list): O(n)
Kompleksowość: O(n)
Memory Complexity
Linear, O(n) where n is the size of cache.
Solution Breakdown
Caching jest techniką przechowywania danych w szybszej pamięci masowej (zwykle RAM) w celu szybszego obsłużenia przyszłych żądań. Poniżej znajduje się kilka popularnych przykładów użycia pamięci podręcznej:
- Pamięć podręczna procesora jest używana do szybszego odczytu danych z pamięci głównej (RAM).
- Pamięć podręczna w RAM może być używana do przechowywania części danych dyskowych w RAM i obsługi przyszłych żądań szybciej.
- Odpowiedzi sieciowe mogą być buforowane w RAM w celu uniknięcia zbyt wielu wywołań sieciowych.
Jednakże pamięć podręczna zwykle nie jest wystarczająco duża, aby przechowywać pełny zestaw danych. Musimy więc eksmitować dane z pamięci podręcznej, gdy tylko się ona zapełni. Istnieje wiele algorytmów buforowania do implementacji polityki eksmisji z pamięci podręcznej. LRU jest bardzo prostym i powszechnie stosowanym algorytmem. Podstawową koncepcją algorytmu LRU jest usunięcie najstarszych danych z pamięci podręcznej, aby pomieścić więcej danych.
Aby zaimplementować pamięć podręczną LRU używamy dwóch struktur danych: hashmap i podwójnie połączonej listy. Podwójnie połączona lista pomaga w utrzymaniu porządku eksmisji, a haszmapa pomaga w O(1) wyszukiwaniu zbuforowanych kluczy. Oto algorytm dla LRU cache.
If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and ReturnZauważ, że podwójnie połączona lista jest używana do śledzenia ostatnio używanych elementów. Element na ogonie listy podwójnie powiązanej jest ostatnio dostępnym elementem. Wszystkie nowo wstawione elementy (w put) idą na ogon listy. Podobnie, każdy element, do którego uzyskano dostęp (w operacji get), trafia na ogon listy.
