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…...

华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...