最近最少使用的缓存机制,完整实现
共 9532字,需浏览 20分钟
·
2021-06-20 00:24
你好,我是zhenguo
今天结合一道leetcode有意思的题目,设计和实现一个 LRU (最近最少使用) 缓存机制,顺便和读者们加强下双向链表、字典这些数据结构的应用能力。链表增删操作时间复杂度都是O(1),这是它最强的地方,尤其追求卓越性能的算法场景,应用广泛。同时,在面试中也经常会考察到。但是,链表比较容易出错,如果在项目中应用,务必要多多测试。
1 问题
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。
当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
你是否可以在 O(1) 时间复杂度内完成这两种操作?
链接:https://leetcode-cn.com/problems/lru-cache
2 链表
这道题最高效的O(1)实现需要基于链表结构,因此再温习一下链表的基本操作。
链表是一种节点传递结构,所谓的"传递"是靠next变量,以此建立指向下一个节点的关系,可以理解为一条边,仅此而已。
![](https://filescdn.proginn.com/60b8b937cd751ff73256d9e62272dc9c/2c401c1d7f37b94539a0be5fb4da8d20.webp)
如果想令j
节点指向i
节点,需要如何做?如果对链表不熟悉,可能想当然的这么操作:
node_j.next = node_i
上面操作后实现效果如下:
![](https://filescdn.proginn.com/9937bdcada94d0a7df3fed2c6c636cfb/fe85a46dbcd5317929a5286c663d8ea1.webp)
这是不对的,节点i
指向节点j
的边还存在,这不是我们想要的结果!因此,我们需要摘除这条边,那么如何摘除?实际这才是链表的灵活之处,所谓的摘除只不过是一个None赋值操作:
node_i.next = None
上面赋值实现的效果如下:
![](https://filescdn.proginn.com/23f60df98c256ba2090acdf6f24e6342/9a1fae00183e5e7db18c534964a587b4.webp)
你看到吗?剪断后,节点i
和节点j
之间不再有链接关系。所以j
节点指向i
节点的完整代码如下:
node_i.next = None
node_j.next = node_i
![](https://filescdn.proginn.com/7f0d9dcab928ae58c5bf82fe7aa4e37a/beb2f08f47cb28498a3b9dd137022794.webp)
3 实现思路
下面我们再回头问题,要想在O(1)时间复杂度内求解,需要借助字典和双向链表,问题涉及的主要操作包括:
(1). put操作 加入键值对分两种情况讨论:
(1).1 键不存在 (1).2 键存在
(2).get操作,get操作除了具备dict.get的功能外,此处需要定制一个新的功能,即最近使用的节点需要移动到热点区域。而我们知道链表的增删时间复杂度都是O(1),所以根据这个定制化需求,使用链表是再自然不过的了!
4 完整代码
class Node(object):
"""
定义双向链表
"""
def __init__(self, val, pre, next):
self.val = val
self.pre = pre
self.next = next
LRUCache缓存类:
class LRUCache:
def __init__(self, capacity: int):
self.cache_dict = {}
self.linked_dict = {}
self.capacity = capacity
self.head, self.tail = None, None
put
操作对应代码,主要解决三种情况,这和题目是完整一一对应的,分别为:
如果关键字已经存在,则变更其数据值 如果关键字不存在,则插入该组「关键字-值」 当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
def put(self, key: int, value: int) -> None:
if key in self.cache_dict: # 如果关键字已经存在,则变更其数据值
self.cache_dict[key] = value
self._move_to_tail(key)
elif len(self.cache_dict) < self.capacity: # 如果关键字不存在,则插入该组「关键字-值」
self.cache_dict[key] = value
self.linked_dict[key] = Node(key, None, None)
if not self.head:
self.head = self.linked_dict[key]
if self.tail:
self.tail.next = self.linked_dict[key]
tmp = self.tail
self.tail = self.linked_dict[key]
if tmp:
self.linked_dict[key].pre = tmp
tmp.next = self.linked_dict[key]
else: # 当缓存容量达到上限时,
# 它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
self.cache_dict[key] = value
self.linked_dict[key] = Node(key, None, None)
del_key = self.head.val
self.cache_dict.pop(del_key)
pre, next = self.linked_dict[del_key].pre, self.linked_dict[del_key].next
if not pre and not next: # 删除节点无头无尾
self.head = self.linked_dict[key]
elif not pre: # 删除元素是头节点
next.pre = None
self.head = next
elif not next: # 删除元素是尾节点
pre.next = None
self.tail = pre
else:
pre.next = next
next.pre = pre
# 然后在尾部连接上key节点
self.tail.next = self.linked_dict[key]
self.linked_dict[key].pre = self.tail
self.linked_dict[key].next = None
self.tail = self.linked_dict[key]
# 最后再从linked_dict中移除key
self.linked_dict.pop(del_key)
get
操作,
def get(self, key: int) -> int:
if key in self.linked_dict and self.tail != self.linked_dict[key]:
self._move_to_tail(key)
return self.cache_dict.get(key, -1)
简单重构一下,抽离出一个移动节点i
到tail处的方法_move_to_tail
:
def _move_to_tail(self, key):
"""
移动key节点到tail
:param key:
:return:
"""
pre, next = self.linked_dict[key].pre, self.linked_dict[key].next
# 从链表中隔断key节点
if pre and next:
pre.next = next
next.pre = pre
elif next:
next.pre = None
self.head = next
# 如果key节点不在尾部,则移动key节点到尾部
if self.tail != self.linked_dict[key]:
self.linked_dict[key].pre = self.tail
tmp = self.tail
self.tail = self.linked_dict[key]
if tmp:
tmp.next = self.tail
self.linked_dict[key].next = None
5 后记
链表操作比较容易出错,平时需要多加练习,才能在实际项目和面试中,使用得心应手。
其实链表的应用极为广泛,包括我们熟知的版本管理软件git
,里面的多分支和某个分支的管理,都是基于链表操作的。牢固的掌握链表才算是深度掌握算法和数据结构的第一步。