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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |