1. Toy模板网首页
  2. > Toy博客

数据结构和算法专题---3、失效算法与应用

8月前 作者：斑马工 分类：Toy博客 阅读(31) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构和算法专题---3、失效算法与应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本章我们会对失效算法做个简单介绍，包括常用的失效算法（先来先淘汰（FIFO）、最久未用淘汰（LRU）、最近最少使用（LFU））的概述、实现方式、典型场景做个说明。

什么是失效算法

失效算法常见于缓存系统中。因为缓存往往占据大量内存，而内存空间是相对昂贵，且空间有限的，那么针对一部分值，就要依据相应的算法进行失效或移除操作。

先来先淘汰（FIFO）

概述

First In First Out，先来先淘汰。这种算法在每一次新数据插入时，如果队列已满，则将最早插入的数据移除。

实现

可以方便的借助LinkedList来实现：
我们借助一个案例来进行理解，可以重点关注下注释

package com.ls.cloud.sys.alg.release;

import java.util.Iterator;
import java.util.LinkedList;

public class FIFO {
    LinkedList<Integer> fifo = new LinkedList<Integer>();
    int size = 3;
    //添加元素
    public void add(int i){
        fifo.addFirst(i);
        if (fifo.size() > size){
            fifo.removeLast();
        }
        print();
    }
    //缓存命中
    public void read(int i){
        Iterator<Integer> iterator = fifo.iterator();
        while (iterator.hasNext()){
            int j = iterator.next();
            if (i == j){
                System.out.println("find it!");
                print();
                return ;
            }
        }
        System.out.println("not found!");
        print();
    }
    //打印缓存
    public void print(){
        System.out.println(this.fifo);
    }
    //测试
    public static void main(String[] args) {
        FIFO fifo = new FIFO();
        System.out.println("add 1-3:");
        // 添加1-3
        fifo.add(1);
        fifo.add(2);
        fifo.add(3);
        System.out.println("add 4:");
        // 添加4，会挤出第一个进入的1
        fifo.add(4);
        System.out.println("read 2:");
        // 读取2，进行遍历，先进来的先打印
        fifo.read(2);
        System.out.println("read 100:");
        // 读取100，进行遍历，先进来的先打印
        fifo.read(100);
        System.out.println("add 5:");
        // 添加4，会挤出第一个进入的2
        fifo.add(5);
    }
}

结果

add 1-3:
[1]
[2, 1]
[3, 2, 1]
add 4:
[4, 3, 2]
read 2:
find it!
[4, 3, 2]
read 100:
not found!
[4, 3, 2]
add 5:
[5, 4, 3]

优缺点

  • 实现非常简单
  • 不管元素的使用情况，哪怕有些数据会被频繁用到，时间最久也会被踢掉

最久未用淘汰（LRU）

概述

LRU全称是Least Recently Used，即淘汰最后一次使用时间最久远的数值。FIFO非常的粗暴，不管有没有用到，直接踢掉时间久的元素。而LRU认为，最近频繁使用过的数据，将来也很大程度上会被频繁用到，故而淘汰那些懒惰的数据。LinkedHashMap，数组，链表均可实现LRU，下面仍然以链表为例：新加入的数据放在头部，最近访问的，也移到头部，空间满时，将尾部元素删除。

实现

同样我们借助一个案例来进行理解，可以重点关注下注释

package com.ls.cloud.sys.alg.release;

import java.util.Iterator;
import java.util.LinkedList;

public class LRU {
    LinkedList<Integer> lru = new LinkedList<Integer>();
    int size = 3;
    //添加元素
    public void add(int i){
        lru.addFirst(i);
        if (lru.size() > size){
            lru.removeLast();
        }
        print();
    }
    //缓存命中
    public void read(int i){
        Iterator<Integer> iterator = lru.iterator();
        int index = 0;
        while (iterator.hasNext()){
            int j = iterator.next();
            if (i == j){
                System.out.println("find it!");
                lru.remove(index);
                lru.addFirst(j);
                print();
                return ;
            }
            index++;
        }
        System.out.println("not found!");
        print();
    }
    //打印缓存
    public void print(){
        System.out.println(this.lru);
    }
    //测试
    public static void main(String[] args) {
        LRU lru = new LRU();
        System.out.println("add 1-3:");
        // 加入1-3，顺序加入
        lru.add(1);
        lru.add(2);
        lru.add(3);
        System.out.println("add 4:");
        // 加入4，踢出1
        lru.add(4);
        System.out.println("read 2:");
        // 读取2，2移到首位，此时变为[2,4,3]
        lru.read(2);
        System.out.println("read 100:");
        // 读取100，2移到首位，此时变为[2,4,3]
        lru.read(100);
        System.out.println("add 5:");
        // 加入5，踢出最后一个3,5加入最后，[5,2,4]
        lru.add(5);
    }
}

结果

add 1-3:
[1]
[2, 1]
[3, 2, 1]
add 4:
[4, 3, 2]
read 2:
find it!
[2, 4, 3]
read 100:
not found!
[2, 4, 3]
add 5:
[5, 2, 4]

优缺点

  • 性能较高
  • 对于偶发性、周期性的数据没有良好的抵抗力，很容易就形成缓存的污染，影响命中率

最近最少使用（LFU）

概述

Least Frequently Used，即最近最少使用。它要淘汰的是最近一段时间内，使用次数最少的值。可以认为比LRU多了一重判断。LFU需要时间和次数两个维度的参考指标。需要注意的是，两个维度就可能涉及到同一时间段内，访问次数相同的情况，就必须内置一个计数器和一个队列，计数器算数，队列放置相同计数时的访问时间。

实现

package com.ls.cloud.sys.alg.release;

public class Dto implements Comparable<Dto> {
    private Integer key;
    private int count;
    private long lastTime;

    public Dto(Integer key, int count, long lastTime) {
        this.key = key;
        this.count = count;
        this.lastTime = lastTime;
    }

    @Override
    public int compareTo(Dto o) {
        int compare = Integer.compare(this.count, o.count);
        return compare == 0 ? Long.compare(this.lastTime, o.lastTime) : compare;
    }

    @Override
    public String toString() {
        return String.format("[key=%s,count=%s,lastTime=%s]",key,count,lastTime);
    }

    public Integer getKey() {
        return key;
    }

    public void setKey(Integer 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;
    }
}

package com.ls.cloud.sys.alg.release;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class LFU {
    private final int size = 3;

    private Map<Integer,Integer> cache = new HashMap<>();

    private Map<Integer, Dto> count = new HashMap<>();

    //投放
    public void put(Integer key, Integer value) {
        Integer v = cache.get(key);
        if (v == null) {
            if (cache.size() == size) {
                removeElement();
            }
            count.put(key, new Dto(key, 1, System.currentTimeMillis()));
        } else {
            addCount(key);
        }
        cache.put(key, value);
    }
    //读取
    public Integer get(Integer key) {
        Integer value = cache.get(key);
        if (value != null) {
            addCount(key);
            return value;
        }
        return null;
    }

    //淘汰元素
    private void removeElement() {
        Dto dto  = Collections.min(count.values());
        cache.remove(dto.getKey());
        count.remove(dto.getKey());
    }

    //更新计数器
    private void addCount(Integer key) {
        Dto Dto = count.get(key);
        Dto.setCount(Dto.getCount()+1);
        Dto.setLastTime(System.currentTimeMillis());
    }
    //打印缓存结构和计数器结构
    private void print(){
        System.out.println("cache="+cache);
        System.out.println("count="+count);
    }



    public static void main(String[] args) {
        LFU lfu = new LFU();

        //前3个容量没满，1,2,3均加入
        System.out.println("add 1-3:");
        lfu.put(1, 1);
        lfu.put(2, 2);
        lfu.put(3, 3);
        lfu.print();

        //1,2有访问，3没有，加入4，淘汰3
        System.out.println("read 1,2");
        lfu.get(1);
        lfu.get(2);
        lfu.print();
        System.out.println("add 4:");
        lfu.put(4, 4);
        lfu.print();

        //2=3次，1,4=2次，但是4加入较晚，再加入5时淘汰1
        System.out.println("read 2,4");
        lfu.get(2);
        lfu.get(4);
        lfu.print();
        System.out.println("add 5:");
        lfu.put(5, 5);
        lfu.print();

    }
}

add 1-3:
cache={1=1, 2=2, 3=3}
count={1=[key=1,count=1,lastTime=1701744406838], 2=[key=2,count=1,lastTime=1701744406838], 3=[key=3,count=1,lastTime=1701744406838]}
read 1,2
cache={1=1, 2=2, 3=3}
count={1=[key=1,count=2,lastTime=1701744406944], 2=[key=2,count=2,lastTime=1701744406944], 3=[key=3,count=1,lastTime=1701744406838]}
add 4:
cache={1=1, 2=2, 4=4}
count={1=[key=1,count=2,lastTime=1701744406944], 2=[key=2,count=2,lastTime=1701744406944], 4=[key=4,count=1,lastTime=1701744406946]}
read 2,4
cache={1=1, 2=2, 4=4}
count={1=[key=1,count=2,lastTime=1701744406944], 2=[key=2,count=3,lastTime=1701744406947], 4=[key=4,count=2,lastTime=1701744406947]}
add 5:
cache={2=2, 4=4, 5=5}
count={2=[key=2,count=3,lastTime=1701744406947], 4=[key=4,count=2,lastTime=1701744406947], 5=[key=5,count=1,lastTime=1701744406948]}

优缺点

  • LFU也能够有效的保护缓存，相对场景来说，比LRU有更好的缓存命中率。由于是以次数为基准，因此更加准确，天然能有效的保证和提升命中率。

  • 由于LFU须要记录数据的访问频率，所以需要额外的空间；当访问模式改变的时候，算法命中率会急剧降低，这也是他最大弊端。

应用场景

redis属于缓存失效的典型应用场景，常见策略如下：文章来源地址https://www.toymoban.com/news/detail-756202.html

  • noeviction: 不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息（ 比较危险）。
  • allkeys-lru：对所有key，优先删除最近最少使用的 key (LRU)。
  • allkeys-random： 对所有key， 随机删除一部分（听起来毫无道理）。
  • volatile-lru：只限于设置了 expire 的key，优先删除最近最少使用的key (LRU)。
  • volatile-random：只限于设置了 expire 的key，随机删除一部分。
  • volatile-ttl：只限于设置了 expire 的key，优先删除剩余时间(TTL) 短的key。

到了这里，关于数据结构和算法专题---3、失效算法与应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 队列（Queue）：先进先出（FIFO）的数据结构

    队列（Queue）：先进先出（FIFO）的数据结构

    队列是一种基本的数据结构，用于在计算机科学和编程中管理数据的存储和访问。队列遵循先进先出（First In, First Out，FIFO）原则，即最早入队的元素首先出队。这种数据结构模拟了物理世界中的队列，如排队等待服务的人。 在本篇博客中，我们将详细介绍队列的概念、用途

    2024年02月05日
    浏览(39)
  • 深入了解队列：探索FIFO数据结构及队列

    深入了解队列：探索FIFO数据结构及队列

    之前介绍了栈：探索栈数据结构：深入了解其实用与实现（c语言实现栈） 那就快马加鞭来进行队列内容的梳理。队列和栈有着截然不同的工作方式，队列遵循先进先出（FIFO）的原则，在许多场景下都表现出强大的效率和实用性 源码可以来我的github进行查找：Nerosts/just-a-tr

    2024年02月03日
    浏览(32)

  • 数据结构与算法--哈夫曼树应用

    第1关：统计报文中各个字符出现的次数 任务描述 本关任务： 给定一串文本，统计其中各个字符出现的次数； 测试说明 平台会对你编写的代码进行测试： 测试输入：` abcdeabcdeabcdabcdabcdabcbccc 预期输出： a 6 b 7 c 9 d 5 e 2 代码： 第2关：对第一关报文中的各个字符进行哈夫曼编

    2024年02月06日
    浏览(36)
  • 【数据结构和算法】---二叉树（2）--堆的实现和应用

    【数据结构和算法】---二叉树（2）--堆的实现和应用

    如果有一个数字集合，并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ，且在逻辑结构（即二叉树）中，如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ；那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(33)
  • 数据结构与算法课程设计---最小生成树的应用

    数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题，有11个城市，城市之间有一些天然气管道，铺设天然气管道需要花费不同的金额，现在要你选择其中一些天然气管道，使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图，每个城市是一个顶点，城市与城市之间的管道是

    2024年02月08日
    浏览(37)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢，每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号，而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(51)

  • 数据结构专题2

    1. Cube - HDU 3584 三维的空间中有 n n n 个元素，初始时每个空间元素均为0。更新操作是0变1，1变0，是一个立方体型区域内的所有元素都更新。然后查询是问某个点的元素是0还是1. ( 1 = n = 100 , m = 10000 1=n=100, m =10000 1 = n = 100 , m = 10000 ) 三维树状数组，维护三维差分数组，所有加法

    2024年02月16日
    浏览(23)
  • 数据结构——顺序表专题

    数据结构——顺序表专题

    什么是数据结构 数据结构是由“数据”和“结构”两词组合而来的。 数据：常见的数值、网页中肉眼可见的信息，这些都是数据。 结构：当我们想要使用大量同一类型的数据时，通过手动定义大量的独立的遍历对于程序来说，可读性非常差，我们可以借助数组这样的数据结

    2024年02月21日
    浏览(22)
  • 数据结构 | 单链表专题【详解】

    数据结构 | 单链表专题【详解】

    顺序表遗留下来的问题 中间/头部的插⼊删除，时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后⾯没有数据插入了

    2024年02月06日
    浏览(30)

  • 数据结构的应用场景：如社交网络、路由算法、图论、网络协议等

    作者：禅与计算机程序设计艺术 数据结构（Data Structure）是计算机科学中存储、组织、管理数据的方式，主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构，以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包