Скопируйте репозиторий. Перейдите в папку с проектом, соберите все 4 таргета
cmake -B build -S . && cmake --build build -j4
Есть несколько таргетов
./build/LFU_tests
./build/Belady_tests
запустят соответствующие программные тесты и выведут результат. Содержание тестов можно увидеть в файле tests/include/tests.hpp.
./build/LFU
./build/Belady
запустят сам кэш. Заполнение в порядке: размер кэша, количество элементов и сами элементы. Будет выведено количество попаданий.
В идеальном кэше заранее известен весь порядок запросов, алгоритм заключается в том, чтобы при кэшмисе вытеснять элемент, который будет использован позже всех.
LFU вытесняются те элементы, которые реже всех попадали в кэш. При попадании увеличивается счетчик, элемент с наименьшим значением счетчика удаляется. При этом значение счетчика обнуляется. То есть если элемент со счетчиком 2 вылетел из кэша, то при возвращении начальным знаяением будет 1.
Выберем контейнеры, которые нужно использовать.
Для идеального кэша нам нужно, чтобы элементы были отсортированы по положению следующего запроса, тогда можно будет быстро найти элемент, от которого нужно избавиться при кэшмисе. Используем упорядоченное множество. При этом нам нужно быстро проверять, есть ли элемент в кэше. То есть хотелось бы находить ячейку по ключу. Значит, нужна хеш-таблица, связывающая ключи-значения и ячейки упорядоченного множества.
Для LFU нужно хранить значения попаданий. Тогда при каждом попадании нужно будет обновлять ячейку, как и было в идеальном. Можно использовать те же контейнеры для этого, изменив условие упорядочивания.