1.LRU
2.LFU
什么是LRU?
LRU就是一种缓存淘汰策略。
计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢?
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。
举个简单的例子,安卓手机都可以把软件放到后台运行,比如我先后打开了「设置」「手机管家」「日历」,那么现在他们在后台排列的顺序是这样的:
但是这时候如果我访问了一下「设置」界面,那么「设置」就会被提前到第一个,变成这样:
假设我的手机只允许我同时开 3 个应用程序,现在已经满了。那么如果我新开了一个应用「时钟」,就必须关闭一个应用为「时钟」腾出一个位置,关那个呢?
按照 LRU 的策略,就关最底下的「手机管家」,因为那是最久未使用的,然后把新开的应用放到最上面:
实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和哈希表的搭
配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因
为哈希表的增删查改也是O(1)。
下面我们来看OJ:
对应letecode链接:
剑指 Offer II 031. 最近最少使用缓存 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
运用所掌握的数据结构,设计和实现一个 LRU (Least Recently Used,最近最少使用) 缓存机制 。
实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
示例:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示:
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
进阶:是否可以在 O(1) 时间复杂度内完成这两种操作?
解题思路:
对于 get 操作,首先判断 key 是否存在:
如果 key 不存在,则返回 -1−1;
如果 key 存在,则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。
对于 put 操作,首先判断 key 是否存在:
如果 key 不存在,使用 key 和 value 创建一个新的节点,在双向链表的头部添加该节点,并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;
如果 key 存在,则与 get 操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。
上述各项操作中,访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作,都可以在 O(1) 时间内完成。
在这里博主实现的是泛型的更加的通用。
对应代码:
template<class K, class V>
struct Node
{
Node(const pair<K, V>& kv)
:prev(nullptr)
,next(nullptr)
,_kv(kv)
{
}
pair<K, V>_kv;
Node <K, V>* prev;
Node<K, V>* next;
};
template<class K, class V>
struct NodeDoubList
{
typedef Node<K, V>Node;
NodeDoubList()
:tail(nullptr)
, head(nullptr)
{}
void addNode(Node* newnode) {//增加node
if (newnode == nullptr) {
return;
}
if (head == nullptr) {
head = newnode;
tail = newnode;
}
else {
tail->next = newnode;
newnode->prev = tail;
tail = newnode;
}
}
//一定保证在双向链表中,将链表分离挂到链表里面
void moveNodeTotail(Node* node) {
if (tail == node) {
return;
}
if (head == node) {
head = node->next;
head->prev = nullptr;
}
else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = tail;
node->next = nullptr;
tail->next = node;
tail = node;
}
Node* EraseHead() {
if (head == nullptr) {
return nullptr;
}
Node* res = head;
if (head == tail) {
head = tail = nullptr;
}
else {
head = res->next;
res->next = nullptr;
head->prev = nullptr;
}
return res;
}
Node* tail;//头和尾
Node* head;
};
template<class K, class V>
class MyCache {
typedef Node<K, V>Node;
unordered_map<K, Node*>keyNodeMap;
NodeDoubList<K, V>nodelist;
int capacity;
public:
MyCache(int cap)
:capacity(cap)
{}
V get(K key) {
if (keyNodeMap.count(key)) {
Node* res = keyNodeMap[key];
nodelist.moveNodeTotail(res);
return res->_kv.second;
}
return -1;
}
void set(const pair<K, V>& kv) {
if (keyNodeMap.count(kv.first)) {
Node* node = keyNodeMap[kv.first];
node->_kv = kv;
nodelist.moveNodeTotail(node);
}
else {
Node* newnode = new Node(kv);
keyNodeMap.insert(make_pair(kv.first, newnode));
nodelist.addNode(newnode);
if (keyNodeMap.size() == capacity + 1) {
removeMostUnusedCache();
}
}
}
void removeMostUnusedCache() {
Node* removeNode = nodelist.EraseHead();
keyNodeMap.erase(removeNode->_kv.first);
}
};
class LRUCache {
public:
MyCache<int,int>cache;
LRUCache(int capacity)
:cache(capacity)
{
}
int get(int key) {
int ans=cache.get(key);
return ans;
}
void put(int key, int value) {
cache.set(make_pair(key,value));
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
LFU(least frequently used (LFU) page-replacement algorithm)。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多,但以后就不再使用,这类页将会长时间留在内存中,因此可以将引用计数寄存器定时右移一位,形成指数衰减的平均使用次数。----来自百度
LRU和LFU的区别如下:
LRU -> Recently Used,根据最近一次访问的时间比较
LFU -> Frequently Used,根据key的访问频率比较
对应Letecode链接:
460. LFU 缓存 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。
实现 LFUCache 类:
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近最久未使用 的键。
为了确定最不常使用的键,可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
输入:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释:
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 去除键 2 ,因为 cnt(2)=1 ,使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // 返回 -1(未找到)
lfu.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // 返回 -1(未找到)
lfu.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
提示:
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
最多调用 2 * 105 次 get 和 put 方法。
分析:
缓存的大小都是有限的,当缓存满时有新元素需要添加,就需要一种方式从缓存中删除一些元素,删除的策略就是缓存的淘汰算法。
LFU有个兄弟LRU,他们两都是常用的缓存淘汰算法。
LRU(Least Recently Used) 最近最少使用算法,它是根据时间维度来选择将要淘汰的元素,即删除掉最长时间没被访问的元素。
LFU(Least Frequently Used) 最近最不常用算法,它是根据频率维度来选择将要淘汰的元素,即删除访问频率最低的元素。如果两个元素的访问频率相同,则淘汰最久没被访问的元素。
也就是说LFU淘汰的时候会选择两个维度,先比较频率,选择访问频率最小的元素;如果频率相同,则按时间维度淘汰掉最久远的那个元素。
LRU的实现是一个哈希表加上一个双链表
而LFU则要复杂多了,需要用两个哈希表再加上N个双链表才能实现
我们先看看LFU的两个哈希表里面都存了什么
第一个哈希表是key-value的哈希表(以下简称keyMap哈希表)
通过这张表我们能通过key找到key所在桶中的迭代器
第二张哈希表,频率哈希表,这个就要复杂多了:
这张哈希表中的key是频率,也就是元素被访问的频率(被访问了1次,被访问了两次等等),它的value是一个双向链表。
在这里我们需要一个minFrq记录出现平衡最小的位置。
具体操作:
下面我们来看看具体操作,get操作相对简单一些,我们就先说get操作吧。
get操作的具体逻辑大致是这样:
如果key不存在则返回-1
如果key存在,则返回对应的value,同时:
将元素的访问频率+1
将元素从访问频率i的链表中移除,放到频率i+1的链表中
如果频率i的链表为空,则从频率哈希表中移除这个链表
第一个很简单就不用说了,我们看下第二点的执行过程
假设某个元素的访问频率是3,现在又被访问了一次,那么就需要将这个元素移动到频率4的链表中。如果这个元素被移除后,频率3的那个链表变成空了(只剩下头结点和尾节点)就需要删除这个链表,同时删除对应的频率(也就是删除key=3)
put操作就要复杂多了,大致包括下面几种情况
如果key已经存在,修改对应的value,并将访问频率+1
将元素从访问频率i的链表中移除,放到频率i+1的链表中
如果频率i的链表为空,则从频率哈希表中移除这个链表
如果key不存在
缓存超过最大容量,则先删除访问频率最低的元素,再插入新元素
新元素的访问频率为1,如果频率哈希表中不存在对应的链表需要创建
缓存没有超过最大容量,则插入新元素
新元素的访问频率为1,如果频率哈希表中不存在对应的链表需要创建
我们在代码实现中还需要维护一个minFreq的变量,用来记录LFU缓存中频率最小的元素,在缓存满的时候,可以快速定位到最小频繁的链表,以达到 O(1) 时间复杂度删除一个元素。
具体做法是:
更新/查找的时候,将元素频率+1,之后如果minFreq不在频率哈希表中了,说明频率哈希表中已经没有元素了,那么minFreq需要+1,否则minFreq不变。
插入的时候,这个简单,因为新元素的频率都是1,所以只需要将minFreq改为1即可。
我们重点看下缓存超过最大容量时是怎么处理的
对应代码:
class LFUCache {
class Node{
public:
Node(){}
Node(int k, int v, int freq):
k_(k), v_(v), freq_(freq){}
int k_, v_, freq_ = 1;
};
void addNode(int k, int v, int freq){
freqMap[freq].push_back(Node(k, v, freq));
keyMap[k] = --freqMap[freq].end();
}
void removeNode(int freq,const list<Node>::iterator& it){
keyMap.erase(it->k_);
freqMap[freq].erase(it);
if(freqMap[freq].size() == 0){
freqMap.erase(freq);
if(minFreq_ == freq) ++minFreq_;//这个节点已经被删掉了
}
}
unordered_map<int, list<Node>::iterator> keyMap;//这个key能够找到对应桶里的节点的迭代器
unordered_map<int, list<Node>> freqMap;
int capacity_ = 0;//记录容量
int minFreq_ = 0;//次数最少
public:
LFUCache(int capacity): capacity_(capacity) {}
int get(int key) {
if(capacity_ == 0) return -1;//如果是0就直接返回-1;
auto iter = keyMap.find(key);//先查找是否存在
if(iter == keyMap.end()) return -1;//不存在
list<Node>::iterator it = iter->second;
int ans = it->v_, freq = it->freq_;//次数;
removeNode(freq, it);//将其在对应桶中删掉
addNode(key, ans, freq + 1);//添加新的节点
return ans;
}
void put(int key, int value) {
if(capacity_ == 0) return;
auto iter = keyMap.find(key);
//key not existed
if(iter == keyMap.end()){
if(keyMap.size() == capacity_){
auto it = freqMap[minFreq_].begin();
removeNode(minFreq_, it);
}
addNode(key, value, 1);
minFreq_ = 1;
} else {
//existed, replace
auto it = iter->second;//找到节点所在的迭代器
int v = it->v_, freq = it->freq_;
removeNode(freq, it);//在原节点中删除
addNode(key, value, freq + 1); //插入
}
}
};
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_56999918/article/details/123024530
内容来源于网络,如有侵权,请联系作者删除!