LRU cache skrót od Least Recently Used Cache. który eksmituje ostatnio używany wpis. Ponieważ celem pamięci podręcznej jest zapewnienie szybkiego i wydajnego sposobu pobierania danych, musi ona spełniać pewne wymagania.
Niektóre z tych wymagań to
- Stały rozmiar: Cache musi mieć pewne granice, aby ograniczyć wykorzystanie pamięci.
- Fast Access: Operacje wstawiania i wyszukiwania w pamięci podręcznej powinny być szybkie, najlepiej w czasie O(1).
- Zastępowanie wpisu w przypadku, gdy limit pamięci został osiągnięty: Cache powinien mieć wydajny algorytm do eksmisji wpisu, gdy pamięć jest pełna.
W przypadku LRU cache eksmitujemy ostatnio używany wpis, więc musimy śledzić ostatnio używane wpisy, wpisy, które nie były używane od dłuższego czasu i które były używane ostatnio. plus operacja lookup i wstawiania powinna być wystarczająco szybka.
Gdy myślimy o O(1) lookup , oczywistą strukturą danych przychodzi nam na myśl jest HashMap. HashMap zapewnia O(1) wstawianie i wyszukiwanie, ale HashMap nie posiada mechanizmu śledzenia, który wpis został ostatnio zapytany, a który nie.
Aby to śledzić potrzebujemy innej struktury danych, która zapewnia szybkie wstawianie, usuwanie i aktualizację, w przypadku LRU używamy podwójnie połączonej listy. Powodem wyboru Podwójnie LinkList jest O(1) usuwanie, aktualizacja i wstawianie jeśli mamy adres węzła na którym ta operacja ma być wykonana.
Więc nasza implementacja LRU cache będzie miała HashMap i Podwójnie LinkList. W którym HashMap będzie trzymać klucze i adresy węzłów Doubly LinkedList . A Doubly LinkedList będzie przechowywać wartości kluczy.
Jako że musimy śledzić ostatnio używane wpisy, użyjemy sprytnego podejścia. Usuniemy element z dołu i dodamy element na początku listy LinkedList i za każdym razem, gdy jakikolwiek wpis jest dostępny, zostanie przeniesiony na górę. tak, że ostatnio używane wpisy będą na górze, a najmniej używane będą na dole.
Zaimplementujmy LRU Cache.
Mam nadzieję, że kod i samouczek są zrozumiałe.