文档章节

LRU算法

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 794
阅读 13
收藏 0

        LRULeast Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU算法就是将最近最久未使用的页面予以淘汰。

可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时,便将该页面号压入栈顶,其他的页面号往栈底移,如果内存不够,则将栈底的页面号移除。这样,栈顶始终是最新被访问的页面的编号,而栈底则是最近最久未访问的页面的页面号。

        如输入以下序列时:4,7,0,7,1,0,1,2,1,2,6

        结果为:

4        
4        7        
4        7        0        
4        0        7        
4        0        7        1        
4        7        1        0        
4        7        0        1        
4        7        0        1        2        
4        7        0        2        1        
4        7        0        1        2        
7        0        1        2        6        


   java代码实现LRU算法如下:

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算法 了,这时上面算法里的这个特殊的栈就不是保存页面的序号了,而是每个图片的序号或大小;所以上面这个栈的元素都用Object类来表示,这样的话这个栈就可以保存的对像了。

本文转载自:http://blog.csdn.net/luoweifu/article/details/8297084

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
LRU-最近最少使用算法

LRU是Least Recently Used 近期最少使用算法 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来...

zh_iOS
2016/11/03
133
0
LRU 缓存置换算法

1.LRU 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 1.2. 实现 最...

满小茂
2016/01/13
719
0
配置Redis作为缓存

将 Redis 用作缓存时, 如果内存空间用满, 就会自动驱逐老的数据。 默认情况下 memcached 就是这种方式, 大部分开发者都比较熟悉。 LRU是Redis唯一支持的回收算法. 本文详细介绍用于限制最大内...

renfufei
2017/08/15
0
0
年薪六十万的Python程序员第一道面试题就是算法!看我如何破解?

LRU算法在Python这种后端工程师面试中,是必出题。如果你不能够彻底理解,那么就是一道坎!此文带你快速理解LRU算法,然后仅用16行Python代码轻松实现一个基于LRU算法的缓存。 LRU:Least r...

Python资料
2018/03/09
0
0
基于闪存数据库的CCF-LRU算法优化

2018.5.28 今天查看了关于flashdb中关于缓存算法的数据结构,发现了3dsim的数据结构是不一样的,然后又去看了一遍3Dsim的数据结构,发现flashdb的数据结构实际是可以优化的。下面对这个点简单...

祚儿疯
2018/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HashMap源码分析

read

V丶zxw
35分钟前
4
0
Python字符串或JSON字符串转字典dict、列表list

有3种方法 1、使用ast模块 >>> import ast>>> s = '["test",1]'>>> ast.literal_eval(s)['test',1]>>> s = '{"test":1}'>>> ast.literal_eval(s){'test': 1} 2、eval函数,这个......

编程老陆
53分钟前
5
0
【JS复习笔记】03 继承(从ES5到ES6)

本文转载于:专业的前端网站➫【JS复习笔记】03 继承(从ES5到ES6) 前言 很久以前学习《Javascript语言精粹》时,写过一个关于js的系列学习笔记。 最近又跟别人讲什么原型和继承什么的,发现...

前端老手
56分钟前
8
0
简单动态网站搭建

如何在windows服务器上配置wordPress和discuz 网站建设中的概念讲解 网站建设的基础操作 网站程序的基础使用 网站程序的优化 简单动态网站搭建 软件部署 域名和主机的购买 域名解析 环境部署...

达达前端小酒馆
今天
6
0
Java每日面试题_03

15、构造器是否可被override constructor(构造器)不能被继承,所以不能被override(重写),但是可以被overloading(重载)。 16、抽象类和接口的区别 抽象类是什么 含有abstract修饰符的class即...

庭前云落
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部