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; } } 缓存类 /** *实现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数组实现,这里只是提供一个实现的思路，仅供参考哈！ （编辑：银川站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
