LRU和LFU算法解析
LRU
LRU概念
LRU（The Least Recently Used，最近最少未使用）是一种常见内存管理算法，最早应用于Linux操作系统，在Redis中也有广泛使用的。
LRU算法有这样一种假设：如果某个数据长期不被使用，在未来被用到的几率也不大；因此缓存容量达到上限时，应在写入新数据之前删除最久未使用的数据值，从而为新数据腾出空间。
LRU算法实现
LRU算法描述
需要设计一种数据结构，并且提供以下接口：
- 构造函数，确定初始容量大小
get(key)：如果关键字key存于缓存中，则获取其对应的值；否则返回-1put(key, val)：
- 如果关键字key已经存在，则更改其对应的值为
val；
- 如果关键字不存在，则插入（key,val）
- 当缓存容量达到上限时，最久没有访问的数据应该被置换。
LRU算法图示
我们可以使用双向链表+哈希表来模拟实现LRU算法：
- 哈希表用来快速查找某个key是否存于缓存中
- 链表用来表示使用数据项的时间先后次序
LRU存储图示
LRU_Store
当LRU的容量未到达上限时，对某个数据进行访问（包括添加，读取，修改），则只需要在链表头部插入新节点即可。
当LRU的容量到达上限时，需要添加某个数据，则需要移除链表最末端的键值（最久未使用），然后头插新节点。
容量未满，插入新值003
容量未满，插入新值
容量上限，插入新值004
容量上限，插入新值
访问数据003
访问数据003
LRU C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class LRUCache {
public:
struct Node{
int key;
int val;
Node(int k, int v):key(k), val(v){}
};
using node_iter = list<Node>::iterator;
public:
LRUCache(int capacity) {
this->cap = capacity;
}
int get(int key) {
auto it = mp.find(key);
if(it == mp.end()) return -1;
else{
int val = it->second->val;
l.erase(it->second);
l.push_front(Node(key, val));
mp[key] = l.begin();
return val;
}
}
void put(int key, int value) {
auto it = mp.find(key);
if(it == mp.end()){
if(cap == mp.size()){
mp.erase(l.back().key); l.pop_back();
}else{
}
}else{
l.erase(it->second);
}
l.push_front(Node(key, value));
mp[key] = l.begin();
}
private:
unordered_map<int, node_iter> mp;
list<Node> l;
int cap;
};
|
代码测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main() {
const int capacity = 3;
LRUCache cache(capacity);
cache.put(1, 1);
cache.put(2, 2);
std::cout << cache.get(1) << std::endl;
cache.put(3, 3);
std::cout << cache.get(2) << std::endl;
cache.put(4, 4);
std::cout << cache.get(1) << std::endl;
std::cout << cache.get(3) << std::endl;
std::cout << cache.get(4) << std::endl;
}
|
LFU
LFU概念
LFU（The Least Frequently Used，最不经常使用）也是一种常见的缓存算法。
和LRU类似，LFU同样有这样的假设：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰；当存在两个或者更多个键具有相同的使用频次时，应该淘汰最久未使用的数据。（类比LRU）
LFU算法实现
LFU算法描述
需要设计一种数据结构，并且提供一下接口：
- 构造函数，确定初始缓存容量
get(key) ：如果键存在于缓存中，则获取键的值，否则返回 -1。put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，移除最不经常使用的项。当存在两个或者更多个键具有相同的使用频次时，应该移除最久未使用的键。
LFU算法图示
我们可以使用双哈希表 + 双链表来模拟实现LFU算法：
key_table：用来快速查找某个key是否存于缓存中freq_table：以使用频次为键，存储相同使用频次的节点
LFU存储图示
LFU存储图示
当LFU的容量未到达上限时，对某个数据进行访问（包括添加，读取，修改），其使用频次加一，则只需要在对应链表头部插入新节点即可。
当LFU的容量到达上限时，需要添加某个数据，则需要移除当前使用频次最低的链表最末端的键值（最久未使用），然后在频次为1的链表头插新节点。
容量未满，插入新值005
容量未满，插入新值
访问数据001
访问数据001
容量上限，插入新值006
容量上限，插入新值
LFU C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| class LFUCache {
public:
struct Node {
int key, val, freq;
Node(int _key,int _val,int _freq): key(_key), val(_val), freq(_freq){}
};
public:
LFUCache(int capacity) {
this->cap = capacity;
min_freq = 0;
}
int get(int key) {
if(!cap) return -1;
auto it = key_table.find(key);
if(it == key_table.end()){
return -1;
}else{
auto key_iter = it->second;
Node* node = *key_iter;
int val = node->val, freq = node->freq;
freq_table[freq].erase(key_iter);
if(freq_table[freq].size() == 0){
freq_table.erase(freq);
if(min_freq == freq) min_freq = freq + 1;
}
node->freq += 1;
freq_table[freq + 1].push_front(node);
key_table[key] = freq_table[freq + 1].begin();
return val;
}
}
void put(int key, int value) {
if(!cap) return;
auto it = key_table.find(key);
if(it != key_table.end()){
auto key_iter = it->second;
auto node = *key_iter;
int freq = node->freq;
freq_table[freq].erase(key_iter);
if(freq_table[freq].size() == 0){
freq_table.erase(freq);
if(min_freq == freq)min_freq = freq + 1;
}
node->freq += 1; node->val = value;
freq_table[freq + 1].push_front(node);
key_table[key] = freq_table[freq + 1].begin();
}else{
if(key_table.size() == cap){
Node* del_node = freq_table[min_freq].back();
freq_table[min_freq].pop_back();
if(freq_table[min_freq].size() == 0){
freq_table.erase(min_freq);
}
key_table.erase(del_node->key);
delete del_node;
}
freq_table[1].push_front(new Node(key, value, 1));
key_table[key] = freq_table[1].begin();
min_freq = 1;
}
}
private:
int cap;
int min_freq;
unordered_map<int, list<Node*>::iterator> key_table;
unordered_map<int, list<Node*>> freq_table;
};
|
代码测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main(){
const int capacity = 2;
LFUCache cache(capacity);
cache.put(1, 1);
cache.put(2, 2);
std::cout << cache.get(1) << std::endl;
cache.put(3, 3);
std::cout << cache.get(2) << std::endl;
std::cout << cache.get(3) << std::endl;
cache.put(4, 4);
std::cout << cache.get(1) << std::endl;
std::cout << cache.get(3) << std::endl;
std::cout << cache.get(4) << std::endl;
}
|
总结
LRU和LFU的算法暂时就介绍到这里了，作者水平有限，可能会存在疏漏之处，欢迎指正。
关于其他的缓存算法，例如FIFO，ARC，MRU等，我们会在后续的文章继续探讨。
谢谢~
Last updated:
