LRU是Least Recently Used的缩写,即最少使用算法。
位于org.apache.commons.collections.map包中的LRUMap,利用LRU(least recently used)算法对最近使用的保留,最不经常使用的会被删除,当Map满的时候。该MAP在处理cache时还是挺有用的。
LRU算法也可以用于一些实际的应用中,如你要做一个浏览器,或类似于淘宝客户端的应用的就要用到这个原理。大家都知道浏览器在浏览网页的时候会把下载的图片临时保存在本机的一个文件夹里,下次再访问时就会,直接从本机临时文件夹里读取。但保存图片的临时文件夹是有一定容量限制的,如果你浏览的网页太多,就会一些你最不常使用的图像删除掉,只保留最近最久使用的一些图片。这时就可以用到LRU算法 了,这时上面算法里的这个特殊的栈就不是保存页面的序号了,而是每个图片的序号或大小;所以下面这个栈的元素都用Object类来表示,这样的话这个栈就可以保存的对像了。
import java.util.ArrayList;
import java.util.List;
public class LRU {
/**
* 内存块的个数
*/
public static final int N = 5;
/**
* 内存块数组
*/
Object[] array = new Object[N];
private int size;
public LRU() {
}
/**
* 判断内存区是否为空
* @return
*/
public boolean isEmpty() {
if(size == 0) {
return true;
} else {
return false;
}
}
/**
* 判断内存区是否达到最大值
* @return
*/
public boolean isOutOfBoundary() {
if(size >=N) {
return true;
} else {
return false;
}
}
/**
* 查找元素o在数组中的位置
* @param o
* @return
*/
public int indexOfElement(Object o) {
for(int i=0; i<N; i++) {
if(o == array[i]) {
return i;
}
}
return -1;
}
/**
* 有新的数据o需要申请内存
* @param o
* @return 移出内存区的数据
*/
public Object push(Object o) {
int t = -1;
if(!isOutOfBoundary() && indexOfElement(o) == -1){
array[size] = o;
size ++;
} else if(isOutOfBoundary() && indexOfElement(o) == -1){
for(int i=0; i<size-1; i++) {
array[i] = array[i+1];
}
array[size-1] = o;
} else {
t = indexOfElement(o);
for(int i=t; i<size-1; i++) {
array[i] = array[i+1];
}
array[size-1] = o;
}
if( -1 == t) {
return null;
} else {
return array[t];
}
}
/**
* 输出内存区中的各数据
*/
public void showMemoryBlock() {
for(int i=0; i<size; i++) {
System.out.print(array[i] + "\t");
}
}
/**
* @param args
*/
public static void main(String[] args) {
Integer iter[] = {4,7,0,7,1,0,1,2,1,2,6};
LRU lru = new LRU();
for(int i=0; i<iter.length; i++) {
lru.push(iter[i]);
lru.showMemoryBlock();
System.out.println();
}
}
}
分享到:
相关推荐
近期最少使用算法
最近最久未使用(LRU) 选择最后一次访问时间距离当前时间最长的一页并淘汰之 LRU软件实现 设置一个页号栈, 当一个页面被访问时,就立即将它的页号压入页号栈,并检查页号栈中是否有与刚压入栈顶的相同的页号,若...
使用LRU算法实现页面置换算法。LRU算法基于一种假设,长期不使用的数据,在未来的使用性也不大。因此,当数据占用内存达到一定的阙值时,我们要移除最近最少使用的数据。LRU算法中,使用了一种有趣的数据结构,叫做...
高速缓存 最近最少使用算法。
LRU(最近最少使用算法) and MRU(最近最常使用算法)所谓的LRU(Least recently used)算法的基本概念是:当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,换句话说就是优先清除”较不常使用的...
操作系统页面置换-最近最少使用(LRU)算法模拟.doc.doc
LRU页面置换算法的源代码,以及可执行程序
lru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未使用置换算法课程设计 (2).pdflru页面置换算法模拟最近最久未...
LRU页面置换算法 操作系统 大作业 郑州大学软件学院 含有详细注释
主要实现主存空间的分配和回收、存储保护。主要是对用户区的管理。存储管理采用请求分页式存储管理方式。该系统的页面置换算法必须包括先进先出页面置换算法、最近最少使用LRU页面置换算法、最佳置换算法。
(2)最近最少访问页面算法(LRU) 2.要有体现算法比较的程序输出,比如:缺页率和页面置换次数等。 3.采用固定分配局部置换,且可以在程序中实现块数重新分配。 具有抖动判断和Belady异常判断机制 根据设计要求实现对...
LRU页面置换算法,最近最少使用算法,目前很常用的缓存算法
LRU是Least Recently Used最近最少使用算法,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的。
*“最近最少使用算法”(LRU算法),它是将最近一段时间内最少被访问过的行淘汰出局。 *因此需要为每行设置一个计数器,LRU算法是把命中行的计数器清零,其他各行计数器加1。 *当需要替换时淘汰行计数器计数值...
自己写的页面置换算法。期中OPT算法写的不好,请有选择参考
共四种:FIFO\LRU\LFU\OPT 。在VC环境下运行完全成功。 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储...
实现功能: 1、模拟分页式存储管理中硬件的士转换和产生缺页中断 2、用先进先出(FIFO)页面调度算法处理缺页中断 3、用最近最少用(LRU)页面调度算法处理缺页中断
基于JAVA的LRU(Least Recently Used 近期最少使用算法)算法实现
(2) 最近最少使用的算法(LRU) (3) 最佳淘汰算法(OPT)(4) 最少访问页面算法(LFU) (5) 最近最不经常使用算法(NUR) 命中率=1-页面失效次数/页地址流长度 <程序设计> 本实验的程序设计基本上按照实验内容进行。即首先用 ...
页面置换算法 先进先出的算法(FIFO) 最佳置换算法(OPT) 近期最久未使用算法(LRU) 近期最少使用算法(LFU) CLOCK置换算法