欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU原理及其实现(C++)

程序员文章站 2022-06-17 14:51:55
...

读完本文,你不仅学会了算法思路,还可以顺便去 LeetCode 上拿下如下题目:146.LRU缓存机制

LRU原理

在一般标准的操作系统教材里,会用下面的方式来演示 LRU 原理,假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。

LRU原理及其实现(C++)

但是如果让我们自己设计一个基于 LRU 的缓存,这样设计可能问题很多,这段内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。

那么如何设计一个LRU缓存,使得放入和移除都是 O(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。

基于 HashMap 和 双向链表实现 LRU

整体的设计思路是,可以使用 HashMap 存储 key,这样可以做到 save 和 get key的时间都是 O(1),而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点。

LRU原理及其实现(C++)

LRU 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 LRU 的容量,如果存储满了,可以通过 O(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 O(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。

下面展示了,预设大小是 3 的,LRU存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 HashMap部分的变化,仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下:

save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)

相应的 LRU 双向链表部分变化如下:

LRU原理及其实现(C++)

总结一下核心操作的步骤:

  1. save(key, value),首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果LRU空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key。
  2. get(key),通过 HashMap 找到 LRU 链表节点,因为根据LRU 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

完整基于 C++的代码参考如下

struct DLinkedNode {    
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};


class LRUCache {
private:
    map<int, DLinkedNode*> maap;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int cap;

public:
    LRUCache(int capacity) {
        cap = capacity;
        size = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(!maap.count(key))
            return -1;
        DLinkedNode* node = maap[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(maap.count(key)){
            DLinkedNode* node = maap[key];
            moveToHead(node);
            node->value = value;
        }else{
            DLinkedNode* node = new DLinkedNode(key,value);
            addToHead(node);
            maap[key] = node;
            size++;
            if(size > cap){
                DLinkedNode* remoNode = removeTail();
                maap.erase(remoNode->key);
                delete remoNode;
                size--;
            }
        }
    }

    void addToHead(DLinkedNode* node){
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    void removeNode(DLinkedNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void moveToHead(DLinkedNode* node){
        removeNode(node);
        addToHead(node);
    }
    DLinkedNode* removeTail(){
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }

};

/**
 * 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);
 */