越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/lru-cache/

LRU is a very common cache eviction policy. If we only query each key once (and it’s no longer queried until it is evicted), then the LRU cache is basically a fixed-size FIFO queue, and we can implement that with a circular array or a linked list. Because we do want to move a node to the front of the queue when a key is queried while in cache, we can be certain that we want to use a linked list. Here we choose to use a doubly linked list, because we can delete a node in a doubly linked list with only reference to that node, while in a singly linked list we would need the reference to the previous node as well.

In a linked list, moving a given node to the front only requires $\O(1)$ time, but it takes $\O(n)$ time to find that node with sequential search. In order to realize $\O(1)$ put and get, we need the help from a hash table. We use a dictionary to map keys to their corresponding list nodes, so we can find the node to move in $\O(1)$ time.

Another useful trick is to use two dummy nodes as the head and tail nodes. With them, we can treat the actual head and tail in the same way as other nodes in the middle.

LRU 缓存是非常常用的缓存驱逐策略。如果每个 key 只被使用一次(直到它被驱逐之前不会再被 get 或者 put),那 LRU 缓存就相当于一个固定容量的 FIFO 队列,我们可以想到使用循环数组或者链表来实现。但是每个 key 可能在还在缓存中的时候就被再次使用,因此我们需要把队列中的某一项移到队列头部,所以我们可以确定应该选择使用链表。这里我们采用双向链表,因为在双向链表中移除一个结点只需要该结点的引用就可以实现,而在单向链表中还需要获得其前序结点的引用。

在链表中把一个结点移到头部只需要 $\O(1)$ 的时间,但是要获得该结点的引用则需要 $\O(n)$ 的顺序查找。为了实现 $\O(1)$ 时间的 putget,我们需要 hash table 的帮助。我们使用一个字典将 key 映射到对应的链表结点,这样我们就可以在 $\O(1)$ 时间里找到需要移动到队首的结点。

另外一个小技巧是使用两个 dummy 结点来避免在队首和队尾的特殊情况,即使用两个空结点来使真正的队首和队尾的情况与其他结点相同。

class DLinkedNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict()  # key -> DLinkedNode
        self.head = DLinkedNode(0, 0)
        self.tail = DLinkedNode(0, 0)
        self.head.right = self.tail
        self.tail.left = self.head
    
    def _printLinkedList(self):
        curr = self.head
        r = ""
        while curr:
            if curr == self.head:
                r += "HEAD"
            elif curr == self.tail:
                r += "TAIL"
            else:
                r += "({}, {})".format(curr.key, curr.value)
            curr = curr.right
        print(r)
        
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._deleteNode(node)
            self._addNode(node)
            # self._printLinkedList()
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._deleteNode(self.cache[key])
        newNode = DLinkedNode(key, value)
        self._addNode(newNode)
        self.cache[key] = newNode
        if len(self.cache) > self.capacity:
            toDelete = self.tail.left
            self._deleteNode(toDelete)
            del self.cache[toDelete.key]
        # self._printLinkedList()
    
    def _deleteNode(self, node):
        node.left.right = node.right
        node.right.left = node.left

    def _addNode(self, node):
        oldFirst = self.head.right
        oldFirst.left = node
        node.right = oldFirst
        node.left = self.head
        self.head.right = node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)