SQL-Serverleetcode - LRU缓存 - Powered by Discuz! Archiver

忿忿的泥巴坨 发表于 2024-11-27 12:12:09

leetcode - LRU缓存

什么是 LRU

LRU (迩来最少利用算法),
最早是在操作系统中打仗到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略.

LRU算法基于局部性原理, 即迩来被访问的数据在未来被访问的概率更高, 因此应该保留迩来被访问的数据.
迩来最少利用的表明

LRU (迩来最少利用算法), 中的 "迩来" 不是其绝对值的修饰, 而是一个范围.
如: 你迩来去了那些地方, 迩来看了哪些书.
而不是: 离你迩来的人是谁, 离你迩来的座位是哪一个.
了解了迩来的意义, 那么串联起来就是: 迩来利用的一堆数据中, 哪一个数据利用的是最少的
LRU原理

下面展示了 LRU 算法的基本原理.
https://i-blog.csdnimg.cn/direct/8044a157506240b7b7f324c5525f6c68.png

可以看到, 在 LRU 算法中, 涉及到了对象的移动, 假如利用数组来作为缓存, 那么移动对象的服从很慢. 因为在这个算法中, 经常涉及到头插元素, 数组的头插是O(n^2), 非常的慢.
所以推荐利用双向链表来实现.
146. LRU 缓存 - 力扣（LeetCode）
但是在题目中, 要求查找和插入的时间复杂度为O(1);
双向链表的插入删除时间复杂度为O(1), 但是查找的时间复杂度为O(n).
双向链表 + 哈希表

单利用双向链表, 查找的时间复杂度为O(n), 那么数据布局的查找操作的时间复杂度为O(1)?
答案很明显: 哈希表
https://i-blog.csdnimg.cn/direct/b9ef8f4989de4a6da27bfe76a950f6e4.png
界说链表节点 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_map<int, 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 不存在, 则返回 -1
int get(int key) {
   auto it = table.find(key); // 通过 hashtable 查找 key 是否存在
   if(it == table.end())
   {
         return -1; // 不存在对应的 , 返回 -1
   }
   // 存在 key, 记录value, 然后更新这个节点, 将这个节点移动到链表头部
   int ret = it->second->value;
   MoveToHead(it->second); // 将这个节点移动到头部
   return ret;
}
// 插入一对键值对
void put(int key, int value) {
   auto it = table.find(key); // 在 hashtable 中查找是否已经存在 key
   if(it != table.end()) // 已经存在 key 则更新节点的值, 并且将这个节点移动到链表头部
   {
         // 更新节点
         it->second->value = value;
         MoveToHead(it->second); // 将节点移动到链表头部
         return; // 直接返回, 下面是进行插入的操作
   }

   // key 不存在, 判断空间是否已满, 满了就需要删除链表末尾的节点
   if(_size == _capacity)
   {
         // ListNode 中记录的 key 就起作用了, 如果只有 value, 那么就还需要遍历 table
         int back = tail->prev->key;
         table.erase(back); // 删除 hashtable 中这个节点的记录
         pop_back(); // 删除尾部节点
         --_size;
   }
   // 链表末尾的节点已被删除, 现在需要向链表头部插入新的节点
   ListNode* node = push_front(key, value);
   table = 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;
}
}; https://i-blog.csdnimg.cn/direct/662965db570543e09660092667590dd0.png

完整代码

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_map<int, 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 = 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;
}

};

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

页: [1]

IT评测·应用市场-qidao123.com技术社区's Archiver

leetcode - LRU缓存