Зачем предпочитать DoubleLinkedList вместо очереди и хэш-карты для разработки наименее недавно используемого (LRU)?
Решаю задачу дизайна Leetcode LRU - Leetcode LRU:
Спроектируйте структуру данных, которая соответствует ограничениям кэша Наименее недавно использованного (LRU) .
Реализуйте класс LRUCache:
LRUCache(int capacity)Инициализируйте кэш LRU с положительным размеромcapacity.int get(int key)Верните значениеkey, еслиkeyсуществует, в противном случае верните -1.void put(int key, int value)Обновите значениеkey, еслиkeyсуществует. В противном случае добавьте паруkey-valueв кеш. Если количество ключей превышаетcapacityв этой операции, удалите ключ, который использовался реже всего.Каждая из функций
getиputдолжна выполняться со средней временной сложностью O(1).
Я разработал его с использованием Queue и HashMap и смог пройти 20 из 22 тестовых случаев. Однако время ожидания остальных тестовых случаев истекло.
При поиске я обнаружил, что двусвязный список — лучший способ его реализовать. Мне любопытно, почему истекает время ожидания очереди и хеш-карты и почему двусвязный список — лучший способ решить эту проблему.
Ниже моя реализация:
class LRUCache {
int capacity=0;
BlockingQueue<Integer> queue;
Map<Integer, Integer> map = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
queue = new ArrayBlockingQueue<Integer>(capacity);
}
public int get(int key) {
if (queue.contains(key)){
queue.remove(key);
queue.add(key);
return map.get(key);
}
else
return -1;
}
public void put(int key, int value) {
if (queue.contains(key)){
queue.remove(key);
queue.add(key);
map.put(key, value);
}
else if (queue.size()<capacity){
queue.add(key);
map.put(key,value);
}
else{
int oldKey = queue.remove();
map.remove(oldKey);
queue.add(key);
map.put(key,value);
}
}
}
Результат такой, как показано ниже:
O(n), насколько я понимаю. как это поможет? @Луи Вассерман
@KarthikGSarode, в задаче по коду особо упоминается, что «каждый из get и put должен выполняться со средней временной сложностью O (1)».
Ответы 1
Вызовы методов queue.remove(key) и queue.contains(key) не имеют временной сложности O(1). См. документацию по ArrayBlockingQueue, в которой упоминается, что эта очередь «...поддерживается массивом», т. е. ей необходимо сканировать массив, чтобы найти заданное значение. Это имеет временную сложность O(𝑛). Это достаточная причина, чтобы не использовать его для этой задачи. Кроме того, операции используют блокировку, чтобы избежать проблем параллелизма, которые делают их еще медленнее. В документации по remove есть:
удалять
public boolean remove(Object o)[...] Удаление внутренних элементов в очередях на основе кольцевых массивов — это по своей сути медленная и разрушительная операция, поэтому ее следует предпринимать только в исключительных обстоятельствах, в идеале только тогда, когда известно, что очередь недоступна для других потоков.
Двусвязный список
Вы упоминаете двусвязные списки: в Java даже есть реализация двусвязного списка, которая сочетается с хэш-картой: LinkedHashMap.
В документации упоминается:
Предусмотрен специальный конструктор для создания связанной хэш-карты, порядок итерации которой соответствует порядку последнего доступа к ее записям: от самого последнего обращения до самого последнего (порядок доступа). Такая карта хорошо подходит для создания кэшей LRU.
И это именно то, что вам здесь нужно. Реализация может быть:
class LRUCache extends LinkedHashMap<Integer, Integer> {
int capacity;
public LRUCache(int capacity) {
// Foresee one more than desired capacity, so no extension is needed
// when we allow a temporary overrun before deleting the eldest entry
super(capacity + 1, 1, true); // true will enable the LRU behavior
this.capacity = capacity;
}
// This method is called internally by put, getOrDefault (and similar).
// See documentation
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> entry) {
return this.size() > this.capacity; // overrun detected: ask for removal
}
public int get(int key) {
return getOrDefault(key, -1);
}
}
спасибо за ответ, и вы кодируйте!! БОГ, я никогда не видел такой короткой реализации. очень блестяще!
Как вы думаете, какова асимптотическая эффективность
queue.remove(key)иqueue.contains(key)?