Что ж, некоторые люди могут подумать, что я хедлайнер, но я хочу вам сказать, что некоторое время назад интервью действительно касалось разработки алгоритма кэширования RLU. Когда я делал вопрос, я слишком много думал.Я чувствовал, что проектирование алгоритма кэширования LRU (наименее недавно использовавшегося) будет не таким простым, поэтому я неправильно понял смысл вопроса.,), я написал много кода в одной волне операций, а затем застрял.Я внимательно прочитал вопрос и обнаружил, что должен был неправильно его понять.Это так просто, разработать алгоритм кэширования LRU.
Но в данный момент времени очень мало.Разумно сказать, что если вы действительно знакомы с этим алгоритмом, вы можете написать его за десять минут.Однако, хотя вы понимаете идею алгоритма кэширования LRU и знаете конкретные шаги, вы никогда не писали это вручную, поэтому я очень неквалифицирован, когда пишу его.То есть, это полностью отличается от ощущения, что вы можете написать это идеально с помощью кода, поэтому я хотел бы напомнить вам, что если вы можете, вы должны делать то, что, как вы думаете, вы можете сделать с вашим собственным кодом. Не думайте, что если вы понимаете идею, вам не нужно писать код, вы действительно можете понять ее, написав код самостоятельно.
Сегодня я покажу вам, как реализовать алгоритм кэширования LRU с помощью кода.Если вы столкнетесь с проблемой такого типа в будущем, я гарантирую, что вы справитесь с ней идеально.
Описание темы
Разработайте и внедрите наименее часто используемые (LFU) кэшированные структуры данных. Он должен поддерживать следующие операции: получить и положить.
get(key) — если ключ существует в кеше, получить значение ключа (всегда положительное число), в противном случае вернуть -1.
put(key, value) — если ключ не существует, установите или вставьте значение. Когда кеш достигает своей емкости, он должен, прежде чем вставлять новые элементы, Отмените наименее часто используемые элементы. В этой задаче, когда есть ничья (то есть два или более ключа имеют одинаковую частоту использования), Ключ, который использовался реже всего, будет удален.
Передовой:
Можете ли вы выполнить две операции с временной сложностью O(1)?
Пример:
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
Базовая версия: односвязный список для решения
То, что мы хотим удалить, — это наименее используемый узел.Легкий способ думать об этом — использовать структуру данных, такую как односвязный список, для его хранения. Когда мы выполняем операцию put, возникают следующие ситуации:
1. Если put(key,value) уже есть в связанном списке (судя по ключу), то нам нужно удалить долгосрочные данные в связанном списке, а затем вставить новые данные в заголовок связанного списка . ,
2. Если данные, которые нужно поместить (ключ, значение), не существуют в связанном списке, нам нужно оценить, заполнена ли буферная область, Если она заполнена, удалить узел в конце связанного списка, а затем вставьте новые данные в заголовок связанного списка. Если он не заполнен, вы можете напрямую вставить данные в заголовок связанного списка.
Для операций получения происходит следующее
1. Если данные, которые нужно получить (ключ), существуют в связанном списке, верните значение, удалите узел и вставьте его в заголовок связанного списка после удаления.
2. Если данные, которые нужно получить (ключ), не существуют после связанного списка, просто верните -1 напрямую.
Общая идея такова, не думайте, что это очень просто, если вас попросят написать от руки, вы не обязательно напишете это от руки за десять минут. Конкретный код, чтобы не мешать чтению, я поставил в конце статьи.
Анализ временной и пространственной сложности
Для этого метода оба поставляются и получают необходимость провести связанный список, чтобы найти, существуют ли данные, поэтому сложность времени является O (n). Космическая сложность является O (1).
пространство для времени
В практических приложениях, когда мы хотим прочитать часть данных, мы сначала оцениваем, существуют ли данные в кеше, если да, возвращаем их, а если они не существуют, идем в другие места, чтобы найти данные (например, disk ), сохраните данные в буфере после их нахождения и верните их.
Поэтому в практических приложениях операция размещения обычно сопровождается операцией получения, то есть количество операций получения относительно велико, частота совпадений относительно высока, а количество операций размещения относительно невелико. можно считатьпространство для времениспособ ускорить наши операции получения.
Например, мы можем использовать дополнительный хэш-таблица (например, hashmap) для хранения значения ключа, так что наша операция Get может найти целевой узел в O (1) время и вернуть значение.
Тем не менее, каждый хочет использовать хэш-таблицу, получить операции Get, чтобы быть завершены в течение O (1) времени?
После использования хеш-таблицы, хотя мы можем найти целевой элемент за время O(1), да, нам также нужно удалить элемент и вставить элемент в начало связанного списка.Чтобы удалить элемент, нам нужно найти этого элементапредшественник, а затем поиск предшественника этого элемента требует временной сложности O(n).
Конечным результатом является то, что при использовании хэш-таблицы наихудшая временная сложность по-прежнему составляет O(1), а пространственная сложность также становится O(n).
Двусвязный список + хеш-таблица
Нам удалось найти удаляемый узел за время O(1).Причина, по которой нам приходится тратить время O(n) на удаление, заключается главным образом в том, что время тратится на поиск предшественников узла. решить эту проблему Вопрос, по сути, можем ли мы поставитьЕдиный списокзаменитьдвусвязный список, в этом случае мы можем очень хорошо решить эту проблему, и, перейдя на двусвязный список, вы обнаружите, что работать с ним намного проще, чем с односвязным списком.
Итак, наше окончательное решение:Двусвязный список + хеш-таблица, используя комбинацию этих двух структур данных, наша операция get может быть выполнена за O(1) временной сложности. Поскольку узел, который мы хотим удалить в операции размещения, обычно является хвостовым узлом, мы можем использовать переменную tai для постоянной записи положения хвостового узла. В этом случае наша операция размещения также может быть завершена за O (1). ) время.
Конкретный код выглядит следующим образом:
// 链表节点的定义
class LRUNode{
String key;
Object value;
LRUNode next;
LRUNode pre;
public LRUNode(String key, Object value) {
this.key = key;
this.value = value;
}
}
// LRU
public class LRUCache {
Map<String, LRUNode> map = new HashMap<>();
RLUNode head;
RLUNode tail;
// 缓存最大容量，我们假设最大容量大于 1，
// 当然，小于等于1的话需要多加一些判断另行处理
int capacity;
public RLUCache(int capacity) {
this.capacity = capacity;
}
public void put(String key, Object value) {
if (head == null) {
head = new LRUNode(key, value);
tail = head;
map.put(key, head);
}
LRUNode node = map.get(key);
if (node != null) {
// 更新值
node.value = value;
// 把他从链表删除并且插入到头结点
removeAndInsert(node);
} else {
LRUNode tmp = new LRUNode(key, value);
// 如果会溢出
if (map.size() >= capacity) {
// 先把它从哈希表中删除
map.remove(tail);
// 删除尾部节点
tail = tail.pre;
tail.next = null;
}
map.put(key, tmp);
// 插入
tmp.next = head;
head.pre = tmp;
head = tmp;
}
}
public Object get(String key) {
LRUNode node = map.get(key);
if (node != null) {
// 把这个节点删除并插入到头结点
removeAndInsert(node);
return node.value;
}
return null;
}
private void removeAndInsert(LRUNode node) {
// 特殊情况先判断，例如该节点是头结点或是尾部节点
if (node == head) {
return;
} else if (node == tail) {
tail = node.pre;
tail.next = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 插入到头结点
node.next = head;
node.pre = null;
head.pre = node;
head = node;
}
}
Здесь следует напомнить, что для структуры данных связанного списка головной узел и хвостовой узел являются двумя особыми точками.Если удаляемый узел является головным узлом или хвостовым узлом, нам обычно нужно сначала обработать их.
Вот версия односвязного списка
// 定义链表节点
class RLUNode{
String key;
Object value;
RLUNode next;
public RLUNode(String key, Object value) {
this.key = key;
this.value = value;
}
}
// 把名字写错了，把 LRU写成了RLU
public class RLUCache {
RLUNode head;
int size = 0;// 当前大小
int capacity = 0; // 最大容量
public RLUCache(int capacity) {
this.capacity = capacity;
}
public Object get(String key) {
RLUNode cur = head;
RLUNode pre = head;// 指向要删除节点的前驱
// 找到对应的节点，并把对应的节点放在链表头部
// 先考虑特殊情况
if(head == null)
return null;
if(cur.key.equals(key))
return cur.value;
// 进行查找
cur = cur.next;
while (cur != null) {
if (cur.key.equals(key)) {
break;
}
pre = cur;
cur = cur.next;
}
// 代表没找到了节点
if (cur == null)
return null;
// 进行删除
pre.next = cur.next;
// 删除之后插入头结点
cur.next = head;
head = cur;
return cur.value;
}
public void put(String key, Object value) {
// 如果最大容量是 1，那就没办法了，，，，，
if (capacity == 1) {
head = new RLUNode(key, value);
}
RLUNode cur = head;
RLUNode pre = head;
// 先查看链表是否为空
if (head == null) {
head = new RLUNode(key, value);
return;
}
// 先查看该节点是否存在
// 第一个节点比较特殊，先进行判断
if (head.key.equals(key)) {
head.value = value;
return;
}
cur = cur.next;
while (cur != null) {
if (cur.key.equals(key)) {
break;
}
pre = cur;
cur = cur.next;
}
// 代表要插入的节点的 key 已存在，则进行 value 的更新
// 以及把它放到第一个节点去
if (cur != null) {
cur.value = value;
pre.next = cur.next;
cur.next = head;
head = cur;
} else {
// 先创建一个节点
RLUNode tmp = new RLUNode(key, value);
// 该节点不存在，需要判断插入后会不会溢出
if (size >= capacity) {
// 直接把最后一个节点移除
cur = head;
while (cur.next != null && cur.next.next != null) {
cur = cur.next;
}
cur.next = null;
tmp.next = head;
head = tmp;
}
}
}
}
Если вам нужно время, настоятельно рекомендуется вручную реализовать волну самостоятельно.
Если вы считаете, что этот контент вас очень вдохновляет, пусть больше людей увидят эту статью:
1,как, чтобы больше людей могли увидеть этот контент.
2,Следуй за мной и за колонкой, пусть будут долгосрочные отношения
3. Подпишитесь на официальный аккаунт »трудолюбивый кодер"В основном я пишу статьи по алгоритмам и основам работы с компьютером. В ней более 100 оригинальных статей. Также я делюсь множеством видео, книжных ресурсов и средств разработки. Приветствую ваше внимание и впервые читаю свои статьи.