кеширование — кеш LRU в переполнении стека
Возможный дубликат:
LRU кеш дизайн
Я получил этот вопрос в интервью по программированию. Не стесняйтесь думать о том, как вы могли бы ответить.
Как бы вы реализовали LRU (наименее недавно обновленный) кеш в C ++? По сути, кэш может содержать до N Предметы. Если новый элемент вставлен, а количество элементов в кэше меньше NПросто вставлено. Но если новый элемент вставлен и количество элементов в кеше уже Nэлемент, который использовался в последнее время, должен быть удален из кэша.
Подумайте, сколько времени потребуется для каждой вашей операции.
Решение
Я хотел бы иметь элемент кэша, который хранит время последнего доступа. Когда к элементу обращаются (вызывается функция-член), тогда элемент времени доступа обновляется. Когда кэш заполнится, элемент с наименьшим временем доступа будет удален.
Другой вариант — иметь элементы кэша в навязчивый список. Когда к чему-то обращаются и его нет в списке, оно попадает в начало списка. Когда кеш заполнен, нижний элемент списка стирается. Больше работы над каждым доступом, но жертву быстрее найти.
Основная идея не в том, чтобы иметь типичные карты и списки для таких задач, они будут фрагментировать вашу память. Мои алгоритмы постоянно хранят кеш в одном месте.
Другие решения
Других решений пока нет …