欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最近使用容量为K的缓存结构

程序员文章站 2022-03-11 16:19:43
...

设计可以变更的缓存结构

最近使用容量为K的缓存结构

【题目】 设计一种缓存结构,该结构在构造时确定大小,假设大小为K,并有两个功能:
get(key):返回key对应的value值;
set(key,value):将记录(key,value)插入该结构。

【要求】

  1. get和set方法的时间复杂度为O(1)。
  2. 某个key的get和set操作一旦发生,认为这个key的记录成了最经常使用的。
  3. 当缓存的大小超过K时,移除最不经常使用的记录,即get和set最久远的。

【举例】 假设缓存结构的实例是cache,大小为3,并依次发生如下行为:

  1. cache.set(“A”,1)。最经常使用的记录为(“A”,1)。
  2. cache.set(“B”,2)。最经常使用的记录为(“B”,2),(“A”,1)变为最不经常的。
  3. cache.set(“C”,3)。最经常使用的记录为(“C”,2),(“A”,1)还是最不经常的。
  4. cache.get(“A”)。最经常使用的记录为(“A”,1),(“B”,2)变为最不经常的。
  5. cache.set(“D”,4)。大小超过了3,所以移除此时最不经常使用的记录 (“B”,2),加入记录(“D”,4)。
    此时(“D”,4)为最经常使用的记录,然后(“C”,2)变为最不经常使用的记录。

算法思路

LRU(Least Recently Used):最近最少使用算法
一个双端队列存储节点

  • headtail为使用顺序。

两个哈希表keyNodeMapnodeKeyMap

  • keyNodeMap用于增加节点时维护双端队列顺序;

  • nodeKeyMap用于删除节点时维护双端队列顺序(使容量不超过K);

  • nodeKeyMap根据节点获取键值,快速删除keyNodeMap中的节点。

注意:缓存结构需要更新内部节点位置,因此不可以collections模块中deque实现。


相应代码

class Node:
    def __init__(self, value):
        self.value = value
        self.last = None
        self.next = None
# 双端队列
# 注意:缓存结构需要更新内部节点位置,因此不可以用collections模块中deque实现
class NodeDoubleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    # 新增节点至末尾
    def addTail(self, node):
        if self.tail is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            node.last = self.tail
            self.tail = node
    # 移除头节点
    def removeHead(self):
        if self.head is None:
            return
        res = self.head
        if self.head is self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = res.next
            res.next = None
            self.head.last = None
        return res
    # 将已存在的节点移至末尾
    def moveNodeToTail(self, node):
        if node == self.tail:
            return
        # 至少有两个节点,处理前后节点链接
        if node == self.head:
            self.head = self.head.next
            self.head.last = None
        else:
            node.last.next = node.next
            node.next.last = node.last
        # 移至末尾,并标记为tail
        node.last = self.tail
        self.tail.next = node
        self.tail = node

class MyCache:
    def __init__(self, capacity):
        self.keyNodeMap = {}
        self.nodeKeyMap = {}
        self.nodeList = NodeDoubleLinkedList()
        self.capacity = capacity

    def get(self, key):
        if key not in self.keyNodeMap:
            return None
        node = self.keyNodeMap.get(key)
        self.nodeList.moveNodeToTail(node)
        return node

    # 存在则更新,不存在则添加
    def set(self, key, value):
        if key in self.keyNodeMap:
            node = self.keyNodeMap[key]
            node.value = value
            self.nodeList.moveNodeToTail(node)
        else:
            node = Node(value)
            self.keyNodeMap[key] = node
            self.nodeKeyMap[node] = key
            self.nodeList.addTail(node)
            # 超出容量,移除最不经常使用的节点
            if len(self.nodeKeyMap) == self.capacity + 1:
                head = self.nodeList.removeHead()
                key = self.nodeKeyMap[head]
                del self.keyNodeMap[key]
                del self.nodeKeyMap[node]


# 简单测试
if __name__ == '__main__':
    cache = MyCache(3)
    cache.set('A', 1)
    cache.set('B', 2)
    cache.set('C', 3)
    cache.set('D', 4)
    nodeList = cache.nodeList
    cur = nodeList.head
    while cur != None:
        print(cur.value, end=' ')
        cur = cur.next

有任何疑问和建议,欢迎在评论区留言和指正!

感谢您所花费的时间与精力!