github.com/FedoseevAlex/OtusGolangHomeWork/hw04_lru_cache

Домашнее задание №4 «LRU-кэш»

Необходимо реализовать LRU-кэш на основе двусвязного списка.

Задание состоит из двух частей, которые необходимо выполнять последовательно.

1) Реализация двусвязного списка

Список имеет структуру вида

nil <- (prev) front <-> ... <-> elem <-> ... <-> back (next) -> nil

Необходимо реализовать следующий интерфейс List:

• Len() int // длина списка
• Front() *ListItem // первый элемент списка
• Back() *ListItem // последний элемент списка
• PushFront(v interface{}) *ListItem // добавить значение в начало
• PushBack(v interface{}) *ListItem // добавить значение в конец
• Remove(i *ListItem) // удалить элемент
• MoveToFront(i *ListItem) // переместить элемент в начало

Гарантируется, что методы Remove и MoveToFront вызываются от существующих в списке элементов.

Элемент списка ListItem:

• Value interface{} // значение
• Next *ListItem // следующий элемент
• Prev *ListItem // предыдущий элемент

Сложность всех операций должна быть O(1), т.е. не должно быть мест, где осуществляется полный обход списка.

2) Реализация кэша на основе ранее написанного списка

Необходимо реализовать следующий интерфейс Cache:

• Set(key Key, value interface{}) bool // Добавить значение в кэш по ключу.
• Get(key Key) (interface{}, bool) // Получить значение из кэша по ключу.
• Clear() // Очистить кэш.

Структура кэша:

• ёмкость (количество сохраняемых в кэше элементов)
• очередь [последних используемых элементов] на основе двусвязного списка
• словарь, отображающий ключ (строка) на элемент очереди

Элемент кэша хранит в себе ключ, по которому он лежит в словаре, и само значение. Для чего это нужно понятно из алгоритма работы кэша (см. ниже).

Сложность операций Set/Get должна быть O(1), при желании Clear тоже можно сделать О(1).

Алгоритм работы кэша:

• при добавлении элемента:
  • если элемент присутствует в словаре, то обновить его значение и переместить элемент в начало очереди;
  • если элемента нет в словаре, то добавить в словарь и в начало очереди (при этом, если размер очереди больше ёмкости кэша, то необходимо удалить последний элемент из очереди и его значение из словаря);
  • возвращаемое значение - флаг, присутствовал ли элемент в кэше.
• при получении элемента:
  • если элемент присутствует в словаре, то переместить элемент в начало очереди и вернуть его значение и true;
  • если элемента нет в словаре, то вернуть nil и false (работа с кешом похожа на работу с map)

Ожидаются следующие тесты:

• на логику выталкивания элементов из-за размера очереди (например: n = 3, добавили 4 элемента - 1й из кэша вытолкнулся);
• на логику выталкивания давно используемых элементов (например: n = 3, добавили 3 элемента, обратились несколько раз к разным элементам: изменили значение, получили значение и пр. - добавили 4й элемент, из первой тройки вытолкнется тот элемент, что был затронут наиболее давно).

(*) Дополнительное задание: сделать кэш горутино-безопасным.

Критерии оценки

• Пайплайн зелёный - 4 балла
• Добавлены новые юнит-тесты для списка - 1 балл
• Добавлены новые юнит-тесты для кэша (см. выше) - до 3 баллов
• Понятность и чистота кода - до 2 баллов
• Дополнительное задание на баллы не влияет

Зачёт от 7 баллов

Подсказки

• https://en.wikipedia.org/wiki/Doubly_linked_list
• https://ru.bmstu.wiki/LRU_(Least_Recently_Used)
• sync.Mutex