当前位置: 首页 > news >正文

【算法】FIFO先来先淘汰算法分析和编码实战

  • 背景

    • 在设计一个系统的时候,由于数据库的读取速度远小于内存的读取速度

    • 为加快读取速度,将一部分数据放到内存中称为缓存,但内存容量是有限的,当要缓存的数据超出容量,就需要删除部分数据

    • 这时候需要设计一种淘汰机制,看哪些数据删除,哪些数据保留

    • 常见的有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 (maxSize == curSize) {K oldKey = cacheKey.removeFirst();cacheValue.remove(oldKey);curSize--;}//插入新的key-valuecacheKey.add(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<String,String> cache = new FIFOCache<>(5);cache.put("A", "任务A");cache.put("B", "任务B");cache.put("C", "任务C");cache.put("D", "任务D");cache.put("E", "任务E");cache.printKeys();cache.put("F", "任务F");cache.printKeys();System.out.println("G=" + cache.get("G"));System.out.println("C=" + cache.get("C"));}}

在这里插入图片描述

http://www.lryc.cn/news/42401.html

相关文章:

  • 二分查找——我欲修仙(功法篇)
  • Python 多线程
  • JVM笔记(九)选择合适的垃圾收集器
  • 二维图像处理到三维点云处理
  • leetcode 删除有序数组中的重复项
  • JVM学习.03 类加载机制
  • Celery使用:优秀的python异步任务框架
  • 第十四届蓝桥杯三月真题刷题训练——第 19 天
  • 类和对象 - 下
  • 【云原生】Linux基础IO(文件理解与操作)
  • CentOS 7 安装 mysql 8.0 客户端
  • Ubuntu下载、配置、安装和编译opencv
  • 第七讲 贪心
  • 数字藏品的未来及发展趋势
  • 值得记忆的STL常用算法,分分钟摆脱容器调用的困境,以vector为例,其余容器写法类似
  • java如何手动导jar包
  • 怎么防止SQL注入?
  • 【千题案例】TypeScript获取两点之间的距离 | 中点 | 补点 | 向量 | 角度
  • 堆叠注入--攻防世界CTF赛题学习
  • STM32 ADC+定时器+DMA+FFT
  • 用Node.js实现一个HTTP服务器程序(文件服务器)
  • Python实现人脸识别检测, 对美女主播照片进行评分排名
  • 【数据结构与算法】什么是双向链表?并用代码手动实现一个双向链表
  • 23种设计模式
  • 20美刀一个月的ChatGPT架构师,性价比逆天了
  • 海门区教育科学规划课题2020年度成果鉴定书
  • 大数据专业应该怎么学习
  • 学习黑客十余年,如何成为一名高级的安全工程师?
  • 【算法】手把手学会二分查找
  • SVO、vinsmono、 OKVIS系统比较