Зачем использовать двусвязный список и HashMap для LRU-кэша вместо Deque?

Question

Я реализовал дизайн задачи LRU Cache на LeetCode с использованием обычного метода (Doubly Linked List + Hash Map).Для тех, кто не знаком с проблемой, эта реализация выглядит примерно так:

Я понимаю, почему используется этот метод (быстрое удаление / вставка на обоих концах, быстрый доступ в середине).Я не понимаю, почему кто-то использует HashMap и LinkedList, когда можно просто использовать основанную на массиве деку (в Java ArrayDeque, C ++ просто дек).Этот раздел обеспечивает простоту вставки / удаления на обоих концах и быстрый доступ в середине, что именно то, что вам нужно для кэша LRU.Вы также будете использовать меньше места, потому что вам не нужно будет хранить указатель на каждый узел.

Есть ли причина, по которой кэш LRU разработан почти универсально (по крайней мере, в большинстве учебных пособий), используя последний метод какв отличие от метода Deque / ArrayDeque?Будет ли метод HashMap / LinkedList иметь какие-либо преимущества?

Answer 1

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

Если мы отбрасываем элементы с начала очереди, то, мы должны убедиться, что элемент на передней панели - это тот, который не использовался дольше всего.

Мы гарантируем это, проверяя, что элемент попадает в конец очереди всякий раз, когда он используется .Элемент спереди - это тот, который не перемещался в течение самого длительного времени.

Для этого нам нужно поддерживать очередь при каждой операции put ИЛИ get:

• Когда мы put новый элемент в кэше, он становится наиболее недавно использованным элементом, поэтому мы помещаем его в конец очереди.

• Когда мы get элемент, который уже находится в кеше, он становится наиболее недавно использованным элементом, поэтому мы перемещаем его изтекущая позиция в конце очереди.

Перемещение элементов из середины в конец - , а не - операция deque и не поддерживается ArrayDequeинтерфейс.Он также не поддерживается эффективно базовой структурой данных, используемой ArrayDeque.Списки с двойной связью используются потому, что они do эффективно поддерживают эту операцию.

Answer 2

Целью кэша LRU является поддержка двух операций за O(1) время: get(key) и put(key, value) с дополнительным ограничением на то, что наименее недавно использованные ключи сначала отбрасываются.Обычно ключи являются параметрами вызова функции, а значение является кэшированным выходным сигналом этого вызова.

Независимо от того, как вы подходите к этой проблеме, мы можем согласиться с тем, что вы ДОЛЖНЫ использовать хэш-карту.Чтобы отобразить ключ, уже присутствующий в кеше, в значение O(1).

, необходимо иметь хеш-карту. Для того, чтобы справиться с дополнительным ограничением в отношении того, что ключи, которые использовались не так давно, сначала отбрасываются, вы можете использовать LinkedList или ArrayDeque.,Однако, поскольку нам на самом деле не нужен доступ к середине, LinkedList лучше, так как вам не нужно изменять размер.

Редактировать:

Мистер.Тиммерманс обсуждал в своем ответе, почему ArrayDeques нельзя использовать в LRU cache из-за необходимости перемещения элементов от середины до конца.С учетом сказанного здесь есть реализация LRU cache, которая успешно отправляет в leetcode, используя только добавления и дополнения в deque.Обратите внимание, что Python collections.deque реализован в виде двусвязного списка, однако мы используем только операции в collections.deque, которые также являются O(1) в круговом массиве, поэтому алгоритм остается неизменным независимо.

from collections import deque

class LRUCache:

    def __init__(self, capacity: 'int'):
        self.capacity = capacity
        self.hashmap = {}
        self.deque = deque()

    def get(self, key: 'int') -> 'int':
        res = self.hashmap.get(key, [-1, 0])[0]
        if res != -1:
            self.put(key, res)
        return res

    def put(self, key: 'int', value: 'int') -> 'None':

        self.add(key, value)
        while len(self.hashmap) > self.capacity:
            self.remove()

    def add(self, key, value):
        if key in self.hashmap:
            self.hashmap[key][1] += 1
            self.hashmap[key][0] = value
        else:
            self.hashmap[key] = [value, 1]
        self.deque.append(key)

    def remove(self):
        k = self.deque.popleft()
        self.hashmap[k][1] -=1
        if self.hashmap[k][1] == 0:
            del self.hashmap[k]

Я согласен с г-ном Тиммермансом в том, что использование подхода LinkedList предпочтительнее, но я хочу подчеркнуть, что использование ArrayDeque для построения кэша LRU возможно.

Основная путаница между мной и мистером Тиммермансом заключается в том, как мы интерпретировали способности.Я имел в виду способность кешировать последние N запросов get / put, в то время как мистер Тиммерманс полагал, что это означает кэширование последних N уникальных элементов.

Приведенный выше код имеет цикл в put, который замедляет код - но это просто для того, чтобы код соответствовал кэшированию последних N уникальных элементов.Если бы у нас был кэш кода последних N запросов вместо этого, мы могли бы заменить цикл на:

if len(self.deque) > self.capacity: self.remove()

Это сделает его быстрым, если не быстрее, чем вариант связанного списка.

Независимо от того, как интерпретируется maxsize, вышеуказанный метод по-прежнему работает как кэш LRU - в первую очередь отбрасываются наименее недавно использованные элементы.

Я просто хочу подчеркнуть, что разработка LRUкеш таким способом возможен.Источник прямо здесь - попробуйте отправить его на Leetcode!