算法之美：缓存数据淘汰算法分析及分解实现

2024-04-07 08:52
文章标签 算法 分析 实现 淘汰 分解 之美 缓存数据

本文主要是介绍算法之美：缓存数据淘汰算法分析及分解实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        在设计一个系统的时候，由于数据库的读取速度远小于内存的读取速度，那么为加快读取速度，需先将一部分数据加入到内存中（该动作称为缓存），但是内存容量又是有限的，当缓存的数据大于内存容量时，就需要删除一部分数据，以加入新的数据。这时候需要设计一种淘汰机制，计算出哪些数据删除，哪些数据保留，常见的淘汰算法有FIFO、LRU、LFU等淘汰算法，接下来我们将一一讲解及实现。

FIFO淘汰算法

        First In First Out，先进先出，淘汰最早被缓存的对象，是一种常用的缓存淘汰算法，它的原理是按照先进先出的原则，当缓存满了之后，先将最早进入缓存的数据淘汰掉，以腾出空间给新的数据，其优点在于实现简单，不需要记录或统计数据的使用次数，只需要记录每个数据进入缓存的时间和每个数据在缓存中的位置即可。
        其缺点也是明显的,它不能有效地淘汰最近最少使用的数据，最近最多使用的数据也可能被淘汰掉，这样就会导致缓存的效率不够高。

public class FIFOCache<K, V> {// 定义缓存的最大容量private  int maxSize;// 定义当前缓存的容量private int curSize;// 用于存放缓存的keyprivate  LinkedList<K> cacheKey;// 用于存放缓存的valueprivate  HashMap<K, V> cacheValue;// 读写锁，保证线程安全private Lock lock = new ReentrantLock();// 构造函数public FIFOCache(int maxSize) {this.maxSize = maxSize;this.curSize = 0;this.cacheKey = new LinkedList<K>();this.cacheValue = new HashMap<K, V>();}// 向缓存插入key-valuepublic void put(K key, V value) {// 加锁保证线程安全lock.lock();try {// 如果缓存已满，则删除最老的keyif (curSize == maxSize) {K oldKey = cacheKey.removeFirst();cacheValue.remove(oldKey);curSize--;}// 插入key-valuecacheKey.addLast(key);cacheValue.put(key, value);curSize++;} finally {// 释放锁lock.unlock();}}// 查询指定key的valuepublic V get(K key) {return cacheValue.get(key);}public void printKeys() {System.out.println(this.cacheKey.toString());}public static void main(String[] args) {FIFOCache cache = new FIFOCache<String, String>(5);cache.put("A", "数据结构篇：深度剖析LSM及与B+树优劣势分析");cache.put("B", "数据结构篇：深度剖析跳跃表及与B+树优劣分析");cache.put("C", "算法之美：堆排序原理剖析及应用案例分解实现");cache.printKeys();cache.put("D", "算法之美：二叉堆原理剖析及堆应用案例讲解及实现");cache.printKeys();Object cacheObj1 = cache.get("A");System.out.println("cacheObj1=" + cacheObj1);Object cacheObj2 = cache.get("C");System.out.println("cacheObj2=" + cacheObj2);}}

LRU最久未使用算法

        Least Recently Used 淘汰算法以时间作为参考，淘汰最长时间未被使用的数据，设计者认为如果数据最近被访问过，那么将来被访问的几率也更高；当内存满后会优先淘汰最长时间没有被使用的元素（都没人要你了，不淘汰你淘汰谁）
        其基本原理就是在缓存满时，将最近最久未使用的数据淘汰出缓存，以便给新的数据留出空间。实现方式可以用：数组、链表等方式，新插入的数据放在头部，最近访问过的也移到头部，空间满时将尾部元素删除。


public class LRUCache {//用于存储key-value数据private HashMap<String, String> map;//用于存储key的顺序private ArrayList<String> list;//数组的容量private int capacity;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();list = new ArrayList<>();}/*** 查询key对应的value* @param key 键* @return value 值*/public String get(String key) {//如果key存在，则将key移动到最前端if (map.containsKey(key)) {list.remove(key);list.add(0, key);return map.get(key);}return null;}/*** 向缓存中插入key-value* @param key 键* @param value 值*/public void put(String key, String value) {//如果key存在，则将key移动到最前端if (map.containsKey(key)) {list.remove(key);list.add(0, key);map.put(key, value);} else {//如果key不存在，则添加key-valueif (list.size() >= capacity) {//如果容量已满，则删除最后一个keyString lastKey = list.get(list.size() - 1);list.remove(lastKey);map.remove(lastKey);}list.add(0, key);map.put(key, value);}}public void showList(){System.out.println(list.toString());}public static void main(String[] args) {LRUCache cache = new LRUCache(5);cache.put("A", "数据结构篇：深度剖析LSM及与B+树优劣势分析");cache.put("B", "数据结构篇：深度剖析跳跃表及与B+树优劣分析");cache.put("C", "算法之美：堆排序原理剖析及应用案例分解实现");cache.put("D", "海量数据项目大课是营销短链平台项目");cache.put("E", "算法之美：二叉堆原理剖析及堆应用案例讲解及实现");cache.showList();Object cacheObj2 = cache.get("C");System.out.println("cacheObj2=" + cacheObj2);//C被访问，被放置头部cache.showList();cache.put("F", "算法之美：B+树原理、应用及Mysql索引底层原理剖析");//新增了F，超过大小，A由于在尾部，被删除，F被放置头部cache.showList();//G节点不存在，所以不影响顺序Object cacheObj1 = cache.get("G");System.out.println("cacheObj1=" + cacheObj1);cache.showList();}
}

LFU最近最少使用算法

        Least Frequently Used 最近最少使用，增加次数作为参考，淘汰一定时期内被访问次数最少的数据。设计者认为如果数据过去被访问多次，那么将来被访问的频率也更高，比LRU多了一个频次统计，需要时间和次数两个维度进行判断是否淘汰。新加入数据插入到队列尾部，需要将引用计数初始值为 1，当队列中的数据被访问后，对应的元素引用计数 +1，队列按【次数】重新排序，如果相同次数则按照时间排序，当需要淘汰数据时，将排序的队列末尾的数据删除，即访问次数最少。

public class LFUCache {//定义缓存容量private  int capacity ;//存储key valueprivate Map<String,String> cache ;//存储key的使用频次private Map<String, CacheObj> count;public LFUCache(int capacity){this.capacity = capacity;cache =  new HashMap<>();count =  new HashMap<>();}//存储public void put(String key, String value) {}//读取public String get(String key) {}//删除元素private void removeElement() {}//更新相关统计频次和时间private void addCount(String key) {}public void showInfo(){System.out.println(cache.toString());System.out.println(count.toString());}class CacheObj implements Comparable<CacheObj>{private String key;private int count;private long lastTime;public String getKey() {return key;}public void setKey(String key) {this.key = key;}public int getCount() {return count;}public void setCount(int count) {this.count = count;}public long getLastTime() {return lastTime;}public void setLastTime(long lastTime) {this.lastTime = lastTime;}public CacheObj(String key, int count, long lastTime) {this.key = key;this.count = count;this.lastTime = lastTime;}//用于比较大小，如果使用次数一样，则比较时间大小@Overridepublic int compareTo(CacheObj o) {int value = Integer.compare(this.count, o.count);return value == 0 ? Long.compare(this.lastTime, o.lastTime) : value;}@Overridepublic String toString() {return "CacheObj{" +"key=" + key +", count=" + count +", lastTime=" + lastTime +'}';}}
}
public class LFUCache {//定义缓存容量private  int capacity ;//存储key valueprivate Map<String,String> cache ;//存储key的使用频次private Map<String, CacheObj> count;public LFUCache(int capacity){this.capacity = capacity;cache =  new HashMap<>();count =  new HashMap<>();}//存储public void put(String key, String value) {String cacheValue = cache.get(key);if (cacheValue == null) {//新元素插入，需要判断是否超过缓存容量大小if (cache.size() == capacity) {removeElement();}count.put(key, new CacheObj(key, 1, System.currentTimeMillis()));} else {addCount(key);}cache.put(key, value);}//读取public String get(String key) {String value = cache.get(key);if (value != null) {addCount(key);return value;}return null;}//删除元素private void removeElement() {CacheObj cacheObj  = Collections.min(count.values());cache.remove(cacheObj.getKey());count.remove(cacheObj.getKey());}//更新相关统计频次和时间private void addCount(String key) {CacheObj cacheObj = count.get(key);cacheObj.setCount(cacheObj.getCount()+1);cacheObj.setLastTime(System.currentTimeMillis());}public void showInfo(){System.out.println(cache.toString());System.out.println(count.toString());}class CacheObj implements Comparable<CacheObj>{private String key;private int count;private long lastTime;public CacheObj(String key, int count, long lastTime) {this.key = key;this.count = count;this.lastTime = lastTime;}//用于比较大小，如果使用次数一样，则比较时间大小@Overridepublic int compareTo(CacheObj o) {int value = Integer.compare(this.count, o.count);return value == 0 ? Long.compare(this.lastTime, o.lastTime) : value;}@Overridepublic String toString() {return "CacheObj{" +"key=" + key +", count=" + count +", lastTime=" + lastTime +'}';}}
}
public static void main(String[] args) {LFUCache cache = new LFUCache(2);cache.put("A", "数据结构篇：深度剖析LSM及与B+树优劣势分析");cache.put("A", "数据结构篇：深度剖析跳跃表及与B+树优劣分析");cache.showInfo();System.out.println("---------");String cacheValue = cache.get("A");System.out.println(cacheValue);cache.showInfo();System.out.println("---------");cache.put("B", "算法之美：堆排序原理剖析及应用案例分解实现");cache.put("B", "算法之美：二叉堆原理剖析及堆应用案例讲解及实现");cache.showInfo();System.out.println("---------");//插入新元素，由于A的count是3，B的count是2，所以淘汰了Bcache.put("C","算法之美：B+树原理、应用及Mysql索引底层原理剖析");cache.showInfo();
}

这篇关于算法之美：缓存数据淘汰算法分析及分解实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/882150。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2