算法 lru c++ 实现

2020-03-11

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
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
...
class data {
   ...
   private:
    std::string m_key;
    std::string m_value;
};

class lru {
   public:
    ...
    bool insert(const std::string& key, const std::string& value);
    bool update(const std::string& key, const std::string& value);
    /* 删除列表末位节点。*/
    bool pop(); 
    ...
   private:
    /* 数据存储列表。*/
    std::list<data*> m_list;
    /* 哈希表,存储列表节点对应的迭代器,协助查找数据。*/
    std::unordered_map<std::string, std::list<data*>::iterator> m_map;
};

bool lru::insert(const std::string& key, const std::string& value) {
    if (key.empty() || value.empty() || (m_map.find(key) != m_map.end())) {
        return false;
    }
    /* 新数据插入列表头部。*/
    m_list.push_front(new data(key, value));
    /* 更新哈希表数据,存储节点在列表的位置信息,方便查询。*/
    m_map[key] = m_list.begin();
    return true;
}

bool lru::update(const std::string& key, const std::string& value) {
    data* d;
    std::unordered_map<std::string, std::list<data*>::iterator>::iterator itr;

    /* 通过哈希表,查找对应节点在列表的位置。*/
    itr = m_map.find(key);
    if (itr == m_map.end()) {
        return false;
    }

    /*更新数据信息。*/
    d = *(itr->second);
    d->set_value(value);

    /* 先从列表删除对应节点,然后重新将节点添加到列表头部。*/
    m_list.erase(itr->second);
    m_list.push_front(d);
    /* 更新哈希表数据,存储节点在列表的位置信息,方便查询。*/
    m_map[d->get_key()] = m_list.begin();

    return true;
}

bool lru::pop() {
    if (m_list.size() == 0) {
        return false;
    }

    data* d;
    std::list<data*>::iterator itr;

    /* 删除列表末位节点。*/
    itr = m_list.end();
    itr--;
    d = *itr;

    /* 删除哈希表对应信息。*/
    m_map.erase(d->get_key());
    /* 删除列表对应节点。*/
    m_list.erase(itr);
    /* 释放数据。*/
    SAFE_DELETE(d);

    return true;
}
  • 测试源码。
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 数据淘汰策略