Contoh kod untuk melaksanakan algoritma LRU dalam PHP

Artikel ini terutamanya memperkenalkan anda kepada pengetahuan yang berkaitan tentang PHP ialah algoritma yang Paling Kurang Digunakan Baru-baru ini dan algoritma penggantian halaman untuk pengurusan ingatan Prinsip dan pelaksanaan algoritma LRU akan diterangkan secara terperinci di bawah, mari kita lihat bersama-sama, saya harap ia akan membantu semua orang.

(Tutorial disyorkan: Tutorial video PHP)

Prinsip

LRU Paling Kurang Digunakan Paling Kurang Digunakan Baru-baru ini algoritma. Algoritma penggantian halaman untuk pengurusan memori Blok data (blok memori) yang berada dalam memori tetapi tidak digunakan dipanggil LRU Sistem pengendalian akan mengalihkannya keluar dari memori berdasarkan data yang dimiliki oleh LRU untuk memberi ruang untuk dimuatkan data lain.

Apakah algoritma LRU? LRU ialah singkatan daripada Least Recently Used, yang bermaksud ia tidak digunakan untuk masa yang paling lama Ia sering digunakan dalam algoritma penggantian halaman dan menyediakan pengurusan storan halaman maya.

Mengenai pengurusan memori sistem pengendalian, cara menyimpan dan menggunakan memori kecil untuk menyediakan sumber bagi kebanyakan proses sentiasa menjadi hala tuju penting penyelidikan. Pengurusan storan maya memori pada masa ini merupakan cara yang paling biasa dan paling berjaya - apabila ingatan terhad, sebahagian daripada memori luaran dikembangkan sebagai ingatan maya, dan ingatan sebenar hanya menyimpan maklumat yang digunakan semasa masa jalanan semasa. Ini sudah pasti sangat meluaskan fungsi ingatan dan sangat meningkatkan keselarasan komputer.

Pengurusan storan halaman maya ialah kaedah pengurusan yang membahagikan ruang yang diperlukan oleh proses kepada berbilang halaman, menyimpan hanya halaman yang diperlukan pada masa ini dalam memori dan meletakkan halaman yang tinggal ke dalam memori luaran.

Walau bagaimanapun, terdapat kelebihan dan kekurangan pengurusan storan halaman maya mengurangkan ruang memori yang diperlukan oleh proses, tetapi ia juga membawa keburukan masa berjalan yang lebih lama: semasa menjalankan proses, ia tidak dapat dielakkan kepada Sesetengah. maklumat yang disimpan dalam memori luaran ditukar dengan apa yang sudah ada dalam ingatan Disebabkan kelajuan rendah memori luaran, masa yang dihabiskan dalam langkah ini tidak boleh diabaikan.

Oleh itu, adalah agak bermakna untuk menggunakan algoritma terbaik yang mungkin untuk mengurangkan bilangan bacaan daripada memori luaran.

Prinsip Asas

Andaikan urutannya ialah 4 3 4 2 3 1 4 2 dan terdapat 3 blok fizikal Kemudian pusingan pertama 4 dipindahkan ke dalam ingatan 3 dipindahkan ke memori Selepas 3 4, 4 dipindahkan ke memori 4, 2 selepas 3 dipindahkan ke memori 2 4 3 Selepas 3 dipindahkan ke memori 3 2 4 Selepas 1 dipindahkan ke memori 1 3 2 (. kerana 4 digunakan sekurang-kurangnya, jadi 4 dibuang) Selepas 4 dipindahkan ke memori 4 1 3 (prinsipnya sama seperti di atas) ) 2 terakhir dipindahkan ke memori 2 4 1

Peraturan ialah jika nilai baru disimpan atau diakses, nilai itu diletakkan pada permulaan baris gilir. Jika kapasiti storan melebihi had had atas, padamkan elemen di penghujung baris gilir dan simpan nilai baharu.

Reka bentuk keseluruhan

Gunakan tatasusunan untuk menyimpan objek cache (Nod);

Objek cache (Nod) membentuk senarai terpaut dua hala melalui nextKey dan preKey;

Simpan kepala dan ekor senarai terpaut;

Proses pemprosesan

Kod utama

Kelas nod nod

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

Kelas cache

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



}

Kod ujian

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

}

Malah, tatasusunan PHP disusun dan juga boleh dilaksanakan secara terus menggunakan tatasusunan PHP hanya idea pelaksanaan untuk rujukan sahaja

(Tutorial disyorkan: Tutorial video PHP)

Atas ialah kandungan terperinci Contoh kod untuk melaksanakan algoritma LRU dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!