网站备案需要当面核验哪些信息,网页制作三合一第二版,桂林网站优化价格,企业所得税税前扣除凭证管理办法什么是 LRU
LRU (最近最少使用算法), 最早是在操作系统中接触到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略. LRU算法基于局部性原理, 即最近被访问的数据在未来被访问的概率更高, 因此应该保留最近被访问的数据. 最近最少使用的解释 LRU (最近最少使用算法), 中…什么是 LRU
LRU (最近最少使用算法), 最早是在操作系统中接触到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略. LRU算法基于局部性原理, 即最近被访问的数据在未来被访问的概率更高, 因此应该保留最近被访问的数据. 最近最少使用的解释 LRU (最近最少使用算法), 中的 最近 不是其绝对值的修饰, 而是一个范围. 如: 你最近去了那些地方, 最近看了哪些书. 而不是: 离你最近的人是谁, 离你最近的座位是哪一个. 了解了最近的意义, 那么串联起来就是: 最近使用的一堆数据中, 哪一个数据使用的是最少的
LRU原理
下面展示了 LRU 算法的基本原理. 可以看到, 在 LRU 算法中, 涉及到了对象的移动, 如果使用 数组 来作为缓存, 那么移动对象的效率很慢. 因为在这个算法中, 经常涉及到头插元素, 数组 的头插是O(n^2), 非常的慢.
所以推荐使用 双向链表 来实现.
146. LRU 缓存 - 力扣LeetCode
但是在题目中, 要求查找和插入的时间复杂度为O(1); 双向链表的插入删除时间复杂度为O(1), 但是查找的时间复杂度为O(n).
双向链表 哈希表
单使用双向链表, 查找的时间复杂度为O(n), 那么数据结构的查找操作的时间复杂度为O(1)? 答案很明显: 哈希表 定义链表节点 ListNode
struct ListNode
{
public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;// 节点中不仅存储 value, 还存储 key, 这在后面的 put 函数中有用ListNode* next;ListNode* prev;
};
LRUcache 成员属性
class LRUCache {
public:int _size 0; // 记录缓存中已经缓存了多少数据int _capacity 0; // 记录缓存大小 (可缓存的数据个数)ListNode* head nullptr; // 双向链表的头节点ListNode* tail nullptr; // 双向链表的尾节点unordered_mapint, ListNode* table;// 底层是通过 hashtable 实现的map, 用来通过 kev 查找节点
}
LRUcache 成员方法
构造 / get / put 函数
class LRUCache {
public:LRUCache(int capacity) {_capacity capacity; // 记录缓存的大小// 初始化链表的 头节点 和 尾节点head new ListNode;tail new ListNode;// 将头尾节点连接起来head-next tail;head-prev tail;tail-next head;tail-prev head;}// 通过 key 获取对应的 value. 如果 key 不存在, 则返回 -1int get(int key) {auto it table.find(key); // 通过 hashtable 查找 key 是否存在if(it table.end()){return -1; // 不存在对应的 [key, value], 返回 -1}// 存在 key, 记录value, 然后更新这个节点, 将这个节点移动到链表头部int ret it-second-value;MoveToHead(it-second); // 将这个节点移动到头部return ret;}// 插入一对键值对 [key, value]void put(int key, int value) {auto it table.find(key); // 在 hashtable 中查找是否已经存在 keyif(it ! table.end()) // 已经存在 key 则更新节点的值, 并且将这个节点移动到链表头部{// 更新节点it-second-value value;MoveToHead(it-second); // 将节点移动到链表头部return; // 直接返回, 下面是进行插入的操作}// key 不存在, 判断 空间是否已满, 满了就需要删除 链表末尾的节点if(_size _capacity){// ListNode 中记录的 key 就起作用了, 如果只有 value, 那么就还需要遍历 tableint back tail-prev-key;table.erase(back); // 删除 hashtable 中这个节点的记录pop_back(); // 删除尾部节点--_size;}// 链表末尾的节点已被删除, 现在需要向 链表头部 插入 新的节点ListNode* node push_front(key, value);table[key] node; // 在 hashtable 中记录这个新的节点_size;}
};
MoveToHead / push_front / pop_back 函数
class LRUCache {
public:// 将 node 移动到链表头部void MoveToHead(ListNode* node){if(node head-next) // 如果这个节点就是头部, 那么就不移动{return;}ListNode* node_next node-next; // 记录 node 节点的后一个节点ListNode* node_prev node-prev; // 记录 node 节点的前一个节点node_prev-next node_next; // 将 node 的前后节点连接起来node_next-prev node_prev;// 将 node 节点链接到链表首部node-prev head; node-next head-next;head-next-prev node;head-next node;}// 头插ListNode* push_front(int key, int value){ListNode* node new ListNode(key, value);ListNode* next head-next;head-next node;node-prev head;next-prev node;node-next next;return node;}// 尾删void pop_back(){ListNode* prev tail-prev-prev;ListNode* cur tail-prev;prev-next tail;tail-prev prev;delete cur;}
}; 完整代码
class LRUCache {
public:struct ListNode{public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;ListNode* next;ListNode* prev;};int _size 0;int _capacity 0;ListNode* head nullptr;ListNode* tail nullptr;unordered_mapint, ListNode* table;LRUCache(int capacity) {_capacity capacity;head new ListNode;tail new ListNode;head-next tail;head-prev tail;tail-next head;tail-prev head;}int get(int key) {auto it table.find(key);if(it table.end()){return -1;}int ret it-second-value;MoveToHead(it-second); // 将这个节点移动到头部return ret;}void put(int key, int value) {auto it table.find(key);if(it ! table.end()){// 更新节点it-second-value value;MoveToHead(it-second);return;}if(_size _capacity){int back tail-prev-key;table.erase(back); // 删除 hashtable 中的键值对pop_back(); // 删除尾部节点--_size;}ListNode* node push_front(key, value);table[key] node;_size;}void MoveToHead(ListNode* node){if(node head-next){return;}ListNode* node_next node-next;ListNode* node_prev node-prev;node_prev-next node_next;node_next-prev node_prev;node-prev head;node-next head-next;head-next-prev node;head-next node;}ListNode* push_front(int key, int value){ListNode* node new ListNode(key, value);ListNode* next head-next;head-next node;node-prev head;next-prev node;node-next next;return node;}void pop_back(){ListNode* prev tail-prev-prev;ListNode* cur tail-prev;prev-next tail;tail-prev prev;delete cur;}};
