欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 名人名企 > LRU算法

LRU算法

2024/11/30 18:08:46 来源:https://blog.csdn.net/m0_75266675/article/details/143192492  浏览:    关键词:LRU算法

LRU算法

前言:

我们常用缓存提升数据查询速度,由于缓存的容量有限,当达到上限的时候,就需要删除部分数据挪出空间,这样新的数据才可以添加进来,缓存数据不能随机删除,一般情况下需要根据某种特定的算法删除缓存数据,常用的淘汰算法右LRU,LFU,FIFO

核心思想:如果数据最近被访问过,那么是热门数据,下次很大概率会再次被使用。如果内存满了,有限淘汰最近很少使用的数据

LRU: Least Recently Used, 最近最少使用,主要应用场景是缓存,缓存规则如下。

①.最近被使用或访问的数据放置在最前面;
②.没当缓存命中(即缓存数据被访问)则将数据移到头部;
③.当缓存数量达到最大值时,将最近最少访问的数据剔除;

  • 访问一个数据,哪个数据就会被添加到头节点。
class Node { // 双向链表的节点
public:int key;    // key值是为了便于哈希表的定位int value;  // 缓存的数据Node* prev; // 前驱指针Node* next; // 后驱指针// 构造函数// 给一个默认参数key为0,v为0Node(int k = 0, int v = 0) : key(k), value(v) {}
};class LRUCache {
private:int capacity; // 缓存的容量Node* dummy;  // 哨兵节点,双向链表的头节点unordered_map<int, Node*> key_to_node;// 哈希表,存储key和node的信息
public:// 构造函数LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {dummy->prev = dummy;dummy->next = dummy;}// 删除一个节点(抽出一本书)// 双向链表的删除节点void remove(Node* x) {x->prev->next = x->next; // 前面的后继要改x->next->prev = x->prev; // 后面的前驱要改}// 在链表头添加一个节点(把一本书放在最上面)// 双向链表的头插void push_front(Node* x) {x->next = dummy->next; // 1dummy->next = x;       // 4x->prev = dummy;       // 2x->next->prev = x;     // 3// 4一定要在1的后面,其他的顺序随意,绑线原则}Node* get_node(int key) {auto it = key_to_node.find(key);if (it == key_to_node.end()) // 没有这本书return nullptr;auto node = it->second; // 有这本书remove(node);           // 把这本书抽出来push_front(node);       // 放在最上面return node;            //返回这本书}int get(int key) {auto node = get_node(key);//如果node不为空,就返回node的value//如果为空,就是-1return node ? node->value : -1;}void put(int key, int value) {auto node = get_node(key);//获取node//node不为空,就是有这本书if (node) {              // 有这本书node->value = value; // 更新 valuereturn;}node = new Node(key, value); // 新书key_to_node[key] = node;push_front(node);                               // 放在最上面//超过容量if (key_to_node.size() > capacity) {            // 书太多了auto back_node = dummy->prev;//头节点的前驱放的是最后一个节点key_to_node.erase(back_node->key);remove(back_node); // 去掉最后一本书delete back_node;  // 释放内存}}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com