PHP實作LRU演算法的範例程式碼

這篇文章主要給大家介紹了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 &#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();
        }
    }



}

測試程式碼

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中文網其他相關文章！