LRU和LFU算法的简单实现
LRU
#include <iostream>
#include <unordered_map>
#include <list>
struct Node{int key;int value;Node(int key, int value):key(key),value(value){}
};
class LruCache{
private:int maxCapacity;// 最大容量std::list<Node>CacheList;// 缓存链表std::unordered_map<int, std::list<Node>::iterator>mp; // 快速找到key在链表中位置
public:LruCache(int cap):maxCapacity(cap){}int get(int key){// 找一个缓存是否在缓存链表中if(mp.find(key) == mp.end()){return -1;}auto cur = mp[key];CacheList.splice(CacheList.begin(), CacheList, cur);return cur->value;}void put(int key, int value){// 往缓存中插入一个Nodeif(mp.find(key) != mp.end()){ // key 存在时候auto cur = mp[key];cur->value = value;CacheList.splice(CacheList.begin(), CacheList, cur);return;}if(CacheList.size() == maxCapacity){// key 不存在的时候村缓存满的时候需要将CacheList中队尾的一个弹出去auto last = CacheList.back();mp.erase(last.key);CacheList.pop_back();}CacheList.insert(CacheList.begin(), Node(key, value));mp[key] = CacheList.begin(); }};
int main(){LruCache cache(3);cache.put(1, 1);cache.put(2, 2);std::cout << cache.get(1) << std::endl; // 1cache.put(3, 3);std::cout << cache.get(2) << std::endl; // -1cache.put(4, 4); std::cout << cache.get(1) << std::endl; // -1std::cout << cache.get(3) << std::endl; // 3std::cout << cache.get(4) << std::endl; // 4std::getchar();return 0;
}
LFU
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
struct CacheNode{int key;int value;int freq;// 频率CacheNode() = default;CacheNode(int key, int value, int freq):key(key),value(value),freq(freq){}bool operator < (const CacheNode& other)const{return this->freq > other.freq;}
};
class LfuCache{
public:int maxCapacity;// 维护一个key到CacheNode的一个映射std::unordered_map<int, CacheNode>keymap;// 维护一个freq到CacheNode的一个映射std::unordered_map<int, std::vector<CacheNode>>freqmap;// 维护频率的最小堆std::priority_queue<CacheNode, std::vector<CacheNode>>minheap;
public: LfuCache(int cap):maxCapacity(cap){}int get(int key){if(keymap.find(key) == keymap.end()){return -1;}auto cur = keymap[key];updateFreq(cur);return cur.value;}void put(int key, int value){if(keymap.find(key) != keymap.end()){// key存在auto cur = keymap[key];cur.value = value;updateFreq(cur);return ;}if(keymap.size() == maxCapacity){// 满了 // 删除最小频率的键CacheNode node = minheap.top();minheap.pop();freqmap[node.freq].erase(std::remove_if(freqmap[node.freq].end(),freqmap[node.freq].end(),[&](const CacheNode cur){return cur.key == node.key;}),freqmap[node.freq].end());keymap.erase(node.key);}// 插入新的键值对CacheNode node(key, value, 1);keymap[key] = node;minheap.push(node);freqmap[1].push_back(node);}// 更新缓存记录频率void updateFreq(CacheNode node) {// 从原频率表删去freqmap[node.freq].erase(std::remove_if(freqmap[node.freq].end(),freqmap[node.freq].end(),[&](const CacheNode cur){return cur.key == node.key;}),freqmap[node.freq].end());// 更新频率++node.freq;// 插入到新频率表freqmap[node.freq].push_back(node);// 更新最小堆先要将之前堆中的Node删除std::priority_queue<CacheNode, std::vector<CacheNode>>tmp;while(!minheap.empty()){auto cur = minheap.top();minheap.pop();if(cur.key != node.key){tmp.push(cur);}}minheap.swap(tmp);minheap.push(node);}
};
int main(){LfuCache cache(3);std::cout<<cache.get(1)<<std::endl;cache.put(1,1);cache.put(2,2);cache.put(3,3);cache.get(1);cache.get(2);cache.put(4,4);std::cout<<cache.minheap.size()<<std::endl;while(!cache.minheap.empty()){auto cur = cache.minheap.top();cache.minheap.pop();std::cout<<cur.key<<cur.value<<cur.freq<<std::endl;}std::getchar();
};
相关文章:
LRU和LFU算法的简单实现
LRU #include <iostream> #include <unordered_map> #include <list> struct Node{int key;int value;Node(int key, int value):key(key),value(value){} }; class LruCache{ private:int maxCapacity;// 最大容量std::list<Node>CacheList;// 缓存链…...

OCR多语言识别模型构建资料收集
OCR多语言识别模型构建 构建多语言识别模型方案 合合,百度,腾讯,阿里这四家的不错 调研多家,发现有两种方案,但是大多数厂商都是将多语言放在一个字典里,构建1w~2W的字典,训练一个可识别多种语…...
倍增的经典题目:扩大区间、st表
1. 扩大区间 P4155 [SCOI2015] 国旗计划例题1:P4155 [SCOI2015] 国旗计划 计算能覆盖整个圆圈的最少区间,题目给定的所有区间互相不包含,按区间左端点排序后,区间的右端点也是单增的。 我们首先需要化圆为线,然后贪…...
LeetCode——和为K的子数组(中等)
题目 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的连续子数组的个数 。 示例 1: 输入:nums [1,1,1], k 2 输出:2示例 2: 输入:nums [1,2,3], k 3 输出:2 题解 …...
Truncation Sampling as Language Model Desmoothing
本文是LLM系列文章,针对《Truncation Sampling as Language Model Desmoothing》的翻译。 截断采样作为语言模型的去平滑性 摘要1 引言2 背景3 截断作为去平滑性4 方法5 实验与结果6 相关工作7 结论8 不足 摘要 来自神经语言模型的长文本样本可能质量较差。截断采…...

docker安装jenkins
运行jenkins docker run -d \--name jenkins \ --hostname jenkins \-u root \-p 29090:8080 \--restart always \-v D:\springcloud\学习\jekins\jenkins\jks_home:/var/jenkins_home \ jenkins/jenkins获取root登录密码 密码在jekins_home/secrets/initalAdminPassword文件…...

学习pytorch8 土堆说卷积操作
土堆说卷积操作 官网debug torch版本只有nn 没有nn.functional代码执行结果 B站小土堆视频学习笔记 官网 https://pytorch.org/docs/stable/nn.html#convolution-layers 常用torch.nn, nn是对nn.functional的封装,使函数更易用。 卷积核从输入图像左上角…...

pytest自动化测试两种执行环境切换的解决方案
目录 一、痛点分析 方法一:Hook方法pytest_addoption注册命令行参数 1、Hook方法注解 2、使用方法 方法二:使用插件pytest-base-url进行命令行传参 一、痛点分析 在实际企业的项目中,自动化测试的代码往往需要在不同的环境中进行切换&am…...

说说TIME_WAIT和CLOSE_WAIT区别
分析&回答 TCP协议规定,对于已经建立的连接,网络双方要进行四次握手才能成功断开连接,如果缺少了其中某个步骤,将会使连接处于假死状态,连接本身占用的资源不会被释放。网络服务器程序要同时管理大量连接…...
Docker的优势
Docker是一种开源的容器化平台,提供了一种将应用程序、库和其它依赖项封装在容器中的方法。以下是Docker的基本概念和优势: 基本概念: 镜像:一个Docker镜像是一个可运行的软件包,包括应用程序、库和其它依赖项。它是D…...
C++——string使用
string的常见构造接口 string() 构造空的srting类对象,空字符串 string(const char* str) 用字符串初始化 string(const string& str)拷贝构造,使用string类初始化string(size_t n, char c) 用n个字符c初始化 string s1; string s2("hello …...

10. selenium API (二)
目录 1. 多层框架/窗口定位 2. 下拉框处理 2.1 前端界面 2.2 代码 3. 针对 alert 弹窗进行操作 3.1 前端界面 3.2 代码 4. 文件提交 4.1 前端界面 4.2 代码 5. 显示等待 6. 操作浏览器滚动条 7. 截图 8. 浏览器关闭 9. 窗口切换 在上篇文章中,我们学…...

[国产MCU]-W801开发实例-用户报文协议(UDP)数据接收和发送
用户报文协议(UDP)数据接收和发送 文章目录 用户报文协议(UDP)数据接收和发送1、UDP简单介绍2、W801的UDP创建逻辑2.1 UDP使用步骤2.2 代码实现1、UDP简单介绍 用户数据报协议 (UDP) 是一种跨互联网使用的通信协议,用于对时间敏感的传输,例如视频播放或 DNS查找。它通过在数…...

JavaScript 生成 16: 9 宽高比
这篇文章只是对 for 循环一个简单应用,没有什么知识含量。 可以跳过这篇文章。 只是我用来保存一下我的代码,保存在本地我嫌碍眼,总想把他删了。 正文部分 公式:其中 width 表示宽度,height 表示高度 16 9 w i d t…...

HTML5之drawImage函数
参数说明: drawImage(image, x, y) //按原图片大小绘制。 drawImage(image, x, y, width, height) //按指定大小绘制。 drawImage(image, sourceX, sourceY, sourceWidth, sourceHeight, destX, destY, destWidth, destHeight) //常用于图片裁剪。 其中:…...
leetcode7.整数反转-Java
题目 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。 假设环境不允许存储 64 位整数(有符号或无符号)。 7. 整数反转 - 力扣&a…...

操作系统备考学习 day2 (1.3.2 - 1.6)
操作系统备考学习 day2 计算机系统概述操作系统运行环境中断和异常的概念系统调用 操作系统体系结构操作系统引导虚拟机 计算机系统概述 操作系统运行环境 中断和异常的概念 中断的作用 CPU上会运行两种程序,一种是操作系统内核程序,一种是应用程序。…...

Django-跨域
一、基础概念 cors 跨域资源共享 二、跨域请求-简单请求 满足以下全部条件的请求为 简单请求 1.请求方法如下: GET or HEAR or POS 2.请求头仅包含如下: Accept、Accept-Language、Content-Language、Content-Type 3.ConTent-Type 仅支持如下三种&…...

wireshark抓包体验
目录 1、使用基础 1.1 数据包筛选 1.2 MAC地址筛选 1.3 端口筛选 1.4 协议筛选 1.5 包长度筛选 1.6 http请求筛选 2.数据包搜索 3.数据包还原 2、例题复现 1、使用基础 1.1 数据包筛选 ip.src 源ip地址 同理可以得到筛选目标地址: ip.dst 目的ip地址 1.2 …...

Prometheus+grafana安装配置
Prometheus安装配置 Prometheus下载地址 官方地址:Download | Prometheus 可根据系统版本下载想要的安装包,复制链接地址 wget https://github.com/prometheus/prometheus/releases/download/v2.33.3/prometheus-2.33.3.linux-amd64.tar.gzwg 解压pr…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...