Principiul de functionare la Least Frequently Used Cache este urmatorul: fiecare element din cache pastreaza intr-o variabila numarul de accesari al respectivului element, cand cache-ul depaseste limita maxima se elimina elementul cu numarul minim de accesari, lasand loc unui nou element sa fie adaugat in cache.

Implementare Structura de Date

Este nevoie de o structura de date care sa pastreze elementele din cache sortate dupa numarul de accesari, astfel operatia de eliminare a elementului cu numarul minim de accesari sa ruleze in O(log n). Implementarea curenta foloseste un SortedList unde cheia este numarul de accesari iar valoarea este o lista intantuita cu elementele din cache care au acelas numar de accesari. SortedList sorteaza listele inlantuite folosind un arbore binar. Aceasta structura de date permite rulare operatilor de adaugare si accesare elemente din cache in complexitate de timp O(log n)

Am creat o interfata generica pe care clasa LFUCache sa o implementeze:

Implementarea clasa LfuCache este sub forma de structura de date generica care implementeaza interfata ICache, permite crearea unui cache care sa stocheze elemente de orice tip, impreuna cu operatiile Add si Get:

Teste Unitare

In scrierea testelor unitare am folosit framework-ul MSTest de la Microsoft, acestea urmeaza pattern-ul Arrange - Act - Assert.
Implementarea testelor unitare:

Teste de Performanta

Pentru testele de performanta am folosit urmatoarea librarie PerformanceDotNet, aceasta masoara timpul de executie si cantitatea de memorie consumata.
Secventa de operatii pe cache de adaugare/accesare este generata aleatoriu intr-un array de operatii de lungime OperationsCount, aceste operatii proceseaza elementele dintr-o lista de dimensiune EelementsCount folosind LFUCache.