1. 什么是LRU Cache
LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。
什么是Cache?
狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
而Cache的容量有限,那如果cache满了怎么办?
当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。
那应该选取那一部分的内容和新内容进行替换呢?这就涉及到cache的替换算法,而LRU Cache就是cache替换算法中的一种!
LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
2. LRU Cache的实现
那要实现一个LRU Cache其实并不难,方法和思路有很多;但是想要实现一个高效(所有操作都是O(1)
)的LRU Cache是有难度的
实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和哈希表的搭配是最高效和经典的。
使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)。
那具体到底应该应该怎么做呢?
下面我们借助LeetCode上的一道OJ来给大家进行一个详细的讲解。
3. LRU Cache的OJ
题目链接: link
我们来看一下题目:
大家可以自己先看一下题目,我们看到题目中要求函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
那我们来分析一下要如何实现
题目分析
题目要求我们实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
这个 LRUCache 类的要求是这样的:
那我们要如何实现呢?
其实分析完题目我们很容易能想到用哈希表,那当然C++里面我们就用unordered_map去搞,那这样的话get函数(其实就是查找嘛)就能达到O(1);然后put呢,put也是要查找嘛,找到就更新,找不到就插入。那这样就也是O(1)。
但是呢我们真正还要考虑还有——如果插入操作导致关键字数量超过 capacity ,我们此时就要进行LRU替换,则应该 逐出 最久未使用的关键字。
那我们要如何实现LRU的替换呢?满的话应该逐出谁啊?如何找到最久未被使用的那个呢?
🆗,那上面也提到了,使用双向链表和哈希表的搭配是最高效和经典的:
我们再搞一个list(list底层就是带头双向循环链表),让它里面也存储数据(相当于数据存储两份),然后我们可以默认认为尾部的那个元素就是最近最少用(最久未被使用)的(按头部实现也可)。
然后如果有新插入的元素或者被访问(get一个已有的值)的元素我就把它移到链表头部。
这样我们需要替换的时候,那么链表尾部的那个就是最久未被使用的那个。
但是呢?
如果我们就这样设计的话,还存在一个问题。
就是更新的时候其实复杂度是O(N)。
为什么呢?
更新的情况就是调用put先在哈希表里面查找到key是已存在的,那然后我们要修改,哈希表里面我找到这个就可以直接修改。
但是,在list里面我们是不是也要修改啊,因为我们替换的时候找最久未被使用的那个值就是要从list里面找呢。
但是要修改list的话我们知不知道当前要修改的这个元素是list里面的哪一个元素?
是不知道的,所以还得遍历list去找。找到之后更新一下,然后把它移到头部去,更新顺序。
那这里遍历查找的话不就是O(N)了嘛。
那这个问题我们如何解决一下呢?
如何做到在哈希表里面找到这个key之后,就直接能获取到他在list中的位置,而不需要去遍历查找呢?
那这里有一个非常巧的设计是这样来解决的:
还是list和unordered_map搭配。
list里面呢还是存key-value的键值对pair。然后哈希表里面key还是要存的,但是不再像上面写的那样直接存key对应的数据value,而是存这个key对应的元素在list里面的对应的迭代器。(那这样真正的数据就只存在list里面)
那这样的话如果更新的话,首先我们在哈希表里面找到key,然后通过它里面存的该元素在list中的迭代器,就可以直接修改list里面存放的数据。
然后再把它放到链表头部(两种方法,后面会提到)。
当然list<pair<int,int>>::iterator
这个类型比较长,我们也可以typedef一下
那下面我们来尝试写一下代码:
AC代码
那首先我们应该还要再增加一个成员变量:
即cache的容量capactity,因为有时候我们还需要判断cache满不满。
然后我们来逐一实现一下它的3个成员函数:
首先是它的构造函数LRUCache:
那这个很简单,就是初始化一下capacity就行了。
剩下两个成员变量是自定义类型,有默认构造。
那然后是get函数:
get呢也很简单,就是通过key判断在不在嘛。
如果在的话,就返回key对应的值;如果不在,返回-1。
那我们就可以直接调用unordered_map的find函数,根据find的返回结果判断,如果找到了,我们要返回什么呢?
🆗,首先这里的ret是啥啊,这里find返回的是迭代器,找到的话返回的就是key对应的这个元素的迭代器。
那我们要返回这个key对应的那个有效的值,那真正的数据是存在list里面的。
我们通过谁可以找到list里面存储的这个key对应的元素呢?
🆗,现在unordered_map里面的value存的是list里面这个key对应元素的迭代器(有点绕了这里😂)。
所以ret->second就是list里面这个元素的迭代器,但是我们想要拿到的是这个元素的key对应的值,即ret->second->second
,这里要取两次second。
🆗,那这样就完了嘛?
还没有。
如果get的时候成功找到了这个数据,那相当于访问了它,那cache里面存储数据的顺序是不是就要调整了。是不是要把这个刚被访问的元素放到链表头部啊。
那如何在list里面调整这个顺序呢?我们上面提到有两种方式:
首先第一种方法我们可以先把这个元素删除掉,然后在头插到头部。
但是这样的话记得还要更新一下unordered_map里面存的对应的那个迭代器,因为删完之后这个迭代器就失效了。之前的文章我们模拟实现过list,我们知道list的迭代器其实就是对结点指针的封装嘛,这个结点删除的话它这个结点指针指向的空间就释放了。
所以这种方法好像有点麻烦。
那我就可以考虑用另外一种——直接调用list的splice
接口转移结点。
那splice 这个函数其实我们之前也有提到过
它可以把一个链表的一部分转移到另一个链表(当然也可以是同一个链表直接进行转移)
所以我们就可以直接调用splice将这个结点转移到list的头部。
那最后就剩下put:
那put的话呢无非就两种操作
如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。
当然插入的时候需要判断:
如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字,然后插入新值。
另外不论是插入还是更新,都应该把插入或更新的值放到链表头部。
那我们来写一下代码:
🆗,那到这里就完事了。
我们来提交一下:
没有问题!
完整代码:文章来源:https://www.toymoban.com/news/detail-804275.html
class LRUCache {
public:
LRUCache(int capacity)
:_capacity(capacity)
{}
int get(int key) {
auto ret=_hashmap.find(key);
if(ret!=_hashmap.end())
{
LtIter it=ret->second;
//将it对应的结点转移到链表头部
_LRUList.splice(_LRUList.begin(),_LRUList,it);
return it->second;
}
return -1;
}
void put(int key, int value) {
auto ret=_hashmap.find(key);
//如果找到,更新值
if(ret!=_hashmap.end())
{
LtIter it=ret->second;
it->second=value;
//将it对应的结点转移到链表头部
_LRUList.splice(_LRUList.begin(),_LRUList,it);
}
else//找不到,插入
{
//如果满了需要先删除最久未使用的值
if(_capacity==_hashmap.size())
{
pair<int,int> back=_LRUList.back();
_hashmap.erase(back.first);
_LRUList.pop_back();
}
//插入
_LRUList.push_front(make_pair(key,value));
_hashmap[key]=_LRUList.begin();
}
}
private:
typedef list<pair<int,int>>::iterator LtIter;
//hash做到查找更新/插入是O(1)
unordered_map<int, LtIter> _hashmap;
//LRU 默认链表尾部的是最久未被使用的
list<pair<int, int>> _LRUList;
size_t _capacity;
};
那我们这篇文章就到这里…文章来源地址https://www.toymoban.com/news/detail-804275.html
到了这里,关于LRU Cache的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!