LRU（Least recently used，最近最少使用），数据插入队列中，经常访问的数据单元靠近列表头部，不经常访问的靠近列表尾部。列表数据就像按照时间排序一样。常用来淘汰一些长时间不使用的数据。
1. 算法流程
lru 算法用一个列表也可以实现。只是列表数据需要更新操作，那得先查找数据，列表的查找时间复杂度是 O(n)，这是个低效的操作，所以用时间复杂度为 O(1) 的哈希表 std::unordered_map 辅助实现查找。
2. 算法实现
简单实现 LRU 算法的添加，更新和删除最旧数据功能。定时测试相关接口操作。(测试源码放在 github)
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
#ifndef _LRU_H_
#define _LRU_H_
#include <iostream>
#include <list>
#include <unordered_map>
class data {
public:
data() {}
data(const data& d) : m_key(d.m_key), m_value(d.m_value) {}
data(const std::string& key, const std::string& value)
: m_key(key), m_value(value) {}
public:
std::string get_key() const { return m_key; }
void set_key(const std::string& key) { m_key = key; }
std::string get_value() const { return m_value; }
void set_value(const std::string& value) { m_value = value; }
private:
std::string m_key;
std::string m_value;
};
class lru {
public:
lru() {}
virtual ~lru();
bool insert(const std::string& key, const std::string& value);
bool update(const std::string& key, const std::string& value);
const data* get_random();
bool pop();
bool check();
private:
std::list<data*> m_list;
std::unordered_map<std::string, std::list<data*>::iterator> m_map;
};
#endif //_LRU_H_
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
int main() {
lru o;
int i = 0;
srand((unsigned)time(NULL));
while (i++ <= 50) {
if (i % 3 == 1) {
o.insert(std::to_string(i), cur_time());
} else if (i % 8 == 0) {
o.pop();
} else {
const data* d = o.get_random();
if (d) {
o.update(d->get_key(), cur_time());
}
}
o.check();
sleep(2);
}
return 0;
}
3. redis 近似 lru 算法
redis 数据库 maxmemory 数据淘汰策略，通过采样实现了近似 LRU 的算法，有兴趣的朋友可以参考我的帖子 [redis 源码走读] maxmemory 数据淘汰策略
