Pull to refresh

Comments 10

А чем двусвязный список + hash не угодил, зачем хранить время?
Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.
По-моему, стопка листов, в которую новый кладем сверху, а самый старый забираем снизу, понятнее.
Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
Варианты с одной очередью не очень хороши — однократно запрошенные элементы будут вытеснять чуть менее популярные элементы, которые запрашивали много раз. В интернетах встречаются статьи про кэши 2Q, где эта проблема частично решена: хэш-таблица для поиска элементов и 2 очереди. Сначала элемент попадает в нижнюю очередь, а если его запросили второй раз и он всё ещё в кэше — то тогда в верхнюю. Когда верняя очередь заканчиваются — элементы из неё вытесняются в нижнюю, из нижней же элементы вытесняются совсем и удаляются из кэша. Получается константное время поиска записи и её добавления

Кстати, в бусте есть контейнер, который отлично подходят для подобных схем — intrusive list. Ну и ещё intrusive hashmap, чтобы уж совсем минимально с памятью работать.
Спасибо, читал в процессе написания статьи, и решил не грузить. Добавил ссылку для интересующихся.

зачем решение с log(n), когда на листе и хеше элементарно сделать за n?

а что быстрее n или log(n)?

Sign up to leave a comment.

Articles