一、LRU算法描述

LRU全称是Least Recently Used,最近最少使用的意思,是一种常用的内存置换算法。当内存不够的时候,要把部分内存写入到磁盘中,此时就要用到LRU算法来决定把那部分内存写入到磁盘。

当把内存数据写入到磁盘的时候,肯定是把不常用的内存置换到磁盘这样才是最优的。不然把常用的内存写入磁盘,然后又频繁从磁盘读出来,明显会降低系统性能。LRU的核心思想就是把最近最少使用的内存置换到磁盘中去。

一般来说,实现LRU算法都是使用哈希表+链表来实现,这样可以使得LRU操作的时间复杂度是O(1)。具体的过程描述为:

  1. 传入内存地址,通过哈希表判断内存是否已经存在于链表了。如果内存存在,把节点移到链表开头。
  2. 如果内存不存在于哈希表中,有两种情况:

    • 链表没满,把节点插入链表开头。
    • 链表满了,淘汰掉链表末尾节点,当前节点插入到链表开头。

哈希表中记录的是内存和链表节点的对应关系,这样当一个内存地址传入的时候,在O(1)的时间内就能确定该内存地址是否已经存在于缓存中了。如果没有哈希表,那么每次判断内存是否存在于缓存的时候都要遍历链表查询,需要时间复杂度为O(n)。

LRU图解

假设存在一个缓存容量为5的缓存区,当前已经缓存了1、4、8、9四块内存:

访问内存块3,因为缓存中不含有这块内存,要把3加到缓存中去:

访问内存块5,因为5不存在于缓存中,要把5插入到缓存。但是目前链表已经满了,不能容纳更多的节点,所以必须把最后的节点淘汰掉,也就是去掉9:

访问内存块1,1已经存在于缓存了,把它放到链表最前面来:

二、代码描述

2.1 lru对象设计

实现LRU需要用到双向链表+哈希表:

  • 哈希表保存了每个缓存节点的地址,可以直接使用STL中的map。
  • STL中也有双向链表,可以直接使用这个链表结构。

一个LRU缓存对象需要包含的方法:

  • get():从缓存获取一块内存
  • put():存放一块内存到缓存

LRU对象设计:

// 缓存的数据
typedef pair<int, int> cache_val;

class lru_cache {
private:
    // 链表
    list<cache_val> l;
    // 哈希表
    map<int, list<cache_val>::iterator> m;
    // 链表的容量和长度
    size_t cap, len;
public:
    // 构造函数
    lru_cache(size_t cap) : cap(cap), len(0) {}
}

2.2 get函数实现

get函数的实现:

int get(int key) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;

    it = m.find(key);

    // 没有找到,返回-1
    if (it == m.end())
        return -1;

    // 找到了,移到最前面去
    cache = *(it->second);
    // 先删除
    m.erase(key);
    l.erase(it->second);

    // 再插入
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));
    return it->second->second;
}

2.3 put函数实现

put`函数的实现:

void put(const int &key, const int val) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;
    it = m.find(key);

    // 找到了缓存
    if (it != m.end()) {
        // 移到链表开头
        cache = *(it->second);
        l.erase(it->second);
        l.push_front(cache);
        // 重新修改哈希表的指向
        m.erase(key);
        m[key] = l.begin();
        return;
    }

    // 下面是没有找到缓存,要插入新的节点到链表和哈希表
    // 链表的长度已经超过容量了
    if (len >= cap) {
        // 哈希表移除节点
        m.erase(l.back().first);
        // 链表移除末尾节点
        l.pop_back();
    }

    cache = pair<int, int>(key, val);
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));

    if (len < cap)
        len++;
}

三、单元测试

测试案例:

TEST(lru_cache, leetcode) {
    lru_cache cache = lru_cache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    EXPECT_EQ(1, cache.get(1));       // 返回  1

    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    EXPECT_EQ(-1, cache.get(2));

    cache.put(4, 4);    // 该操作会使得密钥 1 作废
    EXPECT_EQ(-1, cache.get(1));
    EXPECT_EQ(3, cache.get(3));
    EXPECT_EQ(4, cache.get(4));
}

最后修改:2020 年 02 月 14 日
喜欢就给我点赞吧