请选择 进入手机版 | 继续访问电脑版
查看: 156|回复: 0

PHP实现LRU算法的示例代码

[复制链接]

2066

主题

2066

帖子

6594

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
6594
发表于 2022-10-9 01:01:29 | 显示全部楼层 |阅读模式
原理

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 节点类
  1. /**
  2.  * 缓存值保存类,
  3.  * Class Node
  4.  * @package app\common\model
  5.  */
  6. class Node{
  7.     private $preKey=null;//链表前一个节点
  8.     private $nextKey=null;//链表后一个节点
  9.     private $value=null;//当前的值
  10.     private $key=null;//当前key


  11.     public function __construct(string  $key,$value)
  12. {
  13.         $this->value=$value;
  14.         $this->key=$key;
  15.     }

  16.     public function setPreKey($preValue){
  17.         $this->preKey=$preValue;
  18.     }
  19.     public function setNextKey($nextValue){
  20.         $this->nextKey=$nextValue;
  21.     }

  22.     public function getPreKey(){
  23.         return $this->preKey;
  24.     }

  25.     public function getNextKey(){
  26.         return $this->nextKey;
  27.     }

  28.     public function getValue(){
  29.         return $this->value;
  30.     }

  31.     public function setValue($value){
  32.         $this->value=$value;
  33.     }

  34.     public function setKey(string  $key){
  35.         $this->key=$key;
  36.     }

  37.     public function getKey(){
  38.         return $this->key;
  39.     }
  40. }
复制代码
缓存类
  1. /**
  2.  * 实现lru缓存
  3.  * Class LruCache
  4.  * @package app\common\model
  5.  */
  6. class LruCache
  7. {
  8.     public $cacheTable =[];
  9.     private $headNode=null;
  10.     private $lastNode=null;
  11.     private $cacheCount=0;
  12.     private $cacheMax=100;


  13.     /**
  14.      * 测试输出使用
  15.      */
  16.     public function dumpAllData(){
  17.         if (!empty($this->headNode)){
  18.             $node=$this->headNode;
  19.             while (!empty($node)){
  20.                 echo 'key='.$node->getKey().'  nextKey='.(empty($node->getNextKey())?'null':$node->getNextKey()->getKey()).' preKey='.(empty($node->getPreKey())?'null':$node->getPreKey()->getKey()).' value='.$node->getValue()."</br>";
  21.                 $node=$node->getNextKey();
  22.             }
  23.         }
  24.     }


  25.     /**
  26.      * @param int $count
  27.      */
  28.     public function setCacheMax(int $count){
  29.         $this->cacheMax=$count;
  30.     }

  31.     /**
  32.      * @param string $key
  33.      * @param $value
  34.      * @return bool
  35.      */
  36.     public function set(string $key,$value){

  37.         //设置值为null,则认为删除缓存节点
  38.         if ($value===null){
  39.             $this->del($key);
  40.             return true;
  41.         }

  42.         //判断是否存在表中,存在则更新连表
  43.         if (!empty($this->cacheTable[$key])){
  44.             $this->updateList($key);
  45.             return true;
  46.         }

  47.         //先判断是否要删除
  48.         $this->shiftNode();
  49.         $this->addNode($key,$value);
  50.         return true;

  51.     }

  52.     /**
  53.      * @param string $key
  54.      * @return bool
  55.      */
  56.     public function del(string $key){
  57.         if (!empty($this->cacheTable[$key])){
  58.             $node=&$this->cacheTable[$key];

  59.             //摘出节点
  60.             $this->jumpNode($node);
  61.             //置空删除
  62.             $node->setPreKey(null);
  63.             $node->setNextKey(null);
  64.             unset($this->cacheTable[$key]);
  65.             return true;
  66.         }

  67.         return false;
  68.     }

  69.     /**
  70.      * @param string $key
  71.      * @return null
  72.      */
  73.     public function get(string $key){
  74.         if (!empty($this->cacheTable[$key])){
  75.             $this->updateList($key);
  76.             return $this->cacheTable[$key]->getValue();
  77.         }

  78.         return null;
  79.     }


  80.     //直接添加节点
  81.     private function addNode($key,$value){
  82.         $addNode=new Node($key,$value);
  83.         if (!empty($this->headNode)){
  84.             $this->headNode->setPreKey($addNode);
  85.         }
  86.         $addNode->setNextKey($this->headNode);

  87.         //第一次保存最后一个节点为头节点
  88.         if ($this->lastNode==null){
  89.             $this->lastNode=$addNode;
  90.         }
  91.         $this->headNode=$addNode;
  92.         $this->cacheTable[$key]=$addNode;
  93.         $this->cacheCount++;
  94.     }


  95.     //主动删超出的缓存
  96.     private function shiftNode(){
  97.         while ($this->cacheCount>=$this->cacheMax){
  98.             if (!empty($this->lastNode)){
  99.                 if (!empty($this->lastNode->getPreKey())){
  100.                     $this->lastNode->getPreKey()->setNextKey(null);
  101.                 }
  102.                 $lastKey=$this->lastNode->getKey();
  103.                 unset($this->cacheTable[$lastKey]);
  104.             }
  105.             $this->cacheCount--;
  106.         }

  107.     }

  108.     //更新节点链表
  109.     private function updateList($key){
  110.         //这里需要使用引用传值
  111.         $node=&$this->cacheTable[$key];

  112.         //当前结点为头结点 直接不用处理
  113.         if ($this->headNode===$node){
  114.             return true;
  115.         }

  116.         //摘出结点
  117.         $this->jumpNode($node);
  118.         //跟头结点交换
  119.         $node->setNextKey($this->headNode);
  120.         $this->headNode->setPreKey($node);
  121.         $node->setPreKey(null);
  122.         $this->headNode=$node;

  123.         return true;

  124.     }


  125.     //将某个节点摘出来
  126.     private function jumpNode(Node &$node){
  127.         if (!empty($node->getPreKey())){
  128.             $node->getPreKey()->setNextKey($node->getNextKey());
  129.         }

  130.         if (!empty($node->getNextKey())){
  131.             $node->getNextKey()->setPreKey($node->getPreKey());
  132.         }

  133.         //如果是最后一个节点,则更新最后节点为它的前节点
  134.         if ($node->getNextKey()==null){
  135.             $this->lastNode=$node->getPreKey();
  136.         }

  137.         //如果是头结点
  138.         if ($node->getPreKey()==null){
  139.             $this->headNode=$node->getNextKey();
  140.         }
  141.     }



  142. }
复制代码
测试代码
  1. public function tt(){
  2.     $cath=model("LruCache");
  3.     $cath->setCacheMax(3);
  4.     $cath->set("aa","aaaaaaaaaaa");
  5.     $cath->set("bb","bbbbbbbbbbbb");
  6.     $cath->set("cc","ccccccccccccc");
  7.     $cath->get("aa");

  8.     //        $cath->dumpAllData();
  9.     $cath->set("dd","ddddddddddddd");
  10.     //        $cath->del("cc");
  11.     //        var_dump($cath->cacheTable);
  12.     $cath->dumpAllData();
  13.     exit();

  14. }
复制代码
其实php的数组就是有序的,也可以直接用php数组实现,这里只是提供一个实现的思路,仅供参考哈!
以上就是PHP实现LRU算法的示例代码的详细内容,更多关于PHP LRU算法的资料请关注趣UU其它相关文章!

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
打赏作者
  • 0
  • 0
  • 0
  • 0
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表