Кэш актуальных данных
Описание
Кэш актуальных (часто используемых) данных (least recently used (LRU) cache) организует (хранит) элементы таким образом, что мы можем легко определить, какие элементы используются часто, а какие - редко.
Реализация КАД включает в себя:
- конструктор
LRUCache(capacity: number), инициализирующий КАД определенного размера (capacity, положительное целое число) - метод
get(key: string), возвращающий значение по ключу (key) илиnull - метод
set(key: string, value: any), обновляющий или добавляющий значение (value) по ключу (key). При превышенииcapacityиз кэша удаляется (вытесняется) самое старое (наименее используемое) значение
Функции get и set должны выполняться за константное время O(1).
Сложность
Временная
| get | set |
|---|---|
| O(1) | O(1) |
Пространственная
O(n)
Реализация
Двусвязный список и хеш-таблица
В следующей реализации КАД мы будем использовать хеш-таблицу (см. часть 2, раздел 5) для константного (в среднем) доступа к элементам и двойной связный список (см. часть 1, раздел 2) для константного обновления и вытеснения элементов.
Начнем с реализации узла:
// data-structures/lru-cache.js
// Узел
class Node {
constructor(key, val, prev = null, next = null) {
// Ключ
this.key = key
// Значение
this.val = val
// Ссылка на предыдущий узел
this.prev = prev
// Ссылка на следующий узел
this.next = next
}
}
Теперь займемся КАД:
// КАД
export default class LRUCache {
// Конструктор принимает емкость кэша
constructor(capacity) {
// Максимальный размер кэша
this.capacity = capacity
// Кэшированные узлы
this.nodesMap = {}
// Текущий размер кэша
this.size = 0
// Головной узел
this.head = new Node()
// Хвостовой узел
this.tail = new Node()
}
}
Метод получения элемента по ключу:
// Возвращает значение по ключу
get(key) {
const node = this.nodesMap[key]
if (!node) return null
// Обновляем "приоритет" узла
this.promote(node)
return node.val
}
Метод добавления элемента в кэш:
// Добавляет узел в кэш
set(key, val) {
if (this.nodesMap[key]) {
// Обновляем значение существующего узла
const node = this.nodesMap[key]
node.val = val
this.promote(node)
} else {
// Добавляем новый узел
const node = new Node(key, val)
this.append(node)
}
}
Метод обновления приоритета узла:
/**
* Перемещает узел в конец связного списка.
* Это означает, что узел используется наиболее часто.
* Это также снижает вероятность удаления такого узла из кэша
*/
promote(node) {
this.evict(node)
this.append(node)
}
Метод добавления узла в конец связного списка:
// Перемещает узел в конец связного списка
append(node) {
this.nodesMap[node.key] = node
if (!this.head.next) {
// Первый узел
this.head.next = node
this.tail.prev = node
node.prev = this.head
node.next = this.tail
} else {
// Добавляем узел в конец
const oldTail = this.tail.prev
oldTail.next = node
node.prev = oldTail
node.next = this.tail
this.tail.prev = node
}
// Увеличиваем текущий размер кэша
this.size += 1
// Если достигнут максимальный размер кэша,
// то удаляем первый узел
if (this.size > this.capacity) {
this.evict(this.head.next)
}
}
И метод удаления узла:
// Удаляет (вытесняет) узел из кэша
evict(node) {
delete this.nodesMap[node.key]
// Уменьшаем текущий размер кэша
this.size -= 1
const prev = node.prev
const next = node.next
// Имеется только один узел
if (prev === this.head && next === this.tail) {
this.head.next = null
this.tail.prev = null
this.size = 0
return
}
// Это головной узел
if (prev === this.head) {
next.prev = this.head
this.head.next = next
return
}
// Это хвостовой узел
if (next === this.tail) {
prev.next = this.tail
this.tail.prev = prev
return
}
// Это узел в середине списка
prev.next = next
next.prev = prev
}
Полный код КАД вместе с узлом
Тесты
Запускаем тесты:
npm run test ./data-structures/__tests__/lru-cache
Упорядоченная карта
Реализация, в которой используется связный список, полезна в целях обучения, поскольку позволяет понять, как достигается время выполнения O(1) операций get и set.
Однако КАД легче реализовать с помощью объекта Map, который хранит пары "ключ-значение" и запоминает порядок добавления ключей. Мы можем хранить последний используемый элемент в конце карты за счет его удаления и повторного добавления. Элемент, находящийся в начале карты, первым вытесняется из кэша. Для проверки порядка элементов можно использовать IteratorIterable, такой как map.keys().
// data-structure/lru-cache-on-map.js
export default class LruCacheOnMap {
// Конструктор принимает размер кэша
constructor(size) {
// Размер кэша
this.size = size
// Хранилище (по сути, сам кэш)
this.map = new Map()
}
// Возвращает значение по ключу
get(key) {
const val = this.map.get(key)
if (!val) return null
// Обновляем "приоритет" элемента
this.map.delete(key)
this.map.set(key, val)
return val
}
// Добавляет элемент в кэш
set(key, val) {
// Обновляем "приоритет" элемента
this.map.delete(key)
this.map.set(key, val)
// Если кэш переполнен, удаляем первый (самый редко используемый) элемент
if (this.map.size > this.size) {
for (const key of this.map.keys()) {
this.map.delete(key)
break
}
}
}
}
Тесты
Запускаем тесты:
npm run test ./data-structures/__tests__/lru-cache-on-map
