• 技术文章 >后端开发 >php教程

    PHP实现LRU算法的示例代码

    长期闲置长期闲置2022-07-26 13:59:36转载492
    本篇文章主要给大家介绍了PHP的相关知识,LRU是Least Recently Used 近期最少使用算法, 内存管理的一种页面置换算法,下面将详解LRU算法的原理以及实现,下面一起来看一下,希望对大家有帮助。

    (推荐教程:PHP视频教程

    原理

    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 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;
        }
    }

    缓存类

    /**
     * 实现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();
            }
        }
    
    
    
    }

    测试代码

    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视频教程

    以上就是PHP实现LRU算法的示例代码的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:脚本之家,如有侵犯,请联系admin@php.cn删除
    专题推荐:php
    上一篇:什么是接口?如何在PHP中使用接口编写优雅的代码? 下一篇:PHP常量两种定义方法:define和const有什么区别
    VIP课程(WEB全栈开发)

    相关文章推荐

    • 【活动】充值PHP中文网VIP即送云服务器• php正则能不能匹配数组• php怎么合并两个数组并从小到大排序• php怎么求数组第一个元素的下标是什么• php怎么检测数组中是否包含某字符串• php只有索引数组对不对
    1/1

    PHP中文网