「lru算法实现java」编程实现lru算法
今天给各位分享lru算法实现java的知识，其中也会对编程实现lru算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、用java语言实现LRU算法和FIFO算法。急急急！！！！！！！
- 2、如何用java实现fifo页面置换算法
- 3、又没有c语言java语言比较厉害的帮我写个代码，不难，会的话估计不到20分钟就写完了页面lru算法
- 4、java lru 算缺页率
- 5、Redis的缓存淘汰策略LRU与LFU
- 6、LRU算法的原理与实现
用java语言实现LRU算法和FIFO算法。急急急！！！！！！！
您好，百度贴吧专家团很高兴能够回答您的问题。您的采纳是我们前进的动力。
public class LRU {
private int theArray[];
private int back; //定义队尾
private int currentSize; //队列中存放元素个数
private int maxSize=5; //队列中能存放元素的个数
public LRU(){
theArray=new int[maxSize];
back=0;
currentSize=0;
}
public void queue(int a[]){
for(int i=0;ia.length;i++){
enQueue(a[i]);
}
}
public void enQueue(int x){ //入队
beUsed(x); //先判断是否已存在该页号，若存在，删除
if(currentSizemaxSize){
theArray[back]=x;
back++;
currentSize++;
}else if(currentSize==maxSize){ //满了
for(int i=0;imaxSize-1;i++){
theArray[i]=theArray[i+1];
}
theArray[maxSize-1]=x;
}
for(int i=0;icurrentSize;i++){
System.out.print(theArray[i]);
}
System.out.println();
}
public void beUsed(int x){ //判断是否已存在该页号,若存在，删除已有的
for(int i=0;icurrentSize;i++){
if(theArray[i]==x){
for(int j=i;jcurrentSize-1;j++){
theArray[j]=theArray[j+1];
}
currentSize--;
back--;
}
}
}
public static void main(String[] args) {
LRU lru=new LRU();
int a[]={4,7,0,7,1,0,1,2,1,2,6};
lru.queue(a);
}
}
如何用java实现fifo页面置换算法
[fifo.rar] - 操作系统中内存页面的先进先出的替换算法fifo
[先进先出页面算法程序.rar] - 分别实现最佳置换算法(optimal)、先进先出(fifo)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。
[0022.rar] - 模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断
[Change.rar] - 用java实现操作系统的页面置换 其中包括 最佳置换算法(Optimal)、先进先出算法（First-in, First-out） 、最近最久不用的页面置换算法（LeastRecently Used Replacement）三种算法的实现
[M_Management.rar] - 操作系统中内存管理页面置换算法的模拟程序，采用的是LRU置换算法
[detail_of_44b0x_TCPIP.rar] - TCPIP 程序包加载到44b0x 的ADS1.2工程文件的说明书。说名了加载过程的细节和如何处理演示程序和代码。演示代码已经上传，大家可以搜索
[OperatingSystemPageReplacementAlgorithm.rar] - java操作系统页面置换算法： （1）进先出的算法（fifo） （2）最近最少使用的算法（LRU） （3）最佳淘汰算法(OPT) （4）最少访问页面算法(LFU) （注：由本人改成改进型Clock算法） （5）最近最不经常使用算法(NUR)
又没有c语言java语言比较厉害的帮我写个代码，不难，会的话估计不到20分钟就写完了页面lru算法
贴一个我写的LRU cache算法，用c++实现的
具体的数据结构用的一个链表加一张哈希表。
实现了set和get, 需要另外的功能我还可以再写。
class LRUCache{
struct cacheEntry{
int key;
int value;
cacheEntry(int c, int v):key(c),value(v){}
};
int _cap;
listcacheEntry entryList;
unordered_mapint, listcacheEntry::iterator entryMap;
void moveToHead(listcacheEntry::iterator it, int key, int value)
{
entryList.erase(it);
cacheEntry tmp(key, value);
entryList.push_front(tmp);
entryMap[key]=entryList.begin();
}
public:
LRUCache(int capacity) {
_cap=capacity;
}
int get(int key) {
if(entryMap.find(key)==entryMap.end())
return -1;
else{
moveToHead(entryMap[key], key, entryMap[key]-value);
return entryMap[key]-value;
}
}
void set(int key, int value) {
if(entryMap.find(key)==entryMap.end()){
if(entryList.size()=_cap){
entryMap.erase(entryList.back().key);
entryList.pop_back();
}
cacheEntry tmp(key, value);
entryList.push_front(tmp);
entryMap[key]=entryList.begin();
}
else{
entryMap[key]-value=value;
moveToHead(entryMap[key], key, value);
}
}
};
java lru 算缺页率
LRU按最近最少使用原则淘汰，即将a,c,d,e...b,v,d一次在cache中存取如果cache中不存在则淘汰最久没被使用的然后加入要使用的。比如说（暂且用【】表示cache）：加入a(缺页+)【a】，加入c【c,a】(缺页+)，加入d【d,c,a】(缺页+)，加入e【e,d,c,a】(缺页+),加入t【t,e,d,c,a】这个时候cache空间用完，之后应用LRU淘汰机制，加入y【y,t,e,d,c】(缺页+，a最久未用被淘汰掉)，加入d(catche中有d,不产生缺页)【d,y,t,e,c】加入f【f,d,y,t,e】(缺页+) 。。。之后一次进行。大概就这样一个思路最后缺页率就是缺页中断次数相加之和/序列总数。
Redis的缓存淘汰策略LRU与LFU
Redis缓存淘汰策略与Redis键的过期删除策略并不完全相同，前者是在Redis内存使用超过一定值的时候（一般这个值可以配置）使用的淘汰策略；而后者是通过定期删除+惰性删除两者结合的方式淘汰内存过期键的。
这里参照官方文档的解释重新叙述一遍过期删除策略：当某个key被设置了过期时间之后，客户端每次对该key的访问（读写）都会事先检测该key是否过期，如果过期就直接删除；但有一些键只访问一次，因此需要主动删除，默认情况下redis每秒检测10次，检测的对象是所有设置了过期时间的键集合，每次从这个集合中随机检测20个键查看他们是否过期，如果过期就直接删除，如果删除后还有超过25%的集合中的键已经过期，那么继续检测过期集合中的20个随机键进行删除。这样可以保证过期键最大只占所有设置了过期时间键的25%。
在Java中LRU的实现方式是使用HashMap结合双向链表，HashMap的值是双向链表的节点，双向链表的节点也保存一份key value。
LFU是在Redis4.0后出现的，LRU的最近最少使用实际上并不精确，考虑下面的情况，如果在|处删除，那么A距离的时间最久，但实际上A的使用频率要比B频繁，所以合理的淘汰策略应该是淘汰B。LFU就是为应对这种情况而生的。
LRU算法的原理与实现
LRU是Least Recently Used的缩写，即最近最少使用算法，应用面非常的广泛，比如redis当中的内存淘汰策略。因为计算机的内存都是有限的，当用户访问的数据如果存在内存当中直接返回的给用户的话，效率会非常快，但是如果内存不存在，在去磁盘里面查找的，效率会大打折扣。所以我们希望在有限的内存空间当中，多存放点热点数据，用户不经常访问的数据，尽量淘汰掉，避免占用内存空间。
使用双向链表来实现LRU 这篇文章已经用双向链表来实现过LRU算法了，但是基于双向链表的特性，使得该算法的时间复杂度为O(n)，显然不是最优的算法，那么有没有算法，可以达到O(1)，当然是有的，早早的计算机科学家已经想到，并且已经实现了。
在笔者介绍接下来的内容时，还是希望先了解一下两篇博文：
一、 图解HashMap原理
二、 图解LinkedHashMap
之前使用双向链表去实现LRU算法时，时间复杂度没有达到O(1)，主要原因在于遍历结点时，带来的时间开销，那么换句话说，要实现遍历结点时，时间复杂度为O(1)，第一时间想到的应该是hash数组，但是hash算法可能会存在不同的key值，产生相同的hash值，那么可以将不同key，但是相同hash值的结点，以单链表的形式存放。这样仅仅是实现了存取时间复杂度为O(1)，如何实现数据能够按访问顺序存放呢？并且增删的时间复杂度为O(1)，这个可以使用双向链表来实现，所以综合来讲，就是实现散列数组+双向链表来使用LRU，可以达到时间复杂度为O(1)。
逻辑视图如下:
咋一看这个图乱的很，稍微解释一下，如果感觉理解上有点困难，可以先去了解一下之前推荐的两篇博文，那里会介绍的更加详细一点。
1.最左侧其实就是一个普通的数组，数组的大小必须是2的倍数，这个原因是什么呢？因为这个数组的存放方式是散列的，意思就是需要key.hashcode (length -1)才能得出存放位置的方式，hash的好处是可以根据key值，在时间复杂度为O(1)的前提找到对应的存放位置，这也是我们的初衷，说到这里其实还没有解释为什么一定要是2的倍数，因为2的倍数-1，这个数的二进制，一定全是1，比如16-1=15，二进制表示就是1111，运算符其实就是将值全部化成二进制逐位与，比如10111011 1111 = 1011 = 11，但是如果不是2的倍数，比如7-1=6，化成二进制就是0110，由于末位是0，不管什么二进制值与0110做运算，一定是偶数，这样会导致散列分布不均匀。
2.不同key值，相同hash值，如何存放呢？相同的hash值做与运算一定能够得到相同的数组脚标，这些结点，以单链表的形式存在，就是图中数组右侧的单链表。
3.如何实现按访问顺序？上图除去数组和挂在数组右侧的单链表，还有绿色和黄色的单向箭头，在右上角还有一个双向链表的头指针。其实这些箭头就是维护不同结点的访问顺序，即双向链表。
总上所述，这种数据结构定义的结构体如下：
class Node{
Object key; //存放key值，用于计算存放数组脚标位置
Object value;//存放元素值
int hash;//存放key.hashcode
Node next;//维护单链表顺序
Node before;//维护双向链表顺序
Node after;
}
笔者用java实现如下，感兴趣可以用自己喜欢的语言去实现一遍，加深理解：
其实以上实现底层原理就是LinkedHashMap的实现原理，只不过笔者做了一些简化，去掉了繁琐的继承，扩容等，突出了算法核心，如果读者感兴趣也可以去研究一下LinkedHashMap的源码。
使用LinkedHashMap来实现LRU算法：
看起来是不是简单了很多，因为LinkedHashMap底层已经封装好了，我们直接调用就好，但是作为一个想要变优秀的码农，一定要知其然知其所以然。
使用散列+双向链表的方式是如何实现O(1)复杂度的？在实现LRU算法过程中，无非两种操作，查找和修改，使用散列数组实现查找时间复杂度为O(1)，使用双向链表实现修改复杂度为O(1)，并且双向链表还可以维护访问顺序，所以使用这种方式，可以达到O(1)。
关于lru算法实现java和编程实现lru算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。