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

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。

相关文章

Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
MySQL 内存使用率常用分析语句

MySQL 内存使用率常用分析语句

《MySQL内存使用率常用分析语句》用户整理了MySQL内存占用过高的分析方法,涵盖操作系统层确认及数据库层bufferpool、内存模块差值、线程状态、performance_schema性能数据... 目录一、 OS层二、 DB层1. 全局情况2. 内存占js用详情最近连续遇到mysql内存占用过高导致
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
深度解析Nginx日志分析与499状态码问题解决

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
Spring Security 单点登录与自动登录机制的实现原理

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录（SSO）与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录（SSO）1.2 自动登录（Remember Me）二、代码分析三、
阅读更多...
PyCharm中配置PyQt的实现步骤

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q
阅读更多...
Python实现批量提取BLF文件时间戳

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF（BinaryLoggingFormat）作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析：从文件遍历到数据导出1. 环境准备与依赖库
阅读更多...
linux下shell脚本启动jar包实现过程

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2