Exemple de code pour implémenter l'algorithme LRU en PHP

Cet article vous présente principalement les connaissances pertinentes de PHP est l'algorithme le moins récemment utilisé, un algorithme de remplacement de page pour la gestion de la mémoire. Le principe et la mise en œuvre de l'algorithme LRU seront expliqués en détail ci-dessous. J'y parviens ensemble, j'espère que cela aidera tout le monde.

(Tutoriel recommandé : Tutoriel vidéo PHP)

Principe

LRU est l'algorithme le moins récemment utilisé. Un algorithme de remplacement de page pour la gestion de la mémoire. Les blocs de données (blocs de mémoire) qui sont dans la mémoire mais ne sont pas utilisés sont appelés LRU. Le système d'exploitation les déplacera hors de la mémoire en fonction des données appartenant à la LRU pour libérer de l'espace pour le chargement. d'autres données.

Qu'est-ce que l'algorithme LRU ? LRU est l'abréviation de Least Récemment Utilisé, ce qui signifie qu'il n'a pas été utilisé depuis le plus longtemps. Il est souvent utilisé dans l'algorithme de remplacement de page et sert à la gestion du stockage de pages virtuelles.

Concernant la gestion de la mémoire du système d'exploitation, comment économiser et utiliser une petite mémoire pour fournir des ressources pour la plupart des processus a toujours été une direction de recherche importante. La gestion du stockage virtuel de la mémoire est actuellement la méthode la plus courante et la plus efficace : lorsque la mémoire est limitée, une partie de la mémoire externe est étendue en tant que mémoire virtuelle et la mémoire réelle ne stocke que les informations utilisées pendant l'exécution en cours. Cela étend sans aucun doute considérablement la fonction de la mémoire et améliore considérablement la simultanéité de l'ordinateur.

La gestion du stockage des pages virtuelles est une méthode de gestion qui divise l'espace requis par le processus en plusieurs pages, stocke uniquement les pages actuellement requises dans la mémoire et place les pages restantes dans la mémoire externe.

Cependant, il existe des avantages et des inconvénients. La gestion du stockage des pages virtuelles réduit l'espace mémoire requis par le processus, mais elle présente également l'inconvénient d'une durée d'exécution plus longue : lorsque le processus est en cours d'exécution, il est inévitable de le stocker dans une mémoire externe. Certaines informations sont échangées avec ce qui est déjà en mémoire. En raison de la faible vitesse de la mémoire externe, le temps passé à cette étape ne peut être ignoré.

Par conséquent, il est tout à fait judicieux d’adopter le meilleur algorithme possible pour réduire le nombre de lectures depuis la mémoire externe.

Principe de base

Supposons que la séquence soit 4 3 4 2 3 1 4 2. Il y a 3 blocs physiques. Ensuite, le premier tour de 4 est transféré dans la mémoire. Après 4, 4 est transféré dans la mémoire. Après 3, 2 est transféré dans la mémoire. Après 2 4 3, 3 est transféré dans la mémoire 3. Après 2 4, 1 est transféré dans la mémoire 1 3 2 (car le moins. celui utilisé est 4, donc 4 est écarté), puis 4 est transféré dans la mémoire 4 1 3 (le principe est le même que ci-dessus) et enfin 2 est transféré dans la mémoire 2 4 1

La règle est que si une valeur est nouvellement stocké ou accédé, la valeur sera placée au début de la file d'attente. Si la capacité de stockage dépasse la limite supérieure, supprimez l'élément à la fin de la file d'attente et stockez la nouvelle valeur.

Conception globale

Utilisez un tableau pour enregistrer les objets de cache (Node) ;

Les objets de cache (Node) forment une liste chaînée bidirectionnelle via nextKey et preKey ;

Enregistrez la tête et la queue de la liste chaînée ; Processus de traitement

Code principal

Classe de nœud de nœud

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

Classe de 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();
        }
    }



}

Code de test

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

}

En fait, les tableaux PHP sont ordonnés et peuvent également être implémentés directement avec des tableaux PHP. Voici juste une idée d'implémentation. pour référence seulement

(Tutoriel recommandé :

Tutoriel vidéo PHP

)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!