最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
PHP实现LRU算法解析
时间:2022-09-19 编辑:坚强 来源:一聚教程网
本文讲解的是关于PHP实现LRU算法解析,本文通过详细的内容和代码为大家呈现,感兴趣的小伙伴快来一起学习学习吧。
基本原理
假设 序列为 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 节点类
/** * 缓存值保存类, * Class Node * @package appcommonmodel */ class Node{ private $preKey=null;//链表前一个节点 private $nextKey=null;//链表后一个节点 private $value=null;//当前的值 private $key=null;//当前key public function __construct(string $key,$value) { $this->value=$value; $this->key=$key; } public function setPreKey($preValue){ $this->preKey=$preValue; } public function setNextKey($nextValue){ $this->nextKey=$nextValue; } public function getPreKey(){ return $this->preKey; } public function getNextKey(){ return $this->nextKey; } public function getValue(){ return $this->value; } public function setValue($value){ $this->value=$value; } public function setKey(string $key){ $this->key=$key; } public function getKey(){ return $this->key; } }
缓存类
/** * 实现lru缓存 * Class LruCache * @package appcommonmodel */ class LruCache { public $cacheTable =[]; private $headNode=null; private $lastNode=null; private $cacheCount=0; private $cacheMax=100; /** * 测试输出使用 */ public function dumpAllData(){ 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().""; $node=$node->getNextKey(); } } } /** * @param int $count */ public function setCacheMax(int $count){ $this->cacheMax=$count; } /** * @param string $key * @param $value * @return bool */ public function set(string $key,$value){ //设置值为null,则认为删除缓存节点 if ($value===null){ $this->del($key); return true; } //判断是否存在表中,存在则更新连表 if (!empty($this->cacheTable[$key])){ $this->updateList($key); return true; } //先判断是否要删除 $this->shiftNode(); $this->addNode($key,$value); return true; } /** * @param string $key * @return bool */ public function del(string $key){ if (!empty($this->cacheTable[$key])){ $node=&$this->cacheTable[$key]; //摘出节点 $this->jumpNode($node); //置空删除 $node->setPreKey(null); $node->setNextKey(null); unset($this->cacheTable[$key]); return true; } return false; } /** * @param string $key * @return null */ public function get(string $key){ if (!empty($this->cacheTable[$key])){ $this->updateList($key); return $this->cacheTable[$key]->getValue(); } return null; } //直接添加节点 private function addNode($key,$value){ $addNode=new Node($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++; } //主动删超出的缓存 private function shiftNode(){ 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--; } } //更新节点链表 private function updateList($key){ //这里需要使用引用传值 $node=&$this->cacheTable[$key]; //当前结点为头结点 直接不用处理 if ($this->headNode===$node){ return true; } //摘出结点 $this->jumpNode($node); //跟头结点交换 $node->setNextKey($this->headNode); $this->headNode->setPreKey($node); $node->setPreKey(null); $this->headNode=$node; return true; } //将某个节点摘出来 private function jumpNode(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(); } } }
测试代码
public function tt(){ $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数组实现,这里只是提供一个实现的思路,仅供参考哈!
-
上一个: PHP实现导入大量CSV数据介绍
-
下一个: PHP实现网络请求方法介绍
相关文章
- PHP导出数据超时的优化建议解读 10-31
- PHP之mysql位运算解析 10-31
- Laravel实现登录跳转功能解析 10-31
- php双向队列解读 10-31
- Laravel异常上下文解决教程 10-24
- php数组查询元素位置方法介绍 10-24