设计LRU缓存

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.rhkb.cn/news/477204.html

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

相关文章

自动驾驶3D目标检测综述(三)

前两篇综述阅读理解放在这啦&#xff0c;有需要自行前往观看&#xff1a; 第一篇&#xff1a;自动驾驶3D目标检测综述&#xff08;一&#xff09;_3d 目标检测-CSDN博客 第二篇&#xff1a;自动驾驶3D目标检测综述&#xff08;二&#xff09;_子流行稀疏卷积 gpu实现-CSDN博客…

MySQL数据库学习(持续更新ing)

1. 什么是数据库&#xff1f;什么是数据库管理系统&#xff1f;什么是SQL&#xff1f;他们之间的关系是什么&#xff1f; 数据库&#xff1a;Database&#xff0c; 简称DB。按照一定格式存储数据&#xff0c;一些文件的组合。 数据库管理系统&#xff1a;DataBaseManagement&…

【线程】Java线程操作

【线程】Java线程操作 一、启动线程1.1 run()和start()的区别 二、终止线程三、等待线程四、线程的状态 一、启动线程 Java中通过start()方法来启动一个线程&#xff0c;其次我们要着重理解start()和run()的区别。 1.1 run()和start()的区别 我们通过一份代码来进行观察&…

MySQL学习/复习10视图/用户/权限/语言连接数据库

一、视图 1.1创建视图 1.2视图影响基表 1.3基表影响视图 1.4删除视图 1.5视图使用规则 二、数据库的用户 2.1mysql中的user表 注意事项&#xff1a;主机/用户名/密码/权限 2.2用户的创建 注意事项&#xff1a;设置密码与登录地点需谨慎 2.3删除用户 注意事项&#xff1a;% 2.4…

Python 中的三重引号

Python 中的三重引号&#xff0c;我之前以为只有长注释的作用&#xff0c;仔细查了下&#xff0c;原来还有给函数、类添加说明的作用。这个功能太好了&#xff0c;大大增加了代码的可读性。 具体的作用&#xff0c;总计如下。 1. 定义长字符串 其实三重引号的最直接作用是用…

rust中解决DPI-1047: Cannot locate a 64-bit Oracle Client library问题

我们在使用rust-oracle crate连接oracle进行测试的过程中&#xff0c;会发现无法连接oracle&#xff0c;测试运行过程中抛出“DPI-1047: Cannot locate a 64-bit Oracle Client library”错误。该问题是由于rust-oracle需要用到oracle的动态连接库&#xff0c;我们通过安装orac…

Python + 深度学习从 0 到 1(00 / 99)

希望对你有帮助呀&#xff01;&#xff01;&#x1f49c;&#x1f49c; 如有更好理解的思路&#xff0c;欢迎大家留言补充 ~ 一起加油叭 &#x1f4a6; 欢迎关注、订阅专栏 【深度学习从 0 到 1】谢谢你的支持&#xff01; ⭐ 什么是深度学习&#xff1f; 人工智能、机器学习与…

太通透了,Android 流程分析 蓝牙enable流程(应用层/Framework/Service层)

零. 前言 由于Bluedroid的介绍文档有限&#xff0c;以及对Android的一些基本的知识需要了(Android 四大组件/AIDL/Framework/Binder机制/JNI/HIDL等)&#xff0c;加上需要掌握的语言包括Java/C/C等&#xff0c;加上网络上其实没有一个完整的介绍Bluedroid系列的文档&#xff0…

【MySQL课程学习】:MySQL安装,MySQL如何登录和退出?MySQL的简单配置

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;MySQL课程学习 &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 MySQL在Centos 7环境下的安装&#xff1a; 卸载…

安宝特分享 | 如何利用AR技术革新医疗实践:从远程急救到多学科协作

AR技术在国内外医院的应用 在现代医疗环境中&#xff0c;患者面临的挑战依然严峻&#xff1a;看病难、看病远、看病急。这些问题不仅影响了患者的治疗效果&#xff0c;也让医务工作者倍感压力。幸运的是&#xff0c;随着增强现实&#xff08;AR&#xff09;技术的发展&#xf…

macOS 无法安装第三方app,启用任何来源的方法

升级新版本 MacOS 后&#xff0c;安装下载的软件时&#xff0c;不能在 ”安全性与隐私” 中找不到 ”任何来源” 选项。 1. 允许展示任何来源 点击 启动器 (Launchpad) – 其他 (Other) – 终端 (Terminal)&#xff1a; 打开终端后&#xff0c;输入以下代码回车&#xff1a; …

Rust中Tracing 应用指南

欢迎来到这篇全面的Rust跟踪入门指南。Rust 的tracing是一个用于应用程序级别的诊断和调试的库。它提供了一种结构化的、异步感知的方式来记录日志和跟踪事件。与传统的日志记录相比&#xff0c;tracing能够更好地处理复杂的异步系统和分布式系统中的事件跟踪&#xff0c;帮助开…

介绍一下strset(arr,ch);(c基础)

hi , I am 36 适合对象c语言初学者 strset(arr,ch)函数 功能 是将arr数组全部赋值为ch 格式 #include<string.h> strset(arr,ch); 返回值为arr 链接分享一下arr的意义(c基础)(必看)(牢记)-CSDN博客 hi I am 36.thanks for your looking .&#x1f44d;&#x1…

Web3与智能合约:区块链技术下的数字信任体系

随着互联网的不断发展&#xff0c;Web3代表着我们迈入了一个去中心化、更加安全和智能的网络时代。作为Web3的核心组成部分&#xff0c;区块链技术为智能合约的出现和发展提供了强有力的基础。智能合约不仅仅是自动化的代码&#xff0c;它们正逐步成为重塑数字世界信任体系的关…

如何更改手机GPS定位

你是否曾想过更改手机GPS位置以保护隐私、玩游戏或访问受地理限制的内容&#xff1f;接下来我将向你展示如何使用 MagFone Location Changer 更改手机GPS 位置&#xff01;无论是在玩Pokmon GO游戏、发布社媒贴子&#xff0c;这种方法都快速、简单且有效。 第一步&#xff1a;下…

青少年编程等级考试C++一级,硬币反转问题

代码 #include<iostream>using namespace std;bool a[300];int main(){ int n,m; cin >> n >> m; for(int i 1;i < m;i) { for (int j 1;j < n;j) { if( j % i 0) { a[j] !a[j];…

微信小程序技术架构图

一、视图层1.WXML&#xff08;WeiXin Markup Language&#xff09; 这是微信小程序的标记语言&#xff0c;类似于 HTML。它用于构建小程序的页面结构。例如&#xff0c;通过标签来定义各种视图元素&#xff0c;如<view>&#xff08;类似于 HTML 中的<div>&#xff…

《生成式 AI》课程 作业6 大语言模型(LLM)的训练微调 Fine Tuning -- part2

资料来自李宏毅老师《生成式 AI》课程&#xff0c;如有侵权请通知下线 Introduction to Generative AI 2024 Spring 来源背景说明 该文档主要介绍了国立台湾大学&#xff08;NTU&#xff09;2024 年春季 “生成式人工智能&#xff08;GenAI&#xff09;” 课程的作业 5&#…

gocv调用opencv添加中文乱码的解决方案

前言 相信很多做视觉的同学在使用opencv给图片添加中文文字的时候会出现这样的乱码显示: 而实际上你期望的是“告警时间:2011-11-11 11:11:11 告警类型:脱岗检测告警 Area:XXXXX Camera:Camera001-001”这样的显示内容,那么这篇文章我将用很简单的方法来解决乱码问题,只需…

【自用】常用希腊字母表

常用希腊字母表 原文链接 https://xilazimu.net/