实现一个 LRU 风格的缓存类

实现一个缓存类

    • 需求描述
    • 豆包
      • 解决思路:
      • 实现代码:
      • 优化1
        • 1. `std::list::remove` 的时间复杂度问题
        • 2. 代码复用
        • 优化后的代码
        • 优化说明
      • 优化2
        • 1. 边界条件检查
        • 2. 异常处理
        • 3. 代码封装性
        • 4. 线程安全
        • 优化后的代码示例
        • 优化说明
    • DeepSeek(深度思考R1):
      • 代码实现
        • 实现说明:
      • 优化方案一:基础互斥锁版本
      • 优化方案二:读写锁版本(C++17+)
      • 优化分析说明:

需求描述

类似于Windows系统的 win 菜单最近打开功能模块,使用最近最少使用(LRU)的缓存淘汰策略,缓存可以设置最大容量。
get:获取缓存数据,不存在时返回 -1
put:新增或者更新缓存,当容量已满时,删除最早的数据,再插入

class UpdateCaching {public:UpdateCaching(int capacity){}int get(int key){}void put(int key ,int value){}
}

豆包

解决思路:

  1. 使用 std::unordered_map 存储键值对,以便快速查找和更新数据。(为啥使用 unordered_map 而不是 map)

  2. 使用 std::list 存储键的访问顺序,以便在容量满时删除最早的数据。

  3. put 操作中:

    • 检查缓存是否已满,如果已满,删除 list 中的第一个元素,并从 unordered_map 中移除对应的键值对。
    • 将新元素添加到 unordered_map 中,并将键添加到 list 的末尾。
  4. get 操作中:

    • 使用 unordered_map 查找键是否存在,如果存在,将键移到 list 的末尾,表示最近访问过。

实现代码:

#include <iostream>
#include <unordered_map>
#include <list>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::list<int> keyOrder;int capacity;public:UpdateCaching(int cap) : capacity(cap) {}int get(int key) {if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾,表示最近使用过keyOrder.remove(key);keyOrder.push_back(key);return cache[key];}void put(int key, int value) {if (cache.count(key) > 0) {// 键已存在,更新值并将其移到列表末尾cache[key] = value;keyOrder.remove(key);keyOrder.push_back(key);return;}if (cache.size() >= capacity) {// 缓存已满,移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);}
};int main() {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1return 0;
}

优化1

1. std::list::remove 的时间复杂度问题

getput 方法中,使用 keyOrder.remove(key) 来移动元素到列表末尾。std::list::remove 的时间复杂度是 O ( n ) O(n) O(n),因为它需要遍历整个列表来找到要删除的元素。可以通过维护一个指向每个键在列表中位置的映射,将这一操作的时间复杂度优化到 O ( 1 ) O(1) O(1)

2. 代码复用

getput 方法中都有将键移到列表末尾的操作,可以将这一操作提取成一个单独的方法,提高代码的复用性。

优化后的代码
#include <iostream>
#include <unordered_map>
#include <list>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::unordered_map<int, std::list<int>::iterator> keyIterators;std::list<int> keyOrder;int capacity;// 将键移到列表末尾void moveToBack(int key) {auto it = keyIterators[key];keyOrder.erase(it);keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();//更新映射容器中key对应的迭代器}public:UpdateCaching(int cap) : capacity(cap) {}int get(int key) {if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾,表示最近使用过moveToBack(key);return cache[key];}void put(int key, int value) {if (cache.count(key) > 0) {// 键已存在,更新值并将其移到列表末尾cache[key] = value;moveToBack(key);return;}if (cache.size() >= capacity) {// 缓存已满,移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);keyIterators.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}
};int main() {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1return 0;
}
优化说明
  1. 引入 keyIterators 映射:用于存储每个键在 keyOrder 列表中的迭代器,这样在移动元素到列表末尾时,就可以直接通过迭代器删除元素,时间复杂度为 O ( 1 ) O(1) O(1)
  2. 提取 moveToBack 方法:将将键移到列表末尾的操作提取成一个单独的方法,提高了代码的复用性和可读性。

通过这些优化,getput 方法的时间复杂度都可以优化到 O ( 1 ) O(1) O(1)

优化2

1. 边界条件检查

在构造函数中可以添加对 capacity 参数的检查,避免传入不合法的值(如负数),增强代码的健壮性。

2. 异常处理

在实际应用中,std::unordered_mapstd::list 的操作可能会抛出异常(如内存分配失败),可以考虑添加异常处理机制,让代码在异常情况下能有更好的表现。

3. 代码封装性

可以提供一些额外的接口方法,如获取缓存当前大小、检查缓存是否为空等,方便调用者使用。

4. 线程安全

如果该缓存类要在多线程环境下使用,需要添加同步机制,保证线程安全。

优化后的代码示例
#include <iostream>
#include <unordered_map>
#include <list>
#include <mutex>class UpdateCaching {
private:std::unordered_map<int, int> cache;std::unordered_map<int, std::list<int>::iterator> keyIterators;std::list<int> keyOrder;int capacity;mutable std::mutex mtx;  // 用于线程安全的互斥锁// 将键移到列表末尾void moveToBack(int key) {std::lock_guard<std::mutex> lock(mtx);  // 加锁,在get或put中被调用时已经加锁了,且是同一个锁 mtx,不会再次进行真正的加锁操作auto it = keyIterators[key];keyOrder.erase(it);keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}public:// 构造函数添加边界检查UpdateCaching(int cap) : capacity(cap) {if (cap <= 0) {throw std::invalid_argument("Capacity must be a positive integer.");}}int get(int key) {std::lock_guard<std::mutex> lock(mtx);  // 加锁if (cache.count(key) == 0) {return -1;}// 将访问的键移到列表末尾,表示最近使用过moveToBack(key);return cache[key];}void put(int key, int value) {std::lock_guard<std::mutex> lock(mtx);  // 加锁if (cache.count(key) > 0) {// 键已存在,更新值并将其移到列表末尾cache[key] = value;moveToBack(key);return;}if (cache.size() >= capacity) {// 缓存已满,移除最久未使用的元素int oldestKey = keyOrder.front();keyOrder.pop_front();cache.erase(oldestKey);keyIterators.erase(oldestKey);}// 插入新元素cache[key] = value;keyOrder.push_back(key);keyIterators[key] = --keyOrder.end();}// 获取缓存当前大小size_t size() const {std::lock_guard<std::mutex> lock(mtx);  // 加锁return cache.size();}// 检查缓存是否为空bool empty() const {std::lock_guard<std::mutex> lock(mtx);  // 加锁return cache.empty();}
};int main() {try {UpdateCaching cache(3);cache.put(1, 10);cache.put(2, 20);cache.put(3, 30);std::cout << cache.get(2) << std::endl;  // 输出 20cache.put(4, 40);  // 缓存已满,删除最早的元素 (1, 10)std::cout << cache.get(1) << std::endl;  // 输出 -1std::cout << "Cache size: " << cache.size() << std::endl;std::cout << "Is cache empty? " << (cache.empty() ? "Yes" : "No") << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}

在多线程环境下使用:

// 线程函数,用于向缓存中插入数据
void insertData(UpdateCaching& cache, int start, int end) {for (int i = start; i < end; ++i) {cache.put(i, i * 10);}
}// 线程函数,用于从缓存中获取数据
void getData(UpdateCaching& cache, int start, int end) {for (int i = start; i < end; ++i) {int value = cache.get(i);if (value != -1) {std::cout << "Key: " << i << ", Value: " << value << std::endl;}}
}int main() {try {UpdateCaching cache(10);// 创建插入数据的线程std::thread insertThread1(insertData, std::ref(cache), 0, 5);std::thread insertThread2(insertData, std::ref(cache), 5, 10);// 创建获取数据的线程std::thread getThread1(getData, std::ref(cache), 0, 5);std::thread getThread2(getData, std::ref(cache), 5, 10);// 等待所有线程完成insertThread1.join();insertThread2.join();getThread1.join();getThread2.join();std::cout << "Cache size: " << cache.size() << std::endl;} catch (const std::exception& e) {std::cerr << "Exception: " << e.what() << std::endl;}return 0;
}
优化说明
  1. 边界条件检查:在构造函数中添加了对 capacity 参数的检查,如果传入的值不合法,会抛出 std::invalid_argument 异常。
  2. 异常处理:通过 try-catch 块捕获可能抛出的异常,并进行相应的处理,提高了代码的健壮性。
  3. 代码封装性:添加了 size()empty() 方法,方便调用者获取缓存的当前大小和检查缓存是否为空。
  4. 线程安全:使用 std::mutex 实现了简单的线程安全机制,在关键操作(如 getputsizeempty 等)前加锁,确保多线程环境下的操作安全。

DeepSeek(深度思考R1):

代码实现

#include <list>
#include <unordered_map>
#include <algorithm>using namespace std;class UpdateCaching {
private:int max_capacity;list<pair<int, int>> cache_list;unordered_map<int, list<pair<int, int>>::iterator> cache_map;public:UpdateCaching(int capacity) {max_capacity = max(0, capacity); // 处理非法容量值}int get(int key) {auto it = cache_map.find(key);if (it == cache_map.end()) {return -1;}// 将访问的节点移动到链表头部cache_list.splice(cache_list.begin(), cache_list, it->second);return it->second->second;}void put(int key, int value) {if (max_capacity <= 0) return; // 容量为0时不操作auto it = cache_map.find(key);if (it != cache_map.end()) {// 更新已有值并移到头部it->second->second = value;cache_list.splice(cache_list.begin(), cache_list, it->second);return;}// 插入新数据if (cache_map.size() >= max_capacity) {// 删除最久未使用的数据int last_key = cache_list.back().first;cache_map.erase(last_key);cache_list.pop_back();}// 插入新数据到头部cache_list.emplace_front(key, value);cache_map[key] = cache_list.begin();}
};
实现说明:
  1. 数据结构选择

    • 使用双向链表list维护访问顺序,最近访问的节点保持在链表头部
    • 使用哈希表unordered_map实现O(1)时间复杂度的查找操作
  2. 核心操作

    • get操作
      • 查找存在时,将节点移动到链表头部并返回值
      • 不存在时返回-1
    • put操作
      • 已存在时更新值并移动到头部
      • 不存在时先检查容量,满时删除链表尾部元素
      • 插入新元素到链表头部并更新哈希表
  3. 边界处理

    • 构造函数处理非法容量值(负数自动设为0)
    • 容量为0时缓存不可用
    • 正确处理链表空时的删除操作
  4. 时间复杂度

    • get和put操作的时间复杂度均为O(1)
    • 链表操作使用splice实现节点移动,保证O(1)时间复杂度

在原有LRU缓存实现基础上,可以通过以下方案优化线程安全问题:

优化方案一:基础互斥锁版本

#include <list>
#include <unordered_map>
#include <mutex>class UpdateCaching {
private:int max_capacity;list<pair<int, int>> cache_list;unordered_map<int, list<pair<int, int>>::iterator> cache_map;mutable mutex cache_mutex; // 可变的互斥锁public:UpdateCaching(int capacity) : max_capacity(max(0, capacity)) {}int get(int key) {lock_guard<mutex> lock(cache_mutex); // 自动加锁if (auto it = cache_map.find(key); it != cache_map.end()) {cache_list.splice(cache_list.begin(), cache_list, it->second);return it->second->second;}return -1;}void put(int key, int value) {lock_guard<mutex> lock(cache_mutex);if (max_capacity <= 0) return;if (auto it = cache_map.find(key); it != cache_map.end()) {it->second->second = value;cache_list.splice(cache_list.begin(), cache_list, it->second);return;}if (cache_map.size() >= max_capacity) {cache_map.erase(cache_list.back().first);cache_list.pop_back();}cache_list.emplace_front(key, value);cache_map[key] = cache_list.begin();}
};

优化方案二:读写锁版本(C++17+)

#include <shared_mutex>class UpdateCaching {// ...其他成员同基础版...mutable shared_mutex rw_mutex; // 读写锁public:int get(int key) {shared_lock<shared_mutex> lock(rw_mutex); // 共享锁// ...原有逻辑...}void put(int key, int value) {unique_lock<shared_mutex> lock(rw_mutex); // 独占锁// ...原有逻辑...}
};

优化分析说明:

  1. 线程安全实现

    • 使用std::mutex保护所有缓存操作
    • 通过lock_guard自动管理锁的生命周期
    • 读写分离版本采用shared_mutex提升读多写少场景性能
  2. 性能影响评估

    方案读并发写并发适用场景
    普通互斥锁串行串行低并发通用场景
    读写锁并行读串行写读多写少的高并发场景
  3. 异常安全

    • 所有容器操作保证基本异常安全
    • 使用RAII风格的锁管理确保不会死锁
  4. 扩展优化建议

    // 示例:分段锁优化(适用于超高并发场景)
    class SegmentedLRUCache {constexpr static int SEGMENTS = 16;array<mutex, SEGMENTS> segment_mutexes;array<UpdateCaching, SEGMENTS> segments;size_t get_segment(int key) {return hash<int>{}(key) % SEGMENTS;}
    public:int get(int key) {auto seg = get_segment(key);lock_guard<mutex> lock(segment_mutexes[seg]);return segments[seg].get(key);}// 类似实现put方法...
    };
    

建议根据实际使用场景选择优化方案:

  • 常规服务:基础互斥锁方案即可满足需求
  • 高频读取服务:升级到读写锁版本
  • 超大规模并发:考虑分段锁或无锁队列方案

需要特别注意:线程安全实现会带来约10%-30%的性能损耗,在单线程场景中可以通过编译选项禁用锁机制(通过条件编译或模板策略)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/13321.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

中小企业的采购流程,采购管理是如何进行的?

经营中小企业的&#xff0c;都明白高效采购管理的重要性。我见过不少中小企业&#xff0c;采购环节混乱无序&#xff0c;花费大量成本&#xff0c;却难以保障物资的优质供应。然而到底该如何梳理采购流程&#xff0c;怎样开展采购管理工作呢&#xff1f;这让众多中小企业主愁眉…

在线教程丨YOLO系列10年更新11个版本,最新模型在目标检测多项任务中达SOTA

YOLO (You Only Look Once) 是计算机视觉领域中最具影响力的实时目标检测算法之一&#xff0c;以其高精度与高效性深受业界青睐&#xff0c;广泛应用于自动驾驶、安防监控、医疗影像等领域。 该模型最早于 2015 年由华盛顿大学研究生 Joseph Redmon 发布&#xff0c;开创了将目…

IOPS与吞吐量、读写块大小及延迟之间的关系

IOPS&#xff08;每秒输入/输出操作次数&#xff09;、吞吐量、读写块大小及延迟是衡量存储系统性能的四个关键指标&#xff0c;它们之间存在密切的关系。以下从多个方面详细说明这些指标之间的关系&#xff1a; 1. IOPS与吞吐量的关系 公式关系&#xff1a;吞吐量&#xff0…

DeepSeek 部署过程中的问题

文章目录 DeepSeek 部署过程中的问题一、部署扩展&#xff1a;docker 部署 DS1.1 部署1.2 可视化 二、问题三、GPU 设置3.1 ollama GPU 的支持情况3.2 更新 GPU 驱动3.3 安装 cuda3.4 下载 cuDNN3.5 配置环境变量 四、测试 DeepSeek 部署过程中的问题 Windows 中 利用 ollama 来…

DeepSeek RAGFlow构建本地知识库系统

学习目标 DeepSeek RAGFlow 构建本地知识库系统 学习内容 下载安装Docker 1.1 Docker 是什么 1.2 下载Docker 1.3 安装Docker配置DockerRAGFlow 配置 3.1 下载RAGFlow 3.2 RAGFlow配置 3.3 启动RAGFlow Docker新建知识库 4.1 查看本机IP 4.2 OLLAMA_HOST 变量配置 4.3 添加模…

11 享元(Flyweight)模式

享元模式 1.1 分类 &#xff08;对象&#xff09;结构型 1.2 提出问题 做一个车管所系统&#xff0c;将会产生大量的车辆实体&#xff0c;如果每一个实例都保存自己的所有信息&#xff0c;将会需要大量内存&#xff0c;甚至导致程序崩溃。 1.3 解决方案 运用共享技术有效…

arcgis for js范围内天地图高亮,其余底图灰暗

在GIS地图开发中&#xff0c;有时我们需要突出显示某个特定区域&#xff0c;而将其他区域灰暗处理&#xff0c;以达到视觉上的对比效果。本文将介绍如何使用ArcGIS for JavaScript实现这一功能&#xff0c;具体效果为&#xff1a;在指定范围内&#xff0c;天地图高亮显示&#…

Spring AI + Ollama 实现 DeepSeek-R1 API 服务和调用

随着大语言模型的快速发展&#xff0c;越来越多的开发者开始探索如何将这些强大的推理模型本地化运行。DeepSeek-R1&#xff0c;作为一款性能卓越的开源AI模型&#xff0c;以其低成本和出色的推理能力在技术圈内引起了广泛关注。本文将详细介绍如何使用Ollama部署DeepSeek-R1&a…

Ubuntu 20.04配置网络

1&#xff0c;检查自己网络是否配通。 网络配置成功显示的网络图标 不成功的网络图标 如果看不见网络图标&#xff0c;可以使用ping命令。连接一下百度网。 ping www.baidu.com ping失败的样子 ping成功的样子 2&#xff0c;接下来进入正题&#xff0c;我们开始配置网络。 这…

ElasticSearch入门

目录 1._cat 2.索引一个 document 3.查询document 4.更新document 5.删除document 或 index 6.批量_bulk API 1._cat Get/_cat/nodes 查看所有节点 Get/_cat/indices 查看所有索引&#xff08;indices &#xff1a;index的复数) Get/_cat/master 查看…

java练习(8)

ps:题目来自力扣 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k&#xff0c;要通过此题&#xff0c;您需要执行以下操作…

Java常用类

文章目录 包装类(Wrapper)包装类的继承体系装箱和拆箱包装类与String类型的相互转换 String类创建 String 对象的两种方式String 类的常见方法案例演示 StringBuffer类类的继承体系String VS StringBufferStringBuffer构造器String 和 StringBuffer 相互转换StringBuffer 类常见…

算法设计与分析三级项目--管道铺设系统

摘 要 该项目使用c算法逻辑&#xff0c;开发环境为VS2022&#xff0c;旨在通过Prim算法优化建筑物间的连接路径&#xff0c;以支持管线铺设规划。可以读取文本文件中的建筑物名称和距离的信息&#xff0c;并计算出建筑物之间的最短连接路径和总路径长度&#xff0c;同时以利用…

【C语言系列】深入理解指针(5)

深入理解指针&#xff08;5&#xff09; 一、sizeof和strlen的对比1.1sizeof1.2strlen1.3sizeof和strlen的对比 二、数组和指针笔试题解析2.1 一维数组2.2 字符数组2.2.1代码1&#xff1a;2.2.2代码2&#xff1a;2.2.3代码3&#xff1a;2.2.4代码4&#xff1a;2.2.5代码5&#…

设计模式——策略模式

设计模式——策略模式 简单介绍一个例子 策略模式是设计模式里面比较简单的设计模式&#xff0c;其特点简单又实用&#xff0c;并且可以让你的代码看起来高大上&#xff0c;维护代码时还方便扩张 多重条件语句不易维护&#xff0c;而使用策略模式可以避免使用多重条件语句&…

【玩转 Postman 接口测试与开发2_018】第14章:利用 Postman 初探 API 安全测试

《API Testing and Development with Postman》最新第二版封面 文章目录 第十四章 API 安全测试1 OWASP API 安全清单1.1 相关背景1.2 OWASP API 安全清单1.3 认证与授权1.4 破防的对象级授权&#xff08;Broken object-level authorization&#xff09;1.5 破防的属性级授权&a…

MySQL的 MVCC详解

MVCC是多版本并发控制&#xff0c;允许多个事务同时读取和写入数据库&#xff0c;而无需互相等待&#xff0c;从而提高数据库的并发性能。 在 MVCC 中&#xff0c;数据库为每个事务创建一个数据快照。每当数据被修改时&#xff0c;MySQL不会立即覆盖原有数据&#xff0c;而是生…

【Uniapp-Vue3】z-paging插件组件实现触底和下拉加载数据

一、下载z-paing插件 注意下载下载量最多的这个 进入Hbuilder以后点击“确定” 插件的官方文档地址&#xff1a; https://z-paging.zxlee.cn 二、z-paging插件的使用 在文档中向下滑动&#xff0c;会有使用方法。 使用z-paging标签将所有的内容包起来 配置标签中的属性 在s…

UG NX二次开发(Python)-API函数介绍与应用实例(三)-UFLayer类操作

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1 前言2、UFLayer类说明3、获取当前工作图层4、移动对象到特定的图层1 前言 采用Python语言进行UG NX二次开发的帮助材料很少,采用录制的方法是一种比较容易实现的方式,但是使用UFun函数更容易上…

免费PDF 转换成 Word、PPT、Excel 格式的工具

在当今数字化办公的时代&#xff0c;文件格式的转换需求日益频繁。我们的软件应运而生&#xff0c;它是一款专业的 PDF 转换成 Word、PPT、Excel 格式的工具&#xff0c;为您的办公流程带来极大便利。 下载地址&#xff1a;https://pan.quark.cn/s/8c42ac2e4bf5 核心功能&…