PHP实现LRU算法的示例代码

吾爱主题阅读：141 2022-11-11 16:14:00 评论：0

原理

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 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * 缓存值保存类， * Class Node * @package app\common\model */ 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; } }

缓存类

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 /** * 实现lru缓存 * Class LruCache * @package app\common\model */ 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(); } } }

测试代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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算法的资料请关注服务器之家其它相关文章！

原文链接：https://mp.weixin.qq.com/s/GsR6IGwGB5BFzUvevRyRiw

可以去百度分享获取分享代码输入这里。

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。