In this repository I implemented LFU-DA (least frequently used with dynamic aging) page replacement policy. And compare this policy with ideal cache replacement policy - Belady's (See the result of this comparision on random tests there).
Linux
cmake -S ./ -B build/ -DCMAKE_BUILD_TYPE=Release
cd build/
make
cd build/
ctest
cd test
./compare.sh
LFU-DA policy similar to the classic LFU except that cache stores his age and the weight of new cache members is set to this age, not to 1 (as in LFU). As in the LFU when needs to insert new element in cache we evict the element with the lowest weight. In other words, LFU-DA combines LFU and LRU policies.
ln(N) on average, worst case N * ln(N), where N - cache capacity.