Привет, дорогой читатель!

Техническое собеседование - это процесс решения интересных алгоритмических задач, которые скорее всего не пригодятся ни тебе, ни твоему интервьюеру в профессиональной карьере, кроме как на следующем техническом собеседовании. И тем не менее такие задачи очень популярны на собеседованиях, потому что позволяют оценить навыки кандидата в поиске ограничений, проследить за его процессом мышления, а также измерить скорость набора циклов for в блокноте. Одним из типов популярных задач являются задачи на реализацию кэша.

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

Обычно интерфейс кэша можно представить в виде следующего набора операций:

1. Добавить элемент по ключу;
2. Получить элемент по ключу;
3. Удалить элемент по ключу;
4. Очистить кэш.

При этом, так как добавлять элементы в кэш бесконечно мы можем только в теории, то кэш должен также описывать стратегию вытеснения элементов. Например, определять элемент, который должен быть удалён при превышении максимального количества элементов.

LRU (least recently used) - стратегия вытеснения элемента, который не использовался дольше всего. Под данным элементом понимается элемент, доступ к которому по ключу (методы добавления и получения значения) не осуществлялся дольше всего.

Полную реализацию LRU кэша на C#, как всегда, можно посмотреть на GitHub проекта coding-interview.

Начнём с реализации самого простого варианта без стратегии вытеснения. Другими словами добавим обёртку вокруг стандартной реализации ассоциативного массива, которая обычно присутствует в стандартной библиотеке твоего любимого языка программирования:

Теперь ограничим наш кэш максимально допустимым количеством элементов capacity. Создадим общий счётчик доступа к элементам totalAccessSteps, который будем увеличивать при каждом последующем доступе. Также будем хранить для каждого сохранённого элемента время доступа к нему accessStepsByKey, необходимое для определения элемента, который не использовался дольше всего. Забегая вперёд отметим, что данная реализация не является оптимальной, в процессе она будет улучшена.

Обновим самые очевидные операции удаления и очистки кэша:

Рассмотрим операцию добавления элемента в кэш. В зависимости от ситуации могут возникнуть три следующих случая:

1. Если данный элемент присутствует в кэше, то обновляем его значение и время доступа;
2. Если кэш содержит меньше элементов, чем его вместимость, то просто сохраняем новый элемент;
3. Если кэш содержит уже максимально допустимое количество элементов, то удаляем элемент, который не использовался дольше всего и сохраняем новый элемент.

Заметим, что обновление значения элемента в данном случае будет эквивалентно удалению элемента и добавлению нового элемента с тем же ключом, так как мы всё равно меняем время доступа. Откуда получаем следующую реализацию добавления элемента:

Операция доступа к элементу по ключу также должна поменять время доступа к элементу, поэтому воспользуемся уже реализованным Update методом:

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

Так как наши операции с кэшем вызываются последовательно, то мы можем упорядочить все наши элементы в виде списка в порядке добавления от более раннего к более позднему (слева записан ключ, а справа - значение):

Посмотрим, как будет изменяться список под воздействием различных операций. Операции очистки кэша и удаления определённого элемента очевидны. Поэтому рассмотрим оставшиеся операции (далее красным цветом будем показывать удаление вершины, а синим - добавление):

• Операция добавления нового элемента, если кэш содержит меньше элементов, чем максимально допустимое значение. В данном случае добавляется новый элемент в конец списка, так как его время добавления будет в любом случае больше, чем время доступа к любому другому элементу:

• Операция добавления нового элемента, если кэш содержит максимально допустимое количество элементов. В данном случае удаляется элемент, который находится в списке первым, так как время доступа к нему меньше, чем время доступа к любому другому элементу. После удаления мы получаем список, в котором количество элементов меньше, чем максимально допустимое. А значит верно то, что описано в пункте выше:

• Операция обновления существующего элемента и операция получения значения по ключу. Оба данных случая эквивалентны удалению элемента и добавлению его в конец списка. Новое значение элемента может быть любым (в примере ниже мы оставили исходное значение), так как не влияет на сортировку элементов:

Осталось научиться быстро находить элемент в списке по ключу. Для этого будем хранить для каждого ключа ссылку на нужный элемент списка:

Перепишем методы очистки и удаления элемента из кэша:

Методы добавления элемента (заметим, что реализация основного метода Add осталась прежней):

И метод получения элемента (реализация метода TryGet практически не поменялась):

Вот и всё, наш кэш готов! Можно смело идти на собеседование, а мне пора прощаться. До скорого!