[C++][数据结构][LRU Cache]详细讲解
目录
- 1.什么是LRU Cache?
- 2.LRU Cache实现
1.什么是LRU Cache?
- LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。
- 什么是 Cache?
- 狭义的Cache指的是位于CPU和主存间的快速RAM
- 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术
- 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构
- 除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache ── 称为Internet临时文件夹或网络内容缓存等
- 狭义的Cache指的是位于CPU和主存间的快速RAM
- Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容
- LRU Cache的替换原则就是将最近最少使用的内容替换掉
- 其实,LRU译成最久未使用会更形象,因为该算法每次替换掉的就是一段时间内最久没有使用过的内容
2.LRU Cache实现
-
实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的Put和Get,那么使用双向链表和哈希表的搭配是最高效和经典的
- 双向链表是因为双向链表可以实现任意位置O(1)的插入和删除
- 哈希表是因为哈希表的增删查改也是O(1)
-
关键:找到key,就要找到key对应存储数据在list中的位置

class LRUCache
{
public:LRUCache(int capacity): _capacity(capacity){}int Get(int key){auto ret = _hashMap.find(key);if (ret != _hashMap.end()){LtIter it = ret->second;// 更新key对应值的位置,splice转移结点_LRUList.splice(_LRUList.begin(), _LRUList, it);return it->second;}else{return -1;}}void Put(int key, int value){auto ret = _hashMap.find(key);if (ret == _hashMap.end()) // 1.新增{if (_hashMap.size() == _capacity){// 若满,则先删除LRU的数据pair<int, int> back = _LRUList.back();_hashMap.erase(back.first);_LRUList.pop_back();}_LRUList.push_front({ key, value });_hashMap[key] = _LRUList.begin();}else // 2.更新{LtIter it = ret->second;it->second = value; // 更新// 更新key对应值的位置,splice转移结点_LRUList.splice(_LRUList.begin(), _LRUList, it);}}
private:typedef list<pair<int, int>>::iterator LtIter;// hash做到查找更新是O(1),value值存的是list的iteratorunordered_map<int, LtIter> _hashMap;// LRU,假设尾部数据就是最近最少用list<pair<int, int>> _LRUList;size_t _capacity;
};
相关文章:
[C++][数据结构][LRU Cache]详细讲解
目录 1.什么是LRU Cache?2.LRU Cache实现 1.什么是LRU Cache? LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。什么是 Cache? 狭义的Cache指的是位于CPU和主存间的快速RAM 通常它不像系统…...
怎样激励员工积极应用新版FMEA培训后的知识?
在快节奏的职场环境中,新版FMEA(失效模式与影响分析)的培训无疑是提升员工技能、优化工作流程的重要一环。然而,如何让员工积极地将所学知识应用于实际工作中,却是一个值得深入探讨的问题。下面,深圳天行健…...
WDF驱动开发-WDF总线枚举(一)
支持在总线驱动程序中进行 PnP 和电源管理 某些设备永久插入系统,而其他设备可以在系统运行时插入和拔出电源。 总线驱动 必须识别并报告连接到其总线的设备,并且他们必须发现并报告系统中设备的到达和离开情况。 总线驱动程序标识和报告的设备称为总线…...
React useEffect 执行时机
默认情况下,Effect 在每次渲染(包括初始渲染)后运行。 如果 React 的所有依赖项都与上次渲染时的值相同,则将跳过本次 Effect。 useEffect(() > {// 这里的代码会在每次渲染后执行 });useEffect(() > {// 这里的代码只会在…...
centos7 根目录扩容
1、先检查一下磁盘空间 [rootlocalhost ~]# lsblk 二、使用fdisk创建新分区 [rootlocalhost ~]# fdisk /dev/vdb 1、输入 p ,查看当前分区表; 2、输入 n ,新建一个分区; 3、再输入 p ,选择分区类型为主分区&#x…...
为什么要做Redis分区和分片
Redis分区(Partitioning)和分片(Sharding)是将数据分布在多个Redis实例或多个节点上的做法。这种技术用于提高性能、可扩展性和可用性。以下是执行Redis分区和分片的主要原因: 1. **提高吞吐量**: - 通…...
电脑不小心删除的文件怎么恢复?4个必备恢复方法!
“刚刚在对电脑里的某些垃圾文件进行清理时,我一不小心误删了比较重要的数据。这些误删的数据还有机会恢复吗?希望大家帮帮我,非常感谢!” 在这个数字化飞速发展的时代,电脑早已成为我们日常生活和工作中不可或缺的一部…...
GPTCache:革新大模型缓存,降低成本,提升效率
GPTCache介绍 随着应用程序越来越受欢迎并遇到更高的流量水平,与 LLM API 调用相关的费用可能会变得相当可观。此外,LLM 服务的响应时间可能会很慢,尤其是在处理大量请求时。GPTCache是一个致力于构建用于存储 LLM 响应的语义缓存的项目。 项目架构 数字人助力传统客服 1…...
[Day 15] 區塊鏈與人工智能的聯動應用:理論、技術與實踐
區塊鏈的數字身份認證 1. 概述 數字身份認證是當今數字世界中的關鍵問題之一。傳統的身份驗證方法面臨著安全性、隱私性和可信度等方面的挑戰。區塊鏈技術通過其去中心化、不可篡改和可追溯的特性,為解決這些問題提供了新的可能性。本文將深入探討區塊鏈在數字身份…...
绘唐3下载地址
小说推文是一种将小说内容以推文的形式发布的方式,可以吸引更多读者的关注。以下是一些小说推文工具:下载地址 Twitter:Twitter是一个非常受欢迎的社交媒体平台,适合发布小说推文。你可以使用Twitter的140个字符限制来创造悬念和吸…...
两个基因相关性细胞系(CCLE)(升级)
目录 单基因CCLE数据 ①细胞系转录组CCLE数据下载 ②单基因泛癌表达 CCLE两个基因相关性 ①进行数据整理 ②相关性分析 单基因CCLE数据 ①细胞系转录组CCLE数据下载 基因在各个细胞系表达情况_ccle expression 23q4-CSDN博客 rm(list = ls()) library(tidyverse) libra…...
2024全国各地高考录取分数线一览表(含一本、二本、专科)
2024年高考录取分数线陆续公布,上大学网(www.sdaxue.com)为大家整理全国31个省市高考录取分数线汇总,包括本科批、专科批和特殊类招生控制分数线汇总,来看看你的省份多少分能上大学吧。 一、2024年全国高考录取线一览表 1、宁夏 一本线&…...
汇编快速入门
一.基础知识 1.数据类型 DB(Define Byte,字节类型 占位8位bit 1字节) 范围:DB可以用来定义(无符号、有符号)整数(包含二、十、十六进制)和字符 语法:a DB 数据个数…...
Apache Tomcat 10.1.25 新版本发布 java 应用服务器
Tomcat 是一个小型的轻量级应用服务器,在中小型系统和并发访问用户不是很多的场合下被普遍使用,是开发和调试 JSP 程序的首选。对于一个初学者来说,可以这样认为,当在一台机器上配置好 Apache 服务器,可利用它响应对 H…...
数据类型 运算符
基本数据类型与引用数据类型的区分 存储内容: 基本数据类型:直接存储实际的数据值,如整数、浮点数、字符等。引用数据类型:存储对象的引用(内存地址),而不是对象本身。 内存分配: 基…...
WordPress网创自动采集并发布插件
网创教程:WordPress插件网创自动采集并发布 阅读更新:随机添加文章的阅读数量,购买数量,喜欢数量。 使用插件注意事项 如果遇到404错误,请先检查并调整网站的伪静态设置,这是最常见的问题。需要定制化服…...
(十三)、MQTT3.1.1-MQTT服务端数据结构设计
为进一步实现一个简易的MQTT服务端,做如下服务端数据结构设计。 1、服务端协议相关的函数 连接 rx_connect() 接收连接请求 Socket中监听,通过第一个字节switch,根据数据创建client对象 tx_connectack() 回复连接响应 处理完成rx_conn…...
StackOverFlowError常见原因及解决方法总结
StackOverFlowError常见原因及解决方法总结 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们来探讨一下 Java 中一个常见的错误:StackOverFl…...
【安全】Linux Fanotify使用入门
1 Fanotify vs Inotify 在实现某些功能时,可能需要获取某个文件执行的操作,一种可能的方案是用Audit的路径监控,但是Audit存在性能和内核稳定性问题,这个时候就可以其他的文件变更检测机制。 inotify可以监控文件被创建、修改和…...
java的输出流File OutputStream
一、字节输出流FileOutput Stream 1、定义 使用OutputStream类的FileOutput Stream子类向文本文件写入的数据。 2.常用构造方法 3.创建文件输出流对象的常用方式 二、输出流FileOutputStream类的应用示例 1.示例 2、实现步骤 今天的总结就到此结束啦,拜拜&#x…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
