加入收藏 | 设为首页 | 会员中心 | 我要投稿 武汉站长网 (https://www.027zz.cn/)- 云连接、智能边缘云、数据快递、云手机、云日志!
当前位置: 首页 > 站长学院 > PHP教程 > 正文

PHP实现LRU算法基本原理

发布时间:2023-12-25 21:06:01 所属栏目:PHP教程 来源:DaWei
导读: 在实际应用中,我们有时候会遇到“PHP实现LRU算法基本原理、流程及代码是什么”这样的问题,我们该怎样来处理呢?下文给大家介绍了解决方法,希望这篇“PHP实现LRU算法基本原
在实际应用中,我们有时候会遇到“PHP实现LRU算法基本原理、流程及代码是什么”这样的问题,我们该怎样来处理呢?下文给大家介绍了解决方法,希望这篇“PHP实现LRU算法基本原理、流程及代码是什么”文章能帮助大家解决问题。

原理

LRU是Least Recently Used 近期最少使用算法。内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。

什么是LRU算法?LRU是Least Recently Used的缩写,即最近最久未使用,常用于页面置换算法,是为虚拟页式存储管理服务的。

关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。

虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。

然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。

因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。

基本原理

假设 序列为 4 3 4 2 3 1 4 2物理块有3个 则首轮 4调入内存 4次轮 3调入内存 3 4之后 4调入内存 4 3之后 2调入内存 2 4 3之后 3调入内存 3 2 4之后 1调入内存 1 3 2(因为最少使用的是4,所以丢弃4)之后 4调入内存 4 1 3(原理同上)最后 2调入内存 2 4 1

规律就是,如果新存入或者访问一个值,则将这个值放在队列开头。如果存储容量超过上限cap,那么删除队尾元素,再存入新的值。

整体设计

用数组保存缓存对象(Node);

缓存对象(Node)之间通过nextKey,preKey组成一个双向链表;

保存链表头跟尾;

处理流程

主要代码

Node 节点类

/**
*缓存值保存类,
*ClassNode
*@packageapp\common\model
*/
classNode{
private$preKey=null;//链表前一个节点
private$nextKey=null;//链表后一个节点
private$value=null;//当前的值
private$key=null;//当前key


publicfunction__construct(string$key,$value)
{
$this->value=$value;
$this->key=$key;
}

publicfunctionsetPreKey($preValue){
$this->preKey=$preValue;
}
publicfunctionsetNextKey($nextValue){
$this->nextKey=$nextValue;
}

publicfunctiongetPreKey(){
return$this->preKey;
}

publicfunctiongetNextKey(){
return$this->nextKey;
}

publicfunctiongetValue(){
return$this->value;
}

publicfunctionsetValue($value){
$this->value=$value;
}

publicfunctionsetKey(string$key){
$this->key=$key;
}

publicfunctiongetKey(){
return$this->key;
}
}

其实php的数组就是有序的,也可以直接用php数组实现,这里只是提供一个实现的思路,仅供参考哈!

上述内容具有一定的借鉴价值,感兴趣的朋友可以参考,希望能对大家有帮助。

(编辑:武汉站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章