Algorytm LFU dla pamięci cache – rozwiązanie w stałym czasie – O(1)

Z nieistniejącego jeszcze cyklu: pytania algorytmiczne oraz struktury danych u gigantów doliny krzemowej: Google, Amazon, Microsoft etc.

Pamięć podręczna cache to pamięć o bardzo szybkim dostępie, której jest bardzo mało. Tworząc procesor twórcy implementują jeden z algorytmów do zarządzania pamięcią, który decyduje, który element z pamięci ma wylecieć, aby utworzyć miejsce dla nowego elementu.

Wikipedia podaje kilkanaście różnych podejść w celu rozwiązania tego problemu. Miedzy innymi jest:

• Usuwanie najdawniej użytego elementu – Least Recently Used (LRU)
• Usuwanie ostatnio użytego elementu – Most Recently Used (MRU)
• i bohater dzisiejszego odcinka – Usuwanie najrzadziej używanego elementu – Least Frequently Used (LFU)

Tych co nie wiedzą czym jest notacja Dużego-O, przypomnienie: O(x) określa jak rozwiązanie problemu w czasie, będzie wzrastać razem z zwiększeniem problemu. O(n) wzrost liniowy (szukanie elementu w tablicy), O(n^2) wzrost kwadratowy (sortowanie bąbelkowe), O(lg n) wzrost logarytmiczny (wyszukiwanie binarne), O(1) czas stały (dostęp do elementu w tablicy).

Jeżeli masz trudność z zdecydowaniem się jaki algorytm lub struktura danych ma jaką złożoność obliczeniową to udaj się na Big O Cheat Sheet.

Algorytmu do obsługi pamięci cache muszą być dwa.

• wstawianie wartości metoda set(key, value): void
• wyciąganie wartości metoda get(key): value

(po dwukropku informacja o wartości zwracanej przez funkcję).

Prostym rozwiązaniem, nie optymalnym jest wykorzystanie dwóch Hash Table, więc .NET’owych Dictionary.

Pierwszy Dictionary przechowuje wartości pod kluczem Dictionary<string, TValue>, drugi Dictionary przechowuje jak często dany klucz jest wykorzystany czyli Dictionary<string, int>.

Metoda get(key) zwiększa licznik użycia dla danego klucza oraz zwraca wartość przechowywaną w pierwszym Dictionary. Obie te operacje są operacjami O(1) więc wyjściowa złożoność get(key) jest równa O(1). Połowa za nami.

Druga metoda set(key, value), musi znaleźć najmniej używany klucz i go w to miejsce podmienić. Niestety operacja szukania najmniej używanego klucza „kosztuje nas” O(n), więc cała metoda kosztuje nas O(n).

Jak zoptymalizować to rozwiązanie? Do czasu O(1)

Im więcej poświęcam czasu na te zadania, to tym częściej widzę, że rozwiązanie zawsze jest przy pomocy:

• Hash Table (czyli Dictionary)
• Double Linked List (lista w której każdy element jest powiązany z poprzednim i następnym )
• Grafy

Użyliśmy Dictionary i uzyskaliśmy O(n). Rozwiązaniem jest użycie Dictionary oraz Double Linked List. Sam na to nie wpadłem. Oto ten artykuł powiedział jak tego dokonać.

Otóż trzeba wykorzystać Double Linked List w .NET tym typem jest LinkedList<T> w celu zarządzania kluczami.

Trzeba utworzyć „poziomą” LinkedList, która będzie automatycznie sortować klucze według częstotliwości ich wykorzystania.

„Pionowe” listy LinkedList są wykorzystane w celu przechowywania kluczy. Używamy LinkedList zamiast tradycyjnej List, ponieważ operacje wstawiania i usuwania w LinkedList są znacznie szybsze niż w List. Szybkość operacji jest „opłacona” większą ilością pamięci operacyjnej, którą tutaj pomijamy.

Implementowałem algorytm największą trudność miałem z za modelowaniem klas-pojemników.

Klasy pojemniki wyglądają tak:

Klasa LFUCache to nasz cache, którego przy tworzeniu ustawiamy wielkość cache ustawiając _cacheSize. _usageList to lista częstotliwości wykorzystania, w niej będziemy sortować klucze. Klucze będą od razu wstawiane w odpowiednie miejsce, nie będzie potrzeby sortowania całej tablicy więc operacja O(1). _data to struktura klucz-wartość, dzięki niej dostęp do elementów jest O(1).

UsageNode klasa będzie przechowywać jedną grupę kluczy o jednakowej stopniu użycia. KeyList to pojemnik na klucze.

KeyNode klasa pojemnik na klucz. ParentUsage to odwołanie do pojedynczego elementu na liście _usageList, trzymamy to odwołanie, aby każdorazowo nie szukać tego elementu i aby utrzymać złożoność O(1).

DataNode jest bardzo podobna do KeyNode. W niej będziemy przechowywać informacje o danej oraz informacje gdzie znajduje się klucz w jakiej KeyList i pośrednio mamy dostęp do odpowiedniego elementu _usageList.

Chyba najtrudniejsze za nami.

Algorytm funkcji void Set(TKey key, TValue value) działa w następujący sposób

1. Jeżeli klucz istnieje w _data to:
   1. usuń go z _data (posiadamy bezpośrednie odwołanie czyli O(1) – skrót BO)
   2. usuń go z odpowiadającej mu KeyList (BO)
   3. jeżeli opróżniło to KeyList
      1. usuń rodzica z _usageList (BO)
2. Jeżeli danych jest więcej niż rozmiar cache
   1. usuń pierwszy element KeyList z pierwszego elementu _usageList. (BO)
   2. kolejne kroki jak przy usuwaniu z _data
3. Jeżeli na liście _usageList nie ma elementów lub pierwszego elementu na liście _usageList Usage nie jest równy 1, to:
   1. Utwórz nowy UsageNode z Usage=1 (O(1))
   2. Dodaj go na pierwszą pozycję (BO)
4. Utwórz KeyNode
5. Dodaj go do pierwszego KeyList w pierwszym elemencie _usageList (O(1))
6. Utwórz odpowiadający wpis w _data, aby móc odwołać się do niego bezpośrednio poprzez klucz (O(1)).

Pierwszy etap za nami, teraz funkcja TValue Get(TKey key). Musi ona nie tylko wyciągnąć odpowiędnią wartość, ale także ułożyć klucze w posortowany sposób.

1. Jeżeli taki klucz nie istnieje w _data, wtedy wyrzuć wyjątek ArgumentException
2. Wyciągnij wartość z _data za pomocą klucza i zapisz tą wartość jako returnValue.
3. Przy użyciu returnValue dostań informacje grupie częstotliwości użycia – usageCurrent.
4. Sprawdz czy następny element po usageCurrent nie istnieje lub następnego elementu wartość Usage nie jest o jeden większa niż usageCurrent.
   • Jeżeli tak:
     1. Utwórz nowy UsageNode i wstaw go po usageCurrent (korzystamy z BO)
     2. Odwołanie do nowego elementu zapisz pod nazwą usageNext
   • Jeżeli nie:
     1. To odpowiedni UsageNode już istnieje
     2. Zapisz następny element po usageCurrent jako usageNext
5. Przesuń KeyNode do którego jest odwołanie poprzez _data z usageCurrent do usageNext (O(1)).
6. Jeżeli wyniku przenosin KeyNode, KeyList został pusty to usuń to UsageNode (czyli usageCurrent) z _usageList (O(1)).
7. Popraw odwołanie ParentUsage na usageNext.
8. Zwróć wartość returnValue.Value

Trochę tego jest 🙂 A od odwołań przechodzących przez kilka obiektów naraz w jednej linijce, aż może się w głowie zakręcić.

Ten problem spotkałem na leetcode. Oznaczone jako Hard. Szczerze miałem parę problemów z prawidłowym wymyśleniem klas-pojemników. W pracy nad tym algorytmie dowiedziałem się o istnieniu LinkedListNode który reprezentuje pojedynczy element na liście LinkedList.

Dzięki temu zadaniu rozumiałem korzyści płynące z połączenia kilku struktur danych, Szybki odczyt dzięki Dictionary oraz umieszczanie nowych elementów w odpowiednim miejscu dzięki LinkedList.

Trzeba pamiętać, że korzyść z strategi LFU będzie największa, gdy elementy najczęściej używane w aplikacji „mają czas” na nabicie licznika „użycia”.

Pełny kod