Pr0grammer Jan 22 2012 at 17:05

LRU, метод вытеснения из кэша

3 min

114K

Website development*

+24

Comments 9

Frozik Jan 22 2012 at 17:11

А чем двусвязный список + hash не угодил, зачем хранить время?

Pr0grammer Jan 22 2012 at 17:15

Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.

Goder Jan 22 2012 at 17:49

По-моему, стопка листов, в которую новый кладем сверху, а самый старый забираем снизу, понятнее.

Pr0grammer Jan 22 2012 at 17:53

Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.

ToSHiC Jan 22 2012 at 18:42

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

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