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

高阶数据结构学习——LRU Cache

文章目录

  • 1、了解LRU Cache(Least Recently Used缩写)
  • 2、代码实现


1、了解LRU Cache(Least Recently Used缩写)

Cache是缓存,在磁盘和内存之间,内存和寄存器之间都存在,CPU和内存之间存在三级缓存,是一个三层结构。缓存用于两个速度不一致的硬件之间,提高效率用。缓存空间有限,满了以后,新数据要进入,旧数据应当怎么办?操作系统中有个热数据概念,意思是经常被使用的数据,可能放进缓存就被拿出来,再次放进后又被拿出来使用,对应的,也有很少被使用的,也就是LRU的意思,缓存满了后,新数据进来,这些很少被使用的就出去。

设计一个LRU Cache不难,设计一个高效的,任意操作都是O(1)的LRU Cache不简单,但只有这样才能满足要求。LRU Cache最主要的操作是get和put,这两个接口必须以O(1)的时间复杂度进行。

2、代码实现

看一个题

146. LRU 缓存

在这里插入图片描述
在这里插入图片描述

看在不在,可以看地址是否在缓存中。整个操作有查找,更新,新增。虽然可以用unordered_map作为缓存,做到查找,更新都O(1),但如何找到LRU?这涉及到顺序问题,还有时间问题,这里的解决办法就是用vector或list来控制LRU,比如list,在这个list里,让处于尾部就是最久未被使用的,用一个数据就把它提到头部,list<pair<int, int>> _LRUList。但这两个结合还是做不到O(1)。因为更新时无法做到O(1),更新时可以直接修改map里的数据,但在list中更新时需要先找到这个数据再放到头部,所以不是O(1)。

以上问题的解决办法是找到key时,就同时找到key对应存储数据在list中的位置。把map中value的类型换成list的迭代器,这样map[key]中存的就是一个指针,指向list中的对应的元素,如果要使用这个数据时就用指针把它拿出来,然后头插即可。

private:typedef list<pair<int, int>>::iterator LtIter;unordered_map<int, LtIter> _hashMap;list<pair<int, int>> _LRUList;
class LRUCache {
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {auto ret = _hashMap.find(key);if(ret != _hashMap.end()){//更新key对应值的位置LtIter it = ret->second;//方案1: erase + push_front 更新迭代器,原迭代器失效//方案2: list的splice接口可以转移节点_LRUList.splice(_LRUList.begin(), _LRUList, it);return ret->second->second;//第一个second对应迭代器,第二个second对应list的pair}else{return -1;}}void put(int key, int value) {//1、新增//2、更新auto ret = _hashMap.find(key);if(ret == _hashMap.end())//新增{if(_capacity == _hashMap.size()){pair<int, int> back = _LRUList.back();_hashMap.erase(back.first);_LRUList.pop_back();  }_LRUList.push_front(make_pair(key, value));_hashMap[key] = _LRUList.begin();}else//更新{LtIter it = ret->second;it->second = value;_LRUList.splice(_LRUList.begin(), _LRUList, it);}}
private:typedef list<pair<int, int>>::iterator LtIter;unordered_map<int, LtIter> _hashMap;list<pair<int, int>> _LRUList;size_t _capacity;
};

结束。

相关文章:

高阶数据结构学习——LRU Cache

文章目录 1、了解LRU Cache&#xff08;Least Recently Used缩写&#xff09;2、代码实现 1、了解LRU Cache&#xff08;Least Recently Used缩写&#xff09; Cache是缓存&#xff0c;在磁盘和内存之间&#xff0c;内存和寄存器之间都存在&#xff0c;CPU和内存之间存在三级缓…...

代码冲突解决

远程仓库修改 本地代码修改 接下来我们push一下 如果使用IDE 冲突内容如下&#xff1a; 我们可以使用自带的工具进行修改 我们选择接受自己改动的即可 如果使用git工具怎么去处理呢 远程分支是这样 本地是这样的 add和commit之后&#xff0c;再pull&#xff0c;最后pus…...

c/c++程序的内存开辟时 的内存情况

我们写的代码都是要存放在内存空间中的&#xff0c;我们经常说堆区&#xff0c;静态区&#xff0c;还有栈区&#xff0c;相信很多人不是很明白&#xff0c;在今天这篇博客中让大家对它们有一个粗略的认识 1.栈区&#xff08;static&#xff09; 在执行函数时&#xff0c;函数内…...

【linux常用命令+vi编辑器_2023.11.3】

芯片开发 Linux/Unix&#xff08;环境&#xff09; EDA工具TCL&#xff08;波形&#xff09; SVN/GIT&#xff08;版本控制&#xff09; Makefile&#xff08;脚本语言&#xff09; Perl/Python&#xff08;脚本语言&#xff09; Vim/Gvim&#xff08;编辑器&#xff09; 命令…...

okhttp post请求 header post参数加密遇到的两个问题

如果你对于网络请求用了https后是否还有必要对参数加密有疑问可以看我上篇的文章&#xff1a;网络安全https 记得耐心看完&#xff0c;下面说问题&#xff1a; Caused by: java.lang.IllegalArgumentException: Unexpected char 0x0a 一开始以为是okhttp框架对特殊字符做了现在…...

什么是Webpack的loader和plugin?它们的作用是什么?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…...

ESXi for ARM 最新下载地址

由于VMware决定关闭 flings.vmware.com 网站&#xff0c;内容被迁移到不同的地方&#xff0c;网站跳转到 Code Samples and PowerCLI Example Scripts | VMware - VMware {code} ESXi for ARM的下载地址迁移到了 https://customerconnect.vmware.com/downloads/get-download?…...

2. 网络之网络编程

网络编程 文章目录 网络编程1. UDP1.1 DatagramSocket1.1.1 DatagramSocket 构造方法1.1.2 DatagramSocket 方法&#xff1a; 1.2 DatagramPacket1.2.1 DatagramPacket构造方法1.2.2 DaragramPacket方法1.2.3InetSocketAddress API 1.3 UDP回显服务器1.3.1 框架结构1.3.2 读取请…...

工作数字化的中国历程 | 从 OA 到 BPM 到数字流程自动化

业务流程是由“活动”&#xff08;或称“工作任务”&#xff09;构成的&#xff0c;在企业里的所有工作是不是都叫流程&#xff0c;或者属于流程的一部分&#xff0c;这个概念很绕&#xff0c;我觉得没有必要去做学究气的辨析。我曾经提出过一个从工作的两个特性&#xff08;产…...

6-1 二叉排序树查找操作

description 本题要求实现二叉排序树的查找操作。 函数接口定义&#xff1a; BSTree SearchBST(BSTree T,ElemType e); 其中BSTree结构定义如下&#xff1a; typedef int ElemType; typedef struct BSTNode { ElemType data; struct BSTNode *lchild,*rchild; }BSTNode,*BS…...

服务上千家企业,矩阵通2.0重磅上线,全链路管理新媒体矩阵

自上线以来 矩阵通已服务了上千家企业级客户 覆盖汽车、家居、媒体、金融、教育等多个行业 矩阵通1.0时代 我们以“数据”为基座打造出10功能 帮助企业轻松管理新媒体矩阵 实现账号管理、数据分析、竞对监测、 人员考核、风险监管等需求 而现在 矩阵通2.0重磅上线 新增…...

【代码随想录】算法训练计划11

1、20. 有效的括号 题目&#xff1a; 给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’&#xff0c;‘}’&#xff0c;‘[’&#xff0c;‘]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。 左括号…...

Jmeter之JSR223

一、JSR223组件 JSR是Java Specification Requests的缩写,意思是Java规范提案。JSR已成为Java界的一个重要标准. JSR223其实包含了有好几种组件,但是其用法都是一致的,并且都是执行一段代码&#xff0c;主要分类如下&#xff1a; JSR223 PreProcessor JSR223 Timer JSR223 S…...

c++23中的新功能之十八新增的属性

一、c23新的属性 在前面的分析中说过&#xff0c;各种语言的发展整体思路是一致的&#xff0c;即朝着更加实用、简单和更接近自然语言的方向在前进。c23中也在不断的完善和增加相关开发的一些属性和预编译处理指令&#xff0c;这样就可以让开发者在开发的过程中对程序进行控制…...

动手学深度学习:1.线性回归从0开始实现

动手学深度学习&#xff1a;1.线性回归从0开始实现 1.手动构造数据集2.小批量读取数据集3.初始化模型参数4.定义模型和损失函数5.小批量随机梯度下降更新6.训练完整代码 1.手动构造数据集 根据带有噪声的线性模型构造一个人造数据集&#xff0c;任务是使用这个有限样本的数据集…...

【计算机网络】应用层

应用层协议原理 客户-服务器体系结构&#xff1a; 特点&#xff1a;客户之间不能直接通信&#xff1b;服务器具有周知的&#xff0c;固定的地址&#xff0c;该地址称为IP地址。 配备大量主机的数据中心常被用于创建强大的虚拟服务器&#xff1b;P2P体系结构&#xff1a; 特点&…...

python 深度学习 解决遇到的报错问题9

本篇继python 深度学习 解决遇到的报错问题8-CSDN博客 目录 一、can only concatenate str (not "int") to str 二、cant convert np.ndarray of type numpy.object_. The only supported types are: float64, float32, float16, complex64, complex128, int64, in…...

能源管理系统为什么选择零代码开发平台?

市面上有很多能源管理系统&#xff0c;但是零代码开发能源管理系统却非常少。那为什么推荐选择零代码开发平台呢&#xff1f;因为很多企业缺少技术人员&#xff0c;但是却仍然需要数字化工具和流程推进业务和项目&#xff0c;解决能源管理技术人员不懂代码的矛盾问题&#xff0…...

【LeetCode】剑指 Offer Ⅱ 第8章:树(12道题) -- Java Version

题库链接&#xff1a;https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案二叉树的深搜剑指 Offer II 047. 二叉树剪枝递归&#xff08;深搜&#xff09;&#xff1a;二叉树的后序遍历 &#xff08;⭐&#xff09;剑指 Offer II 048. 序列化和反序列化二叉树递归&…...

利用maven的dependency插件将项目依赖从maven仓库中拷贝到一个指定的位置

https://maven.apache.org/plugins/maven-dependency-plugin/copy-dependencies-mojo.html 利用dependency:copy-dependencies可以将项目的依赖从maven仓库中拷贝到一个指定的位置。 使用默认配置拷贝依赖 如果直接执行mvn dependency:copy-dependencies&#xff0c;是将项目…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...