PHP中实现LRU算法基本原理流程及代码是什么

发布时间：2023-02-03 11:15 所属栏目：121 来源：互联网

导读：在实际应用中，我们有时候会遇到PHP实现LRU算法基本原理、流程及代码是什么这样的问题，我们该怎样来处理呢？下文给大家介绍了解决方法，希望这篇PHP实现LRU算法基本原理、流程及代码是什么文章能帮助大家解决问题。原理 LRU是Least Recently Used 近期最少

　　在实际应用中，我们有时候会遇到“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;

　　}

　　}

　　缓存类

　　/**

　　*实现lru缓存

　　*ClassLruCache

　　*@packageapp\common\model

　　*/

　　classLruCache

　　{

　　public$cacheTable=[];

　　private$headNode=null;

　　private$lastNode=null;

　　private$cacheCount=0;

　　private$cacheMax=100;

　　/**

　　*测试输出使用

　　*/

　　publicfunctiondumpAllData(){

　　if(!empty($this->headNode)){

　　$node=$this->headNode;

　　while(!empty($node)){

　　echo'key='.$node->getKey().'nextKey='.(empty($node->getNextKey())?'null':$node->getNextKey()->getKey()).'preKey='.(empty($node->getPreKey())?'null':$node->getPreKey()->getKey()).'value='.$node->getValue()."</br>";

　　$node=$node->getNextKey();

　　}

　　}

　　}

　　/**

　　*@paramint$count

　　*/

　　publicfunctionsetCacheMax(int$count){

　　$this->cacheMax=$count;

　　}

　　/**

　　*@paramstring$key

　　*@param$value

　　*@returnbool

　　*/

　　publicfunctionset(string$key,$value){

　　//设置值为null，则认为删除缓存节点

　　if($value===null){

　　$this->del($key);

　　returntrue;

　　}

　　//判断是否存在表中,存在则更新连表

　　if(!empty($this->cacheTable[$key])){

　　$this->updateList($key);

　　returntrue;

　　}

　　//先判断是否要删除

　　$this->shiftNode();

　　$this->addNode($key,$value);

　　returntrue;

　　}

　　/**

　　*@paramstring$key

　　*@returnbool

　　*/

　　publicfunctiondel(string$key){

　　if(!empty($this->cacheTable[$key])){

　　$node=&$this->cacheTable[$key];

　　//摘出节点

　　$this->jumpNode($node);

　　//置空删除

　　$node->setPreKey(null);

　　$node->setNextKey(null);

　　unset($this->cacheTable[$key]);

　　returntrue;

　　}

　　returnfalse;

　　}

　　/**

　　*@paramstring$key

　　*@returnnull

　　*/

　　publicfunctionget(string$key){

　　if(!empty($this->cacheTable[$key])){

　　$this->updateList($key);

　　return$this->cacheTable[$key]->getValue();

　　}

　　returnnull;

　　}

　　//直接添加节点

　　privatefunctionaddNode($key,$value){

　　$addNode=newNode($key,$value);

　　if(!empty($this->headNode)){

　　$this->headNode->setPreKey($addNode);

　　}

　　$addNode->setNextKey($this->headNode);

　　//第一次保存最后一个节点为头节点

　　if($this->lastNode==null){

　　$this->lastNode=$addNode;

　　}

　　$this->headNode=$addNode;

　　$this->cacheTable[$key]=$addNode;

　　$this->cacheCount++;

　　}

　　//主动删超出的缓存

　　privatefunctionshiftNode(){

　　while($this->cacheCount>=$this->cacheMax){

　　if(!empty($this->lastNode)){

　　if(!empty($this->lastNode->getPreKey())){

　　$this->lastNode->getPreKey()->setNextKey(null);

　　}

　　$lastKey=$this->lastNode->getKey();

　　unset($this->cacheTable[$lastKey]);

　　}

　　$this->cacheCount--;

　　}

　　}

　　//更新节点链表

　　privatefunctionupdateList($key){

　　//这里需要使用引用传值

　　$node=&$this->cacheTable[$key];

　　//当前结点为头结点直接不用处理

　　if($this->headNode===$node){

　　returntrue;

　　}

　　//摘出结点

　　$this->jumpNode($node);

　　//跟头结点交换

　　$node->setNextKey($this->headNode);

　　$this->headNode->setPreKey($node);

　　$node->setPreKey(null);

　　$this->headNode=$node;

　　returntrue;

　　}

　　//将某个节点摘出来

　　privatefunctionjumpNode(Node&$node){

　　if(!empty($node->getPreKey())){

　　$node->getPreKey()->setNextKey($node->getNextKey());

　　}

　　if(!empty($node->getNextKey())){

　　$node->getNextKey()->setPreKey($node->getPreKey());

　　}

　　//如果是最后一个节点,则更新最后节点为它的前节点

　　if($node->getNextKey()==null){

　　$this->lastNode=$node->getPreKey();

　　}

　　//如果是头结点

　　if($node->getPreKey()==null){

　　$this->headNode=$node->getNextKey();

　　}

　　}

　　}

　　测试代码

　　publicfunctiontt(){

　　$cath=model("LruCache");

　　$cath->setCacheMax(3);

　　$cath->set("aa","aaaaaaaaaaa");

　　$cath->set("bb","bbbbbbbbbbbb");

　　$cath->set("cc","ccccccccccccc");

　　$cath->get("aa");

　　//$cath->dumpAllData();

　　$cath->set("dd","ddddddddddddd");

　　//$cath->del("cc");

　　//var_dump($cath->cacheTable);

　　$cath->dumpAllData();

　　exit();

　　}

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

（编辑：ASP站长网）