当前位置: 首页 > news >正文

重庆忠县网站建设公司哪家好怎么开网店

重庆忠县网站建设公司哪家好,怎么开网店,WordPress和微信公众号,网站建设简介淄博LRU缓存 LRU缓存的实现思路LRU缓存的操作C11 STL实现LRU缓存自行设计双向链表 哈希表 LRU(Least Recently Used,最近最少使用)缓存是一种常见的缓存淘汰算法,其基本思想是:当缓存空间已满时,移除最近最少使…

LRU缓存

  • LRU缓存的实现思路
  • LRU缓存的操作
  • C++11 STL实现LRU缓存
  • 自行设计双向链表 + 哈希表

LRU(Least Recently Used,最近最少使用)缓存是一种常见的缓存淘汰算法,其基本思想是:当缓存空间已满时,移除最近最少使用的数据。LRU缓存通常通过链表(双向链表)和哈希表相结合来实现,利用哈希表快速查找,链表保持数据的使用顺序。

链接:leetcode 设计LRU缓存

LRU缓存的实现思路

实现思路:哈希表 + 双向链表

  • 为什么使用哈希表?
    哈希表:用来存储键值对,可以在常数时间内(O(1))进行查找、插入和删除操作。

  • 为什么使用双向带头尾链表?
    双向链表:用来维护数据的使用顺序。最近使用的元素放在链表的头部,最久未使用的元素放在链表的尾部。通过这种方式可以在O(1)的时间复杂度下实现删除最久未使用的元素。

LRU缓存的操作

  • Get(key): 如果键存在于缓存中,返回对应的值并将该键值对移到链表头部,表示最近被访问过。如果不存在,返回-1。
  • Put(key, value): 插入键值对。如果缓存已满,则删除最久未使用的元素,之后插入新的键值对,并将其移到链表头部。

C++11 STL实现LRU缓存

时间复杂度分析:
get(key):查找操作是O(1),然后通过 touch 函数将键移到链表头部,也是在O(1)时间内完成的。
put(key, value):插入或更新键值对的操作是O(1),如果缓存满了需要删除最久未使用的元素(evict),删除操作也是O(1)。因此,get 和 put 操作的时间复杂度都是 O(1)。

#include <iostream>
#include <unordered_map>
#include <list>class LRUCache {
public:LRUCache(int capacity) : capacity(capacity) {}// 获取缓存中的值int get(int key) {auto it = cache.find(key);if (it == cache.end()) {return -1;  // 未找到键,返回 -1}touch(it);  // 标记为最近使用return it->second.first;  // 返回对应的值}// 插入新的键值对void put(int key, int value) {auto it = cache.find(key);if (it != cache.end()) {touch(it);  // 标记为最近使用it->second.first = value;  // 更新值} else {if (cache.size() == capacity) {evict();  // 删除最久未使用的元素}// 插入新的键值对到链表头部order.push_front(key);cache[key] = {value, order.begin()};  // 存入哈希表,值和链表位置}}private:// 更新元素为最近使用void touch(std::unordered_map<int, std::pair<int, std::list<int>::iterator>>::iterator it) {int key = it->first;order.erase(it->second.second);  // 删除当前元素order.push_front(key);  // 将元素插入链表头部it->second.second = order.begin();  // 更新迭代器位置}// 淘汰最久未使用的元素void evict() {int key_to_evict = order.back();  // 获取尾部元素(最久未使用)order.pop_back();  // 从链表中移除cache.erase(key_to_evict);  // 从哈希表中删除}int capacity;  // 缓存容量std::list<int> order;  // 双向链表,维护键的访问顺序std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;  // 哈希表,存储键值对和链表位置
};int main() {LRUCache cache(2);  // 设置缓存容量为2cache.put(1, 1);    // 缓存: {1=1}cache.put(2, 2);    // 缓存: {1=1, 2=2}std::cout << cache.get(1) << std::endl;  // 返回 1,缓存: {2=2, 1=1}cache.put(3, 3);    // 淘汰键 2,缓存: {1=1, 3=3}std::cout << cache.get(2) << std::endl;  // 返回 -1 (未找到)cache.put(4, 4);    // 淘汰键 1,缓存: {3=3, 4=4}std::cout << cache.get(1) << std::endl;  // 返回 -1 (未找到)std::cout << cache.get(3) << std::endl;  // 返回 3std::cout << cache.get(4) << std::endl;  // 返回 4return 0;
}

效果:代码简洁,但效率不高。
在这里插入图片描述

自行设计双向链表 + 哈希表

#include <iostream>
#include <unordered_map>using namespace std;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:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;public:LRUCache(int _capacity) : capacity(_capacity), size(0) {// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) {return -1;  // 如果找不到该键,返回 -1}DLinkedNode* node = cache[key];moveToHead(node);  // 移动到链表头部return node->value;  // 返回值}void put(int key, int value) {if (!cache.count(key)) {// 如果 key 不存在,创建新节点DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node;addToHead(node);  // 添加到链表头部++size;if (size > capacity) {// 超过容量,删除尾部节点DLinkedNode* removed = removeTail();cache.erase(removed->key);  // 从哈希表中删除该键delete removed;  // 防止内存泄漏--size;}}else {// 如果 key 存在,更新值,并移到头部DLinkedNode* node = cache[key];node->value = value;moveToHead(node);}}void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;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;}
};int main() {LRUCache cache(2);  // 缓存容量为2cache.put(1, 1);    // 缓存: {1=1}cache.put(2, 2);    // 缓存: {1=1, 2=2}cout << cache.get(1) << endl;  // 返回 1,缓存: {2=2, 1=1}cache.put(3, 3);    // 淘汰键 2,缓存: {1=1, 3=3}cout << cache.get(2) << endl;  // 返回 -1,键 2 不存在cache.put(4, 4);    // 淘汰键 1,缓存: {3=3, 4=4}cout << cache.get(1) << endl;  // 返回 -1,键 1 不存在cout << cache.get(3) << endl;  // 返回 3cout << cache.get(4) << endl;  // 返回 4return 0;
}

代码转自力扣官方题解。
效果:时间复杂度明显降低, 效率提高。在这里插入图片描述

总结

上述实现利用了哈希表和双向链表的组合,保证了LRU缓存操作的高效性。哈希表提供了O(1)的查找和更新时间,而双向链表提供了O(1)的插入和删除操作,确保了缓存的高效管理。这个实现适用于高性能缓存系统,如数据库缓存、Web缓存等。

http://www.zhongyajixie.com/news/62885.html

相关文章:

  • 呼和浩特网站建设宣传登封搜索引擎优化
  • 做网站和推广seo在线培训机构
  • 西安到北京飞机几个小时网站内容优化关键词布局
  • 开发 网站 费用seo竞价推广
  • 长沙网站建设建关键词优化公司哪家强
  • 网站域名指什么优化设计六年级下册语文答案
  • 北京 网站空间 租用短视频推广渠道有哪些
  • 假山网站如何做怎么在百度上做广告推广
  • 怎么做网上问卷湖南seo推广系统
  • 通辽做家教的网站电商网络销售是做什么
  • 如何做自己的公司网站网络运营培训班
  • 中小企业网站多大空间互联网推广怎么找客户
  • 公司简介模板免费图片泉州百度seo公司
  • pc网站 公众号数据互通千锋教育培训
  • 建设公司营销网站百度seo排名优化排行
  • 罗湖附近公司做网站建设哪家技术好永久免费域名注册
  • 济南网站制作软件中国seo高手排行榜
  • 苏州建筑设计公司seo外包是什么意思
  • 外贸网站制作价格表苏州网站建设公司排名
  • 百度网站提交入口百度seo技术软件
  • 九一制作网站长沙网络推广网站制作
  • 企业网站模板哪里好关于新品牌的营销策划
  • 网站备案最快要几天google海外版
  • 外包网站建设费用包括网站备份市场调研报告范文模板word
  • 按钮特效网站免费网站注册平台
  • 同ip网站过多是空间的原因还是域名的原因品牌推广渠道
  • 新站网站如何做Seoseo网站优化培训多少价格
  • 高阳网站制作域名注册需要多少钱?
  • 权威的网站建设北京关键词优化服务
  • 网站关键词排名100免费独立站自建站网站