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
- Jeżeli klucz istnieje w
_data
to:- usuń go z
_data
(posiadamy bezpośrednie odwołanie czyliO(1)
– skrót BO) - usuń go z odpowiadającej mu
KeyList
(BO) - jeżeli opróżniło to
KeyList
- usuń rodzica z
_usageList
(BO)
- usuń rodzica z
- usuń go z
- Jeżeli danych jest więcej niż rozmiar cache
- usuń pierwszy element
KeyList
z pierwszego elementu_usageList
. (BO) - kolejne kroki jak przy usuwaniu z _data
- usuń pierwszy element
- Jeżeli na liście
_usageList
nie ma elementów lub pierwszego elementu na liście_usageList
Usage nie jest równy 1, to:- Utwórz nowy
UsageNode
z Usage=1 (O(1)
) - Dodaj go na pierwszą pozycję (BO)
- Utwórz nowy
- Utwórz KeyNode
- Dodaj go do pierwszego
KeyList
w pierwszym elemencie_usageList
(O(1)
) - 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.
- Jeżeli taki klucz nie istnieje w
_data
, wtedy wyrzuć wyjątekArgumentException
- Wyciągnij wartość z
_data
za pomocą klucza i zapisz tą wartość jakoreturnValue
. - Przy użyciu
returnValue
dostań informacje grupie częstotliwości użycia –usageCurrent
. - 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:
- Utwórz nowy
UsageNode
i wstaw go pousageCurrent
(korzystamy z BO) - Odwołanie do nowego elementu zapisz pod nazwą
usageNext
- Utwórz nowy
- Jeżeli nie:
- To odpowiedni
UsageNode
już istnieje - Zapisz następny element po
usageCurrent
jakousageNext
- To odpowiedni
- Jeżeli tak:
- Przesuń
KeyNode
do którego jest odwołanie poprzez_data
zusageCurrent
dousageNext
(O(1)
). - Jeżeli wyniku przenosin
KeyNode
,KeyList
został pusty to usuń toUsageNode
(czyliusageCurrent
) z_usageList
(O(1)
). - Popraw odwołanie
ParentUsage
nausageNext
. - 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
using System; | |
using System.Collections; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ConsoleApplication3 | |
{ | |
class UsageNode<TKey> | |
{ | |
public int Usage { get; set; } | |
public LinkedList<KeyNode<TKey>> KeyList { get; set; } | |
} | |
class KeyNode<TKey> | |
{ | |
public TKey Key { get; set; } | |
public LinkedListNode<UsageNode<TKey>> ParentUsage { get; set; } | |
} | |
class DataNode<TKey, TValue> | |
{ | |
public TValue Value { get; set; } | |
public LinkedListNode<KeyNode<TKey>> KeyNode { get; set; } | |
} | |
class LFUCache<TKey, TValue> | |
{ | |
private readonly int cacheSize; | |
private readonly Dictionary<TKey, DataNode<TKey, TValue>> _data; | |
private readonly LinkedList<UsageNode<TKey>> _usageList; | |
public int Count => _data.Count; | |
public LFUCache(int cacheSize) | |
{ | |
this.cacheSize = cacheSize; | |
_data = new Dictionary<TKey, DataNode<TKey, TValue>>(this.cacheSize); | |
_usageList = new LinkedList<UsageNode<TKey>>(); | |
} | |
public void Set(TKey key, TValue value) | |
{ | |
if (_data.ContainsKey(key)) | |
{ | |
var node = _data[key].KeyNode.Value; | |
_data.Remove(key); | |
node.ParentUsage.Value.KeyList.Remove(node); | |
if (node.ParentUsage.Value.KeyList.Count == 0) | |
{ | |
_usageList.Remove(node.ParentUsage); | |
} | |
} | |
if (_data.Count >= this.cacheSize) | |
{ | |
//removing a key from usage tree | |
var first = _usageList.First.Value.KeyList.First; | |
_data.Remove(first.Value.Key); | |
_usageList.First.Value.KeyList.Remove(first); | |
if (_usageList.First.Value.KeyList.Count == 0) | |
{ | |
_usageList.Remove(_usageList.First); | |
} | |
} | |
if (_usageList.Count == 0 || _usageList.First.Value.Usage != 1) | |
{ | |
var usageHead = new UsageNode<TKey> | |
{ | |
Usage = 1, | |
KeyList = new LinkedList<KeyNode<TKey>>() | |
}; | |
_usageList.AddFirst(usageHead); | |
} | |
var newKeyNode = new KeyNode<TKey>() | |
{ | |
Key = key, | |
ParentUsage = _usageList.First | |
}; | |
var newUsageNode = _usageList.First.Value.KeyList.AddFirst(newKeyNode); | |
_data.Add(key, new DataNode<TKey, TValue> | |
{ | |
Value = value, | |
KeyNode = newUsageNode | |
}); | |
} | |
public TValue Get(TKey key) | |
{ | |
if (!_data.ContainsKey(key)) | |
{ | |
throw new ArgumentException("No such key"); | |
} | |
var returnValue = _data[key]; | |
var usageCurrent = returnValue.KeyNode.Value.ParentUsage; | |
LinkedListNode<UsageNode<TKey>> usageNext = null; | |
if (usageCurrent.Next == null || (usageCurrent.Next.Value.Usage != usageCurrent.Value.Usage + 1)) | |
{ | |
var usagenode = new UsageNode<TKey>() | |
{ | |
Usage = usageCurrent.Value.Usage + 1, | |
KeyList = new LinkedList<KeyNode<TKey>>() | |
}; | |
usageNext = _usageList.AddAfter(usageCurrent, usagenode); | |
} | |
else | |
{ | |
usageNext = usageCurrent.Next; | |
} | |
returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Remove(returnValue.KeyNode); | |
if (returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Count == 0) | |
{ | |
_usageList.Remove(returnValue.KeyNode.Value.ParentUsage); | |
} | |
usageNext.Value.KeyList.AddFirst(returnValue.KeyNode); | |
returnValue.KeyNode.Value.ParentUsage = usageNext; | |
return returnValue.Value; | |
} | |
public Dictionary<TKey, TValue> ToDictionary() | |
{ | |
return _data.ToDictionary(x => x.Key, x => x.Value.Value); | |
} | |
} | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var cache = new LFUCache<string, int>(2); | |
cache.Set("a", 1); | |
Console.WriteLine(cache.Get("a")); | |
Console.WriteLine(cache.Get("a")); | |
cache.Set("b", 2); | |
cache.Get("b"); | |
cache.Set("c", 3); | |
foreach (var kv in cache.ToDictionary()) | |
{ | |
Console.WriteLine($"K: {kv.Key} V:{kv.Value}"); | |
} | |
Console.WriteLine($"Count {cache.Count}"); | |
Console.ReadKey(true); | |
} | |
} | |
} |