146. LRU缓存机制 [medium]

146. LRU缓存机制 [medium]

LRU: Least Recently Used, 即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

• 你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

通过次数82,093 | 提交次数164,407

Third Try

2020-07-21

双向链表标准解法

有几个注意要点：

• dict() hashmap里保存的是链表节点，key:node格式，因此可以通过key快速找到node
• 链表需要使用双向链表，这样在通过hashmap找到node之后，能够快速把node的前一个节点和下一个节点进行连接，移除node。
• 链表的节点里面需要保存key和value，而不是只有value。不然在移除最早的元素的时候，通过链表得到节点node，只能得到value值，没法删除hashmap里保存的信息。这里贡献了几次错误提交。
• 双向链表的设计需要额外提供head和tail的dummy node节点，以便在处理prev和next的各种跳转的时候不会出现None节点的情况。写过只用head dummy，tail指向最后一个有效节点的写法，贡献了几次错误提交。
• 双向链表在使用的时候尤其需要注意下一个节点的prev的处理。当前节点的上一个和下一个节点之间的prev和next有好几种情况要考虑，很容易就遗漏了，贡献了几次错误提交。
• 我这里把新节点都放在最后面，每次删除的是head节点。官方题解里则是相反。另外官方提交里把节点操作拆分成几个小函数，看起来清晰了不少。insert head, remove node, remove tail, move head，刚好覆盖。

class LinkedNode(object):
    def __init__(self, key=None, val=None, prev=None, nex=None):
        self.key = key
        self.val = val 
        self.prev = prev 
        self.nex = nex


class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int

        新插入的元素放在链表尾部，即将被删除的放在前面
        更新元素的时候，move to end 
        删除元素的时候，delete first 
        
        没办法只使用一个head dummy 而不使用tail dummy 
        典型的如删除最后一个元素，node.prev.nex = node.nex, node.nex.prev = node.prev 第二

        ["LRUCache","put","get","put","get","get"]
        [[1],[2,1],[2],[3,2],[2],[3]]

        ["LRUCache","put","put","get","put","get","put","get","get","get"]
        [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

        ["LRUCache","put","get","put","get","get"]
        [[1],[2,1],[2],[3,2],[2],[3]]
        """
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.nex = self.tail 
        self.tail.prev = self.head 

        self.cache = dict() 
        self.capacity = capacity
        self.size = 0 

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1 
        self.move_to_end(key)
        return self.cache[key].val 

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # print("pre insert node", key, value, self.helper())

        if key in self.cache:
            self.move_to_end(key)
            self.cache[key].val = value 
        else:
            node = LinkedNode(key, value)
            self.cache[key] = node 
            self.tail.prev.nex = node 
            node.prev = self.tail.prev 
            node.nex = self.tail
            self.tail.prev = node # 又忘了一个
            self.size += 1
        # print("after insert", self.helper())
        
        if self.size > self.capacity:
            # print(key, value, self.helper(), self.cache)
            first_node = self.head.nex 
            # self.cache.pop(first_node.val)  # 傻逼了，这个bug花了好长时间才发现
            self.cache.pop(first_node.key)
            self.head.nex = first_node.nex
            first_node.nex.prev = self.head  # 又忘了一个
            self.size -= 1
            # print("after delete", self.helper())
    
    def move_to_end(self, key):
        node = self.cache[key]
        # 断开中路
        node.prev.nex = node.nex
        node.nex.prev = node.prev # 双向链表多一步

        # 插入末尾
        self.tail.prev.nex = node 
        node.prev = self.tail.prev 
        node.nex = self.tail 
        self.tail.prev = node # tmd又漏了一个

    def helper(self):
        node = self.head 
        rv = [node.val]
        while node.nex:
            rv.append(node.nex.val)
            node = node.nex
        return rv

• 执行用时：256 ms, 在所有 Python3 提交中击败了44.81%的用户
• 内存消耗：22.5 MB, 在所有 Python3 提交中击败了15.38%的用户

• failed 1

只使用一个dummy head节点，tail节点指向最后一个有效元素，结果贡献了几次错误提交，在各种操作的时候需要考虑None的情况。如果是单向链表就没有这个问题，可惜这里面需要考虑prev的连接。

class LinkedNode(object):
    def __init__(self, val=None, prev=None, nex=None):
        self.val = val 
        self.prev = prev 
        self.nex = nex


class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int

        新插入的元素放在链表尾部，即将被删除的放在前面
        更新元素的时候，move to end 
        删除元素的时候，delete first 
        
        没办法只使用一个head dummy 而不使用tail dummy 
        典型的如删除最后一个元素，node.prev.nex = node.nex, node.nex.prev = node.prev 第二
        """
        self.head = LinkedNode()
        self.tail = self.head 
        self.cache = dict() 
        self.capacity = capacity
        self.size = 0 

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1 
        self.move_to_end(key)
        return self.cache[key].val 

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.cache:
            self.move_to_end(key)
            self.cache[key].val = value 
        else:
            node = LinkedNode(value)
            self.cache[key] = node 
            self.tail.nex = node
            node.prev = self.tail # 这一步不习惯双向链表的真的容易遗忘 
            self.tail = node 
            self.size += 1
        
        if self.size > self.capacity:
            print("put", key, value, self.head)
            first_node = self.head.nex 
            self.cache.pop(first_node.val)
            self.head.nex = first_node.nex
            first_node.nex.prev = self.head  # 又忘了一个
            self.size -= 1
    
    def move_to_end(self, key):
        node = self.cache[key]
        node.prev.nex = node.nex
        node.nex.prev = node.prev # 双向链表多一步
        node.nex = None 
        self.tail.nex = node
        node.prev = self.tail # 双向链表多一步
        self.tail = node 

• failed 2

没有在linked node里面放置key，只放了value。并且在移除节点的时候，用的是cache.pop(node.val)，导致出现key error的错误。

class LinkedNode(object):
    def __init__(self, val=None, prev=None, nex=None):
        self.val = val 
        self.prev = prev 
        self.nex = nex


class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int

        新插入的元素放在链表尾部，即将被删除的放在前面
        更新元素的时候，move to end 
        删除元素的时候，delete first 
        
        没办法只使用一个head dummy 而不使用tail dummy 
        典型的如删除最后一个元素，node.prev.nex = node.nex, node.nex.prev = node.prev 第二

        ["LRUCache","put","get","put","get","get"]
        [[1],[2,1],[2],[3,2],[2],[3]]

        ["LRUCache","put","put","get","put","get","put","get","get","get"]
        [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

        ["LRUCache","put","get","put","get","get"]
        [[1],[2,1],[2],[3,2],[2],[3]]
        """
        self.head = LinkedNode()
        self.tail = LinkedNode()
        self.head.nex = self.tail 
        self.tail.prev = self.head 

        self.cache = dict() 
        self.capacity = capacity
        self.size = 0 

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1 
        self.move_to_end(key)
        return self.cache[key].val 

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        print("pre insert node", key, value, self.helper())

        if key in self.cache:
            self.move_to_end(key)
            self.cache[key].val = value 
        else:
            node = LinkedNode(value)
            self.cache[key] = node 
            self.tail.prev.nex = node 
            node.prev = self.tail.prev 
            node.nex = self.tail
            self.tail.prev = node # 又忘了一个
            self.size += 1
        print("after insert", self.helper())
        
        if self.size > self.capacity:
            print(key, value, self.helper(), self.cache)
            first_node = self.head.nex 
            # self.cache.pop(first_node.val)  # 傻逼了，这个bug花了好长时间才发现
            self.head.nex = first_node.nex
            first_node.nex.prev = self.head  # 又忘了一个
            self.size -= 1
            print("after delete", self.helper())
    
    def move_to_end(self, key):
        node = self.cache[key]
        # 断开中路
        node.prev.nex = node.nex
        node.nex.prev = node.prev # 双向链表多一步

        # 插入末尾
        self.tail.prev.nex = node 
        node.prev = self.tail.prev 
        node.nex = self.tail 
        self.tail.prev = node # tmd又漏了一个

    def helper(self):
        node = self.head 
        rv = [node.val]
        while node.nex:
            rv.append(node.nex.val)
            node = node.nex
        return rv

Second Try

2020-07-21

使用列表写法，每次搜索删除和移位，O(n)复杂度。

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.hist = []
        self.cache = dict()
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1
        # 列表的这些操作就是O(n)了
        self.hist.remove(key)
        self.hist.append(key)
        return self.cache[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None

        ["LRUCache","get","put","get","put","put","get","get"]
        [[2],[2],[2,6],[1],[1,5],[1,2],[1],[2]]
        """
        if len(self.hist) == self.capacity:
            if key not in self.cache:
                self.cache.pop(self.hist[0])
                self.hist.pop(0)

        if key not in self.cache:
            self.cache[key] = value 
            self.hist.append(key)
        else:
            self.cache[key] = value 
            self.hist.remove(key)
            self.hist.append(key)
            

• 执行用时：940 ms, 在所有 Python 提交中击败了28.42%的用户
• 内存消耗：21.7 MB, 在所有 Python 提交中击败了100.00%

First Try

2020-07-21

使用OrderedMap数据结构，发现了平时没用过的函数接口move to end和popitem, 并且可以通过last参数控制ordermap是LILO还是LIFO。LRU需要的显然是LILO。

另外move to end是python3才有的接口，python2的话只能通过popitem来绕道实现该功能。

In [22]: o = OrderedDict()

In [23]: o.popitem?
Docstring:
od.popitem() -> (k, v), return and remove a (key, value) pair.
Pairs are returned in LIFO order if last is true or FIFO order if false.
Type:      builtin_function_or_method

In [24]: o.move_to_end?
Docstring:
Move an existing element to the end (or beginning if last==False).

Raises KeyError if the element does not exist.
When last=True, acts like a fast version of self[key]=self.pop(key).
Type:      builtin_function_or_method

In [25]: o?
Type:        OrderedDict
String form: OrderedDict()
Length:      0
File:        ~/.pyenv/versions/3.6.1/envs/flamingo/lib/python3.6/collections/__init__.py
Docstring:   Dictionary that remembers insertion order

In [26]: OrderedDict?
Init signature: OrderedDict(self, /, *args, **kwargs)
Docstring:      Dictionary that remembers insertion order
File:           ~/.pyenv/versions/3.6.1/envs/flamingo/lib/python3.6/collections/__init__.py
Type:           type

• collections.orderedmap解法

这里面self.cache.move_to_end(key, last=True)是把元素放到最后面，因为对应的删除元素是self.cache.popitem(last=False)，删除的是最前面的元素。因此把新加入和新刷新的元素放在前面还是后面无关紧要，重要是两个操作一致即可。

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = collections.OrderedDict()
        self.size = 0 
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache:
            return -1 
        self.cache.move_to_end(key, last=True)
        return self.cache[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.cache:
            self.cache.move_to_end(key, last=True)
            self.cache[key] = value 
        else:
            self.cache[key] = value 
            self.size += 1
        if self.size > self.capacity:
            self.cache.popitem(last=False)
            self.size -= 1
            

• 执行用时：216 ms, 在所有 Python3 提交中击败了81.77%的用户
• 内存消耗：21.9 MB, 在所有 Python3 提交中击败了80.77%的用户

• 使用popitem的写法

python2没有move to end，只有pop item，写起来比较绕。后来看官方题解才知道还有move to end这种api.

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity 
        self.cache = collections.OrderedDict()
        self.size = 0 

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        rv = self.cache.get(key, -1)
        if rv != -1:
            self.cache.pop(key)
            self.cache[key] = rv 
        return rv 

        # order dict的insert order竟然是第一次插入的顺序，无法直接通过插入进行更新
        # if key in self.cache:
        #     self.cache[key] = self.cache[key]
            
        # return self.cache.get(key, -1)


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None

        ["LRUCache","get","put","get","put","put","get","get"]
        [[2],[2],[2,6],[1],[1,5],[1,2],[1],[2]]
        """
        if key not in self.cache:
            if self.size == self.capacity:
                self.cache.popitem(last=False)  # FIFO
                self.size -= 1
            self.cache[key] = value 
            self.size += 1
        else:
            # 使用get还是不够，因为有可能相同key，不同value
            # 就算相同key和相同value，也需要对数据操作一遍才行
            # self.get(key)
            self.cache.pop(key)
            self.cache[key] = value 

            
        # 如果插入一个存在的元素，会被提前删除一个不需要删除的元素
        # if self.size == self.capacity:
        #     # last = False 时为 FIFO, last = True时为LIFO
        #     self.cache.popitem(last=False)
        #     self.size -= 1
        # self.cache[key] = value 
        # self.size += 1



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

• 执行用时：724 ms, 在所有 Python 提交中击败了60.74%的用户
• 内存消耗：22.4 MB, 在所有 Python 提交中击败了100.00%的用户