Sample code for implementing LRU algorithm in PHP

This article mainly introduces you to the relevant knowledge of PHP. LRU is the Least Recently Used algorithm, a page replacement algorithm for memory management. The principle and implementation of the LRU algorithm will be explained in detail below. , let’s take a look at it, I hope it will be helpful to everyone.

(Recommended tutorial: PHP video tutorial)

Principle

LRU is Least Recently Used Least Recently Used algorithm. A page replacement algorithm for memory management. Data blocks (memory blocks) that are in the memory but are not used are called LRU. The operating system will move them out of the memory based on which data belongs to the LRU to make room for loading other data.

What is the LRU algorithm? LRU is the abbreviation of Least Recently Used, which means it has not been used for the longest time. It is often used in the page replacement algorithm and serves virtual page storage management.

Regarding the memory management of operating systems, how to save and utilize small memory to provide resources for the most processes has always been an important direction of research. The virtual storage management of memory is the most common and successful way now - when the memory is limited, a part of the external memory is expanded as virtual memory, and the real memory only stores the information used during the current runtime. This undoubtedly greatly expands the function of memory and greatly improves the concurrency of the computer.

Virtual page storage management is a management method that divides the space required by the process into multiple pages, stores only the currently required pages in the memory, and puts the remaining pages into external memory.

However, there are advantages and disadvantages. Virtual page storage management reduces the memory space required by the process, but it also brings the disadvantage of longer running time: during the running of the process, it is inevitable to Some information stored in the external memory is exchanged with what is already in the memory. Due to the low speed of the external memory, the time spent in this step cannot be ignored.

Therefore, it is quite meaningful to adopt the best algorithm possible to reduce the number of reads from external memory.

Basic Principle

Assume that the sequence is 4 3 4 2 3 1 4 2. There are 3 physical blocks. Then the first round of 4 is transferred into the memory. The second round of 3 is transferred into the memory. After 3 4, 4 is transferred into the memory. After 4, 3 is transferred into memory, 2 is transferred into memory 2, after 3, 3 is transferred into memory, 3 2, after 4, 1 is transferred into memory 1 3 2 (because 4 is used at least, so 4 is discarded), after 4, 4 is transferred into memory, 4 1 3 (the principle is the same as above) ) The last 2 is transferred into the memory 2 4 1

The rule is that if a value is newly stored or accessed, the value is placed at the beginning of the queue. If the storage capacity exceeds the upper limit cap, delete the element at the end of the queue and store the new value.

Overall design

Use an array to save the cache object (Node);

The cache objects (Node) form a two-way linked list through nextKey and preKey;

Save the head and tail of the linked list;

Processing process

Main code

Node node class

/**
 * 缓存值保存类，
 * 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;
    }
}

Cache class

/**
 * 实现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 &#39;key=&#39;.$node->getKey().&#39;  nextKey=&#39;.(empty($node->getNextKey())?&#39;null&#39;:$node->getNextKey()->getKey()).&#39; preKey=&#39;.(empty($node->getPreKey())?&#39;null&#39;:$node->getPreKey()->getKey()).&#39; value=&#39;.$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();
        }
    }



}

Test code

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();

}

In fact, PHP arrays are ordered and can also be implemented directly using PHP arrays. Here is just an implementation idea for reference only

(Recommended tutorial: PHP video tutorial)

The above is the detailed content of Sample code for implementing LRU algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!