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 节点类 /**
?*?缓存值保存类，
?*?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()."</br>";
????????????????$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实现LRU算法的示例代码的详细内容，更多关于PHP LRU算法的资料请关注其它相关文章！ |
