厦门大型网站设计公司,做原油的网站,wordpress开启小绿锁,哪个网站做的w7系统好介绍
LRU的英文全称为Least Recently Used#xff0c;即最近最少使用。它是一种内存数据淘汰算法#xff0c;当添加想要添加数据而内存不足时#xff0c;它会优先将最近一段时间内使用最少的数据淘汰掉#xff0c;再将数据添加进来。 原理
LRU的原理在介绍中就已经基本说…介绍
LRU的英文全称为Least Recently Used即最近最少使用。它是一种内存数据淘汰算法当添加想要添加数据而内存不足时它会优先将最近一段时间内使用最少的数据淘汰掉再将数据添加进来。 原理
LRU的原理在介绍中就已经基本说明过了就是在内存不够用时把最近最少使用的数据淘汰掉
那么它为什么会这么进行淘汰呢其主要思想是最近时间内使用的比较多的数据数据在后面的使用中就大概率还会被被使用而最近使用比较少的数据在后面被使用的概率就比较低。使用这样的淘汰算法在访问内存时就可以提高内存的命中率提高整体系统的速度。
下面来举个例子。假设内存中只能存4个数据。我们依次添加了1234这4个数据在添加完后我访问了3和1随后我继续添加数据加入一个5那么此时淘汰的数据为2因为1和3最近已经使用过了2时最近一段时间内使用最少的数据。流程如下 实现
想要使用程序来实现一个简单的LRU算法可以使用单链表。将一个单链表看成我们的内存每次有数据进来时就在头部添加进来淘汰时就将单链表尾部的最后一个节点淘汰。当每次访问时就把访问的节点移动到头节点。
首先定义链表节点的结构 //定义单链表public static class Node{int val;Node next;Node(){};Node(int val){this.valval;};Node(int val,Node next){this.val val;this.next next;}}
随后定义链表的最大容量和链表的根节点和当前链表中的节点数 public static int size 4;public static int curSize 0;public static Node rootnew Node(0);
再编写向链表添加节点的方法
分为三种情况
情况一链表未满那么这就将该节点插入到链表的头部并将curSize加一。
情况二添加的节点时链表已满此时需要我们将链表的最后一个节点淘汰掉然后该节点插入头部。 /*** 向链表中添加* param val*/public static void LRUAdd(int val){if(curSize0){Node node new Node(val);root.next node ;curSize;}//链表已满else if(curSizesize){Node node new Node(val);node.next root.next;root.next node;Node pre null;Node cur root;while (cur.next!null){pre cur;curcur.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.valval){break;}pre node;nodenode.next;}if(node.nextnull){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 rootnew 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.valval;};Node(int val,Node next){this.val val;this.next next;}}/*** 向链表中添加* param val*/public static void LRUAdd(int val){if(curSize0){Node node new Node(val);root.next node ;curSize;}//链表已满else if(curSizesize){Node node new Node(val);node.next root.next;root.next node;Node pre null;Node cur root;while (cur.next!null){pre cur;curcur.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.valval){break;}pre node;nodenode.next;}if(node.nextnull){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();}}
