привет~Уважаемые зрители и господа~ В последнее время я пристрастился к GraphQL и не могу выпутаться.В процессе его использования я столкнулся со многими механизмами кэширования.Алгоритм LRU является одним из наиболее часто используемых, поэтому я заинтересовался этим. Я только что закончил этот ответ, когда раньше чистил LeetCode.Проверив соответствующую информацию и посмотрев на исходную реализацию, я понял, насколько глупым это было раньше ~ Поэтому у меня есть эта статья, чтобы записать идею этого алгоритма.
В этой статье в основном представлен алгоритм кэширования LRU и представлена идея реализации. В дополнение к тому, чтобы дать всем немного больше информации об алгоритме LRU, я надеюсь, что вся идея решения проблемы может помочь вам решить проблему в других подобных сценариях. Ниже приведен текст:
Что такое алгоритм LRU
Алгоритм LRU — это тип алгоритма удаления кеша, а LRU — это сокращение от трех слов, используемых наименее недавно. Проще говоря, потому что Объем памяти ограничен, и менее важные данные необходимо удалять в соответствии с определенной стратегией освобождения памяти. Стратегия LRU состоит в том, чтобы поместить самые ранние обработанные данные в конец, а самые последние обработанные данные - в начало, в соответствии с порядком, обратным времени работы.Если достигнут верхний предел, последний элемент будет исключен.
Весь алгоритм LRU имеет определенную сложность, и его можно расширить, добавив множество функций.Рекомендуется напрямую использовать зрелые библиотеки в производственной среде, такие какlru-cache. Следующий шаг принесет простую реализацию, которая также является скелетом реализации этого алгоритма.
Поскольку это алгоритм, сначала необходимо определить проблему, которую нужно решить.146. Механизм кэширования LRU.
Используя известные вам структуры данных, спроектируйте и внедрите механизм кэширования LRU (наименее использовавшийся ранее). Он должен поддерживать следующие операции: получить данные, получить и записать данные, положить.Получить данные get(key) — Получить значение ключа (всегда положительное число), если ключ (ключ) существует в кеше, иначе вернуть -1. Записать данные put(key, value) — если ключ не существует, записать его значение данных. Когда емкость кэш-памяти достигает верхнего предела, он должен удалить последнее использованное значение данных перед записью новых данных, чтобы освободить место для нового значения данных.
Передовой:
Можете ли вы выполнить обе операции с временной сложностью O(1)?
Конечно, реализация должна быть идеальной, поэтому необходимо реализовать расширенные требования~
Идеи реализации алгоритма LRU
Фактически, алгоритм можно разделить на три аспекта, которые следует учитывать, а именно получение, запись и устранение. Сначала рассмотрим самый простой аспект: приобретение.
Если вам нужно выполнить операцию выборки за время сложности O(1), то хорошим выбором будет хеш-таблица. Реализация JavaScript очень проста, просто используйте объекты, еслиkeyне простой тип, вы можете использоватьMapвыполнить. В сценариях, где алгоритм должен решить проблему, здесь можно использовать объекты:
var LRUCache = function(capacity) {
...
this.map = {};
...
};
Поскольку используется хэш-таблица, получение данных может, естественно, быть O (1).
Самое хлопотное — устранение. Хотя удаление данных в хеш-таблице имеет постоянную временную сложность, у нас нет возможности узнать, какой элемент удалить. Затем измените сохраненное в хеш-таблицеvalue, из прямого храненияvalueМожно ли вместо этого сохранить объект в дополнение к связанному значению плюс время модификации?
Несмотря на время, устранение произошло в нужное время? Это происходит, когда записываются новые данные, и как только данные необходимо удалить, необходимо просмотреть всю хеш-таблицу, чтобы получить элемент, с которым была произведена операция. Операция выборки больше не является временной сложностью O(1). Так нельзя~
Чистая хэш-таблица не может удовлетворить это требование, поэтому как насчет замены пространства на время?Используйте дополнительные переменные для записи элемента, который использовался раньше, и удаляйте элемент непосредственно, когда его необходимо удалить. Чуть ближе к цели, но все равно мало. Рассмотрим этот сценарий, сначала действуйтеA, а затем оперироватьB, и, наконец, работатьA. Если кого-то нужно устранить, то нужно устранить того, кого нужно устранить.B, тогда как переменная записываетA, не соответствует требованиям.
Затем вместо записи одного элемента используйте массив для записи всех элементов.Каждый раз, когда выполняется определенный элемент данных, этот элемент извлекается из массива, а затемpushв массив. Чуть ближе к цели, но чтобы найти этот элемент, нужно обойти массив, а это O(n).
Хотя указанный выше путь не достигает цели, все же есть преимущества:
- нужно использовать хеш-таблицу;
- Временная сложность удаления данных должна быть O(1), что требует дополнительных структур данных;
- Нам нужна структура данных, которая может выполнять операции вставки и удаления с временной сложностью O(1).
Существует ли такая структура данных? Да, это двусвязный список! Операции вставки и удаления связанного списка имеют временную сложность O(1), но сложнее найти элемент, который равен O(n). Однако наличие хеш-таблицы компенсирует недостатки, а найти элемент очень просто! Просто измените хеш-таблицу и установите сохраненное значение в качестве узла связанного списка.
Реализация алгоритма LRU
Подумайте, этого довольно просто добиться, и весь код вы разместите напрямую:
const LRUCache = function(capacity) {
this.map = {};
this.size = 0;
this.maxSize = capacity;
// 链表的头
this.head = {
prev: null,
next: null
};
// 链表的尾
this.tail = {
prev: this.head,
next: null
};
this.head.next = this.tail;
};
LRUCache.prototype.get = function(key) {
if (this.map[key] !== undefined) {
// 将对应的节点抽出并设为链表的首项并返回对应的值
const node = this.extractNode(this.map[key]);
this.insertNodeToHead(node);
return this.map[key].val;
} else {
return -1;
}
};
LRUCache.prototype.put = function(key, value) {
let node;
if (this.map[key]) {
// 如若该项存在，则抽取出来并设置为对应的值
node = this.extractNode(this.map[key]);
node.val = value;
} else {
// 如该项不存在，那就创造一个新节点
node = {
prev: null,
next: null,
val: value,
key,
};
this.map[key] = node;
this.size++;
}
// 将节点设为链表的首项
this.insertNodeToHead(node);
if (this.size > this.maxSize) {
// 超过限制则删除最后一项
const delNode = this.tail.prev;
const delKey = delNode.key;
this.extractNode(delNode);
this.size--;
delete this.map[delKey];
}
};
// 插入节点到链表首项
LRUCache.prototype.insertNodeToHead = function(node) {
const head = this.head;
const oldFirstNode = this.head.next;
node.prev = head;
head.next = node;
node.next = oldFirstNode;
oldFirstNode.prev = node;
return node;
}
// 从链表中抽取节点
LRUCache.prototype.extractNode = function(node) {
const before = node.prev;
const after = node.next;
before.next = after;
after.prev = before;
node.prev = null;
node.next = null;
return node;
}
Я добавил примечание.В соответствии с приведенными выше идеями, я считаю, что вы должны понимать приведенный выше код ~ Видно, что вся реализация не имеет цикла, поэтому все временную сложность всех операций можно считать O (1).
резюме
Это все для этой статьи! На самом деле существуют и другие методы реализации алгоритма LRU, но этот метод понятен, понятен и имеет высокую эффективность, поэтому выбрана именно эта идея. Приведенный выше код не идеален, например, код, связанный с работой связанного списка, не выделен, а пропущен для простоты понимания и экономии места.
На самом деле алгоритмы и структуры данных редко используются во внешнем интерфейсе, но это не значит, что они бесполезны. В предыдущем решении этой задачи я использовал метод сортировки массивов для решения этой задачи, что довольно неэффективно. Знакомство со структурами данных и сознательное их использование в реальных сценариях значительно улучшит людей в дополнение к решению проблем.
Вышеизложенное является небольшим личным мнением, спасибо всем зрителям за то, что увидели это. Легче сказать, чем сделать, надеюсь, эта статья будет вам полезна~ Спасибо!