Komentarz Michała sprowokował ten wpis, aby porównać dwie implementacje LFU, jedną bazującą na dwóch słownikach (o złożoności obliczeniowej O(n)) oraz opartą na listach dwukierunkowych i słowniku (o złożoności obliczeniowej O(1)).

Zasady benchmarku

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)