最近使用容量为K的缓存结构
程序员文章站
2022-03-11 16:19:43
...
文章目录
设计可以变更的缓存结构
最近使用容量为K的缓存结构
【题目】 设计一种缓存结构,该结构在构造时确定大小,假设大小为K,并有两个功能:
get(key):返回key对应的value值;
set(key,value):将记录(key,value)插入该结构。
【要求】
- get和set方法的时间复杂度为O(1)。
- 某个key的get和set操作一旦发生,认为这个key的记录成了最经常使用的。
- 当缓存的大小超过K时,移除最不经常使用的记录,即get和set最久远的。
【举例】 假设缓存结构的实例是cache,大小为3,并依次发生如下行为:
- cache.set(“A”,1)。最经常使用的记录为(“A”,1)。
- cache.set(“B”,2)。最经常使用的记录为(“B”,2),(“A”,1)变为最不经常的。
- cache.set(“C”,3)。最经常使用的记录为(“C”,2),(“A”,1)还是最不经常的。
- cache.get(“A”)。最经常使用的记录为(“A”,1),(“B”,2)变为最不经常的。
- cache.set(“D”,4)。大小超过了3,所以移除此时最不经常使用的记录 (“B”,2),加入记录(“D”,4)。
此时(“D”,4)为最经常使用的记录,然后(“C”,2)变为最不经常使用的记录。
算法思路
LRU(Least Recently Used):最近最少使用算法。
一个双端队列存储节点
- 从
head
至tail
为使用顺序。
两个哈希表:keyNodeMap
,nodeKeyMap
,
-
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
有任何疑问和建议,欢迎在评论区留言和指正!
感谢您所花费的时间与精力!
上一篇: 从N个数中等概率打印M个数
下一篇: 2020做什么副业在家就能月入1W?
推荐阅读