LRU的原理与实现(java)

介绍

LRU的英文全称为Least Recently Used,即最近最少使用。它是一种内存数据淘汰算法,当添加想要添加数据而内存不足时,它会优先将最近一段时间内使用最少的数据淘汰掉,再将数据添加进来。

原理

LRU的原理在介绍中就已经基本说明过了,就是在内存不够用时把最近最少使用的数据淘汰掉,

那么它为什么会这么进行淘汰呢?其主要思想是最近时间内使用的比较多的数据数据在后面的使用中就大概率还会被被使用,而最近使用比较少的数据在后面被使用的概率就比较低。使用这样的淘汰算法,在访问内存时就可以提高内存的命中率,提高整体系统的速度。

下面来举个例子。假设内存中只能存4个数据。我们依次添加了1,2,3,4这4个数据,在添加完后我访问了3和1,随后我继续添加数据,加入一个5,那么此时淘汰的数据为2,因为1和3最近已经使用过了,2时最近一段时间内使用最少的数据。流程如下:

实现

想要使用程序来实现一个简单的LRU算法可以使用单链表。将一个单链表看成我们的内存,每次有数据进来时就在头部添加进来,淘汰时就将单链表尾部的最后一个节点淘汰。当每次访问时就把访问的节点移动到头节点。

首先定义链表节点的结构

    //定义单链表
    public static class Node{
        int val;
        Node next;
        Node(){};
        Node(int val){
            this.val=val;
        };
        Node(int val,Node next){
            this.val = val;
            this.next = next;
        }
    }

随后定义链表的最大容量,和链表的根节点和当前链表中的节点数

    public static int size = 4;
    public static int curSize = 0;
    public static Node root=new Node(0);

再编写向链表添加节点的方法

分为三种情况

情况一:链表未满,那么这就将该节点插入到链表的头部,并将curSize加一。

情况二:添加的节点时链表已满,此时需要我们将链表的最后一个节点淘汰掉,然后该节点插入头部。

    /**
     * 向链表中添加
     * @param val
     */
    public static void LRUAdd(int val){
        if(curSize==0){
            Node node = new Node(val);
            root.next = node ;
            curSize++;
        }
        //链表已满
        else if(curSize==size){
            Node node = new Node(val);
            node.next = root.next;
            root.next = node;
            Node pre = null;
            Node cur = root;
            while (cur.next!=null){
                pre = cur;
                cur=cur.next;
            }
            pre.next = null;
        }else {
            Node node = new Node(val);
            node.next = root.next;
            root.next = node;
            curSize++;
        }
    }

随后编写访问节点的方法,访问某节点时会将该节点直接移动到链表头部。

    public static void LRUGet(int val){
        Node node = root.next;
        Node pre = root;
        while(node!=null){
            if(node.val==val){
                break;
            }
            pre = node;
            node=node.next;
        }
        if(node.next==null){
            Node node1 = new Node();
            node1.next = node;
            node.next = root.next;
            root.next = node;
            pre.next = null;

        }else {
            pre.next = node.next;
            node.next = root.next;
            root.next = node;
        }
        node.toString();
    }

测试例子中的数据:

先添加12345这5个数据,再访问3和2,最后再添加6

可以看到我们成功实现了LRU算法

完成代码

public class Lru {

    public static int size = 4;
    public static int curSize = 0;
    public static Node root=new Node(0);

    public static void main(String[] args) {
        LRUAdd(1);
        LRUAdd(2);
        LRUAdd(3);
        LRUAdd(4);
        LRUAdd(5);
        show();
        LRUGet(3);
        show();
        LRUGet(2);
        show();
        LRUAdd(6);
        show();
    }

    //定义单链表
    public static class Node{
        int val;
        Node next;
        Node(){};
        Node(int val){
            this.val=val;
        };
        Node(int val,Node next){
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 向链表中添加
     * @param val
     */
    public static void LRUAdd(int val){
        if(curSize==0){
            Node node = new Node(val);
            root.next = node ;
            curSize++;
        }
        //链表已满
        else if(curSize==size){
            Node node = new Node(val);
            node.next = root.next;
            root.next = node;
            Node pre = null;
            Node cur = root;
            while (cur.next!=null){
                pre = cur;
                cur=cur.next;
            }
            pre.next = null;
        }else {
            Node node = new Node(val);
            node.next = root.next;
            root.next = node;
            curSize++;
        }
    }

    //访问节点
    public static void LRUGet(int val){
        Node node = root.next;
        Node pre = root;
        while(node!=null){
            if(node.val==val){
                break;
            }
            pre = node;
            node=node.next;
        }
        if(node.next==null){
            Node node1 = new Node();
            node1.next = node;
            node.next = root.next;
            root.next = node;
            pre.next = null;

        }else {
            pre.next = node.next;
            node.next = root.next;
            root.next = node;
        }
        node.toString();
    }
    public static void show(){
        Node node = root.next;
        System.out.println("当前链表为:");
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println("");
    }

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520908.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

linux基础篇:Linux操作系统vi编辑器讲解与常用操作

Linux操作系统vi编辑器讲解与常用操作 一、vi编辑器介绍 vi编辑器是一款功能强大的文本编辑器,广泛应用于Unix和类Unix系统。它是由Bill Joy在1976年开发的,后来演变成vim(vi improved,即“改进版的vi”)编辑器。vi编…

敏感信息泄露漏洞

法律声明 参与培训需要遵守国家法律法规,相关知识只做技术研究,请勿用于违法用途,造成任何后果自负与本人无关。 中华人民共和国网络安全法(2017年6月1日起施行) 第二十二条 任何个人和组织不得从事入侵他人网络、干扰…

【JAVASE】带你了解面向对象三大特性之一(继承)

✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:再无B~U~G-CSDN博客 1.继承 1.1 为什么需要继承 Java 中使用类对现实世界中实体来…

ubuntu-server部署hive-part2-安装hadoop

参照 https://blog.csdn.net/qq_41946216/article/details/134345137 操作系统版本:ubuntu-server-22.04.3 虚拟机:virtualbox7.0 安装hadoop ​​​​​​下载上传 下载地址 https://archive.apache.org/dist/hadoop/common/hadoop-3.3.4/ 以root用…

JDK 17 新特性实战,答案整理,最新面试题

JDK 17中的Pattern类增强了哪些功能? 1、新增asMatchPredicate方法: JDK 17的Pattern类新增了asMatchPredicate方法,可以将正则表达式编译为Predicate,方便用于过滤集合中的字符串。 2、增强了Unicode属性支持: JDK …

LLM推理参数(top_k,top_p, temperature, num_beams)

正常LLM做 next token predicate 时,对输出的 logits 做 softmax,选择概率最大的token。 num_beams :当我们设置 num_beams2 后,就使用了 beam search 的方法,每次不是只直接选择概率最大的 token,而是保留…

0基础确定要?进入it行业?

0基础如何进入IT行业? 🌟想进入IT行业?以下是一些对于0基础的人来说可行的步骤和建议!🌟 "IT"是信息技术(Information Technology)的缩写,它指的是使用计算机、网络、软件和其他设备或系统来存…

数据安全之认识数据库审计系统

随着企业业务数据量的不断增长和数据存储的集中化,数据库成为企业的核心资产之一。然而,数据库面临着各种安全威胁,如SQL注入、权限滥用、数据泄露等。为了保障数据库的安全性和完整性,企业需要采取有效的审计措施来监控和记录数据…

spring源码解析-默认标签解析

spring 默认标签解析 parseDefaultElement处理流程 processBeanDefinition方法解析 processBeanDefinition时序图 元素解析 parseBeanDefinitionElement parseBeanDefinitionElement方法核心源码解析 创建GenericBeanDefinition实例对象 parseMetaElements parseConstructorAr…

平衡二叉树,红黑树,B树和B+树的区别及其应用场景

平衡二叉树 基础数据结构左右平衡高度差大于1会自旋每个节点记录一个数据 平衡二叉树(AVL) AVL树全称G.M. Adelson-Velsky和E.M. Landis,这是两个人的人名。 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree…

通义灵码-ai编码

https://developer.aliyun.com/topic/lingma/activities/202403?taskCode14508&recordIdb1ef3ba27250a5818b1b6ffe418af658#/?utm_contentm_fission_1 「通义灵码 体验 AI 编码,开 AI 盲盒」

使用向量检索和rerank 在RAG数据集上实验评估hit_rate和mrr

文章目录 背景简介代码实现自定义检索器向量检索实验向量检索和rerank 实验 代码开源 背景 在前面部分 大模型生成RAG评估数据集并计算hit_rate 和 mrr 介绍了使用大模型生成RAG评估数据集与评估; 在 上文 使用到了BM25 关键词检索器。接下来,想利用向…

蓝桥杯 十一届C++A组 字符排序 21分(运行超时)

思路: 1. 此题考查的冒泡排序中的交换次数,其实就是考察当前数与后面的逆序对个数问题。而为了最大利用位数,应当使每一位都不小于后面的字符,否则会造成一次逆序对的浪费(贪心,为了使总位数最少&#xff…

springBoot--阿里云短信验证

阿里云短信验证 前言阿里云短信服务免费领取100条短信服务1、开通短信服务2、申请签名3、申请模板4、通过子用户获取账号的AccessKey ID 和AccessKey Secret5、使用教程 前言 在我们平时登录中短信验证吗验证在当今是必不可少的,下面是基于阿里云开发的短信验证操作…

达梦数据库安装与实例创建:图形化方式

达梦数据库安装与实例创建:图形化方式 准备工作数据库安装与卸载安装数据库卸载数据库 实例创建与删除创建实例删除实例 准备工作 查看操作系统信息:Linux内核不能低于2.6。 [rootlocalhost ~]# cat /proc/version Linux version 4.19.90-24.4.v2101.k…

PyTorch|Dataset与DataLoader使用、构建自定义数据集

文章目录 一、Dataset与DataLoader二、自定义Dataset类(一)\_\_init\_\_函数(二)\_\_len\_\_函数(三)\_\_getitem\_\函数(四)全部代码 三、将单个样本组成minibatch(Data…

信息论基础:串联信道

串联信道 大学时候看过一期湖南卫视《快乐大本营》,那时候的主持人是何炅和李湘。节目的一个环节是邀请五名观众上台做猜谜游戏。五人带上耳机,坐在一排椅子上,两两中间隔着挡板,好像并排在一起上厕所。李湘把一部电影的名字写在…

Redis集群三种模式

一、Redis集群的三种模式 Redis有三种模式,分别是主从复制、哨兵模式、cluster 主从复制:主从复制是高可用Redis的基础,哨兵和集群都是在主从复制基础上实现高可用的。主从复制主要实现了数据的多机备份,以及对于读操作的负载均衡和简单的故障…

国家开放大学电大《钢结构》形考任务答案

电大搜题 多的用不完的题库,支持文字、图片搜题,包含国家开放大学、广东开放大学、超星等等多个平台题库,考试作业必备神器。 公众号 答案:更多答案,请关注【电大搜题】微信公众号 答案:更多答案&#x…

【windows】--- nginx 超详细安装并配置教程

目录 一、下载 nginx二、安装三、查看是否安装成功四、配置五、关闭 nginx六 负载均衡七 配置静态资源1. 根目录下的子目录(root)2.完全匹配(alias) 刷新配置(不必重启nginx)八、后端鉴权 一、下载 nginx 打开 nginx 的官网:nginx.org/ &…