Beispielcode für die Implementierung des LRU-Algorithmus in PHP

Dieser Artikel führt Sie hauptsächlich in das relevante Wissen über PHP ein, einen Seitenersetzungsalgorithmus für die Speicherverwaltung. Lassen Sie uns einen Blick darauf werfen Ich hoffe, es hilft allen.

(Empfohlenes Tutorial: PHP-Video-Tutorial)

Prinzip

LRU ist der am wenigsten kürzlich verwendete Algorithmus. Ein Seitenersetzungsalgorithmus für die Speicherverwaltung. Datenblöcke (Speicherblöcke), die sich im Speicher befinden, aber nicht verwendet werden, werden als LRU bezeichnet. Das Betriebssystem verschiebt sie aus dem Speicher, je nachdem, welche Daten zur LRU gehören, um Platz zum Laden zu schaffen andere Daten.

Was ist der LRU-Algorithmus? LRU ist die Abkürzung für „Least Recent Used“, was bedeutet, dass es am längsten nicht verwendet wurde. Es wird häufig im Seitenersetzungsalgorithmus verwendet und dient der virtuellen Seitenspeicherverwaltung.

Im Hinblick auf die Speicherverwaltung des Betriebssystems war es schon immer eine wichtige Forschungsrichtung, wie man kleinen Speicher einspart und nutzt, um Ressourcen für die meisten Prozesse bereitzustellen. Die virtuelle Speicherverwaltung des Speichers ist derzeit die gebräuchlichste und erfolgreichste Methode – wenn der Speicher begrenzt ist, wird ein Teil des externen Speichers als virtueller Speicher erweitert und der reale Speicher speichert nur die während der aktuellen Laufzeit verwendeten Informationen. Dies erweitert zweifellos die Funktion des Speichers erheblich und verbessert die Parallelität des Computers erheblich.

Die virtuelle Seitenspeicherverwaltung ist eine Verwaltungsmethode, die den vom Prozess benötigten Speicherplatz in mehrere Seiten aufteilt, nur die aktuell benötigten Seiten im Speicher speichert und die verbleibenden Seiten im externen Speicher ablegt.

Die Verwaltung virtueller Seitenspeicher hat zwar Vor- und Nachteile, verringert jedoch den vom Prozess benötigten Speicherplatz, bringt aber auch den Nachteil einer längeren Laufzeit mit sich: Wenn der Prozess ausgeführt wird, ist es unvermeidlich, ihn im externen Speicher zu speichern. Einige Informationen werden mit dem ausgetauscht, was sich bereits im Speicher befindet. Aufgrund der geringen Geschwindigkeit des externen Speichers kann der Zeitaufwand für diesen Schritt nicht vernachlässigt werden.

Daher ist es durchaus sinnvoll, den bestmöglichen Algorithmus zu verwenden, um die Anzahl der Lesevorgänge aus dem externen Speicher zu reduzieren.

Grundprinzip

Angenommen, die Reihenfolge ist 4 3 4 2 3 1 4 2. Dann wird die erste 4er-Runde in den Speicher übertragen. Nach 4 wird 4 in den Speicher übertragen. Nach 2 4 wird 3, 3 in den Speicher übertragen. 1 wird 3 2 in den Speicher übertragen Verwendet wird eins 4, also wird 4 verworfen), dann wird 4 in den Speicher übertragen 4 1 3 (das Prinzip ist das gleiche wie oben) und schließlich wird 2 in den Speicher übertragen 2 4 1

Die Regel lautet: Wenn ein Wert Wird ein Wert neu gespeichert oder aufgerufen, wird der Wert an den Anfang der Warteschlange gestellt. Wenn die Speicherkapazität die Obergrenze überschreitet, löschen Sie das Element am Ende der Warteschlange und speichern Sie den neuen Wert.

Gesamtdesign

Verwenden Sie ein Array zum Speichern von Cache-Objekten (Knoten);

Cache-Objekte (Knoten) bilden eine bidirektionale verknüpfte Liste durch nextKey und preKey;

Speichern Sie den Kopf und das Ende der verknüpften Liste Verarbeitungsprozess

Hauptcode

Knotenknotenklasse

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

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



}

Testcode

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

}

Tatsächlich sind PHP-Arrays geordnet und können auch direkt mit PHP-Arrays implementiert werden. Hier ist nur eine Implementierungsidee Nur als Referenz

(Empfohlenes Tutorial:

PHP-Video-Tutorial

)

Das obige ist der detaillierte Inhalt vonBeispielcode für die Implementierung des LRU-Algorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!