【算法】LRU算法

迷南。 2024-02-05 22:58 15阅读 0赞

## **LRU算法** ##

LRU(Least Recently Used) 即最近最少使用，属于典型的内存淘汰机制。

根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”，其思路如下图所示：

![img][]

该算法需要达到两个目的：①可以轻易的更新最新的访问数据。②轻易的找出最近最少未使用的数据。所以要用到哈希表+双向链表实现。利用map，获取key对应的value是O(1)，利用双向链表，实现新增和删除都是O(1)。

> 传统意义的LRU算法是为每一个Cache对象设置一个计数器，每次Cache命中则给计数器+1，而Cache用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。它的弊端很明显，如果Cache的数量少，问题不会很大， 但是如果Cache的空间过大，达到10W或者100W以上，一旦需要淘汰，则需要遍历所有计数器，其性能与资源消耗是巨大的。效率也就非常的慢了。双链表LRU的原理： 将Cache的所有位置都用双链表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。 这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，则向链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

LRU数据结构如下图：

![HashLinkedList][]

根据上图我们可以分析一下：

1.  如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
2.  对于某一个 `key`，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 `val`。
3.  链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 `key` 快速映射到任意一个链表节点，然后进行插入和删除。

*  版本1：自己实现循环链表存储，没有用API
    
        /********************不用API的版本*************************/
        /********************简单说一下思路*************************/
        //1.首先hash表用的是unordered_map来实现，用来查找key对应的node节点，所以hash表应该是[key,node]形式存储
        //2.LRUCache这个类实现双向链表的添加，删除，更新和遍历
        //3.同时这个类还要实现get和put两个功能
        //4.我这里用的是循环双向链表，因此查找链表尾端的元素为O(1)，正常的双向链表是O(n)
        //总结：最重要的就是hash表中的key对应的不是int而是一个node节点，这个要记住
        #include<unordered_map>
        #include<iostream>
        struct Node{
            int key;
            int value;
            Node* pre;
            Node* next;
            Node(){}
            Node(int k, int v):key(k), value(v), pre(nullptr), next(nullptr){}
        };
        
        class LRUCache{
        private:
            //通过key可以找到位于链表中的节点
            std::unordered_map<int, Node*> hash;
            int capacity;
            Node* head_node;
        public:
            LRUCache(int cap){
                capacity = cap;
                head_node = new Node();
                //初始化dummy_Node,next和pre都指向自己
                head_node->next = head_node->pre = head_node;
            }
            //将新来的插入双向链表头部
            void add_Node(Node* n);
            //将某个节点拿出来重新插入头部
            void update_Node(Node* n);
            //移除链表中最后一个（最久未使用）
            void pop_back();
            //输出LRU结构
            void show();
            int get(int key);
            void put(int key, int value);
        };
        
        //注意，该节点可能是新节点，也可能是已经存在的有重新入链表的节点
        void LRUCache::add_Node(Node* n){
            //表示当前节点n就是dummy的next节点，不用加入
            if(n->pre == head_node){
                return;
            }
            //将节点n插入head_node后面
            n->pre = head_node;
            n->next = head_node->next;
            head_node->next->pre = n;
            head_node->next = n;
        }
        
        void LRUCache::update_Node(Node* n){
            //表示当前节点n就是dummy的next节点，不用断掉
            if(n->pre == head_node){
                return;
            }
            n->next->pre = n->pre;
            n->pre->next = n->next;
            add_Node(n);
        }
        
        //弹出链表的最后一个，由于是循环链表，就是head_node->pre
        void LRUCache::pop_back(){
            Node* tmp = head_node->pre;
            head_node->pre = tmp->pre;
            tmp->pre->next = head_node;
            //删除unordered_map中的key
            hash.erase(tmp->key);
        }
        
        void LRUCache::show(){
            //链表中没有节点，退出
            if(head_node->next = head_node){
                return;
            }
            Node* tmp = head_node->next;
            while(tmp->next != head_node){
                std::cout<<"key:"<<tmp->key<<",vlaue:"<<tmp->value<<std::endl;
            }
        }
        int LRUCache::get(int key){
            auto it = hash.find(key);
            if(it == hash.end()){
                std::cout<<"there is no key"<<std::endl;
                return -1;
            }
            //取出key对应的node节点
            Node* node = it->second;
            update_Node(node);
            return node->value;
        
        }
        void LRUCache::put(int key, int value){
            auto it = hash.find(key);
            if(it == hash.end()){
                Node* node = new Node(key, value);
                add_Node(node);
                hash.insert({key, node});
                if(hash.size() > capacity){
                    
                    pop_back();
                }
            }else{
                it->second->value = value;
                update_Node(it->second);
            }
        }
 *  版本2：使用deque，为什么使用deque说的很清楚
    
        /****************注意unordered_map的插入************/
        
        #include <iostream>
        #include <deque>
        #include <unordered_map>
        #include <list>
        
        class LRUCache{
        private:
            int capacity;
            //1.之所以用deque不用list是因为移除尾部元素的时候，deque方便
            //2.deque里面可以存储自定的node类型，也可以用pair表示，这里我用pair了
            std::deque<std::pair<int, int>> my_deque;
            //通过key找到对应key在deque中的位置
            std::unordered_map<int, std::deque<std::pair<int, int>>::iterator> hash;
        public:
            LRUCache(int cap):capacity(cap){}
            int get(int key);
            void put(int key, int value);
        };
        
        int LRUCache::get(int key){
            if(hash.find(key) == hash.end()){
                std::cout<<"there is no key"<<std::endl;
                return -1;
            }
            std::pair<int, int> tmp = *hash[key];
            my_deque.erase(hash[key]);
            my_deque.push_front(tmp);
            //更新hash表中对应key位于deque的位置
            hash[key] = my_deque.begin();
            return tmp.second;
        }
        
        void LRUCache::put(int key, int value){
            if(hash.find(key) == hash.end()){
                if(my_deque.size() >= capacity){
                    //把hash表中的抹除，然后删除deque中的
                    auto it = my_deque.back();
                    hash.erase(it.first);
                    my_deque.pop_back();
                    my_deque.push_front({key, value});
                    hash.insert({key, my_deque.begin()});
                }else{
                    my_deque.push_front({key, value});
                    hash.insert({key, my_deque.begin()});
                }
            }else{
                //更新就行
                my_deque.erase(hash[key]);
                my_deque.push_front({key, value});
                //更新hash表中key的位置
                hash[key] = my_deque.begin();
            }
        }

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/9b8dcdae9dc646d59fe3fb82f012173a.png
[HashLinkedList]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5aaab4c960d44ce3816f4f82cde43d00.png