Categories ProgramowaniePosted on

Benchmark-test algorytmu LFU O(1) vs. O(n)

Paweł SołtysiakLeave a Comment on Benchmark-test algorytmu LFU O(1) vs. O(n)

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

Dla podanych wielkości cache:

  • 2
  • 4
  • 8
  • 16
  • 32
  • 64
  • 128
  • 256
  • 512
  • 1024

Przez 10 sekund dla na cache, będzie wykonywał ten kod w pętli:

var a = Guid.NewGuid().ToString();
var b = Guid.NewGuid().ToString();
var c = Guid.NewGuid().ToString();
var d = Guid.NewGuid().ToString();
var f = Guid.NewGuid().ToString();
cache.Set(a, 1);
cache.Get(a);
cache.Get(a);
cache.Set(b, 2);
cache.Get(b);
cache.Get(b);
cache.Get(b);
cache.Get(b);
cache.Get(b);
cache.Set(c, 3);
cache.Get(c);
cache.Set(d, 3);
cache.Set(f, 13);

I liczyli ile razy ten kod się zdąży się uruchomić.

Wykorzystanie GUID, „gwarantuje”, że klucze będą unikalne.

Cały eksperyment będzie powtórzony dla każdej implementacji cache 3 razy.

Szczegóły: program konsolowy skompilowany w konfiguracji Release, uruchomiony przez CMD z przekierowaniem strumienia do pliku data.csv.

Wyniki

Jest lepiej niż sądziłem. Nawet dla małych rozmiaru cache rozwiązanie O(1) wygrywa nad O(n).

asd
o_n

Użyto skalę logarytmiczną

Twarde dane

time (sec) O(1) O(n) cache size
10 2394798 1934221 2
10 2324175 1859219 2
10 2405498 1919813 2
10 2410710 1849000 4
10 2301162 1772488 4
10 2433414 1842393 4
10 2386576 1630816 8
10 2348449 1628417 8
10 2462402 1672966 8
10 2404047 1345278 16
10 2353876 1329586 16
10 2431250 1341373 16
10 2420747 894717 32
10 2358605 865093 32
10 2418806 889447 32
10 2427581 531775 64
10 2334997 512050 64
10 2342602 522192 64
10 2356430 274580 128
10 2360209 263632 128
10 2337475 270064 128
10 2417599 130473 256
10 2326709 128140 256
10 2419051 131246 256
10 2306131 60029 512
10 2326624 60835 512
10 2367971 60998 512
10 2322806 28985 1024
10 2297528 27721 1024
10 2345859 28339 1024

Kod prostej implementacji na dwa słowniki

Wnioski

Przegrana LFU o złożoności O(n) jest spowodowana przez tą linijkę:

var keyToRemove = _usage.OrderBy(x => x.Value).FirstOrDefault();

Jedyną, która wykonuje, coś co jest liniowo zależne od wielkości cache.

Matematyka nie kłamie, algorytm O(1), działa lepiej i do tego nie ponosi „kary” za zwiększenie wielkości problemu.