Implémentation de l'algorithme d'expulsion du cache LRU à l'aide de PHP

LRU(cache)

LRU Introduction

Le cache est une technologie qui améliore les performances de lecture des données. Mais pour les ordinateurs, il est impossible de mettre en cache toutes les données. Lorsque leur espace critique est atteint, il faut remplacer une partie des données mises en cache par de nouvelles données via certaines règles. Et si vous choisissiez de le remplacer à ce moment-là ?

Il existe de nombreuses stratégies de remplacement, les plus couramment utilisées sont les suivantes :

● FIFO (stratégie premier entré, premier sorti)

● LFU (stratégie la moins utilisée)

● LRU (politique la moins récemment utilisée)

● NMRU (sélectionnez au hasard un remplacement dans le cache qui n'a pas été utilisé récemment)

Puisque cet article implémente principalement LRU, il y a donc c'est non, je vais vous présenter d'autres choses, vous pouvez les découvrir par vous-même.

Supposons que vous ayez déjà 5 petites amies et que vous réussissiez à rencontrer une nouvelle petite amie. Alors que vous êtes accro aux femmes, vous êtes surpris de constater que vous ne pouvez plus vous battre les uns contre les autres comme vous le faisiez lorsque vous l'étiez. jeune. Quand tu as six ans, tu dois abandonner quelques copines. A cette époque, toi, le salaud avec six copines, montre complètement ton caractère de salaud et dis au revoir à la fille qui a montré le moins d'affection récemment : "Je' Je suis désolé, équipe nationale de basket-ball. En ce moment, je dois me lever et servir le ballon de touche. Moi, Nan Ciqiu, je dis au revoir "De cette façon, lorsque vous réussissez à rencontrer une nouvelle jeune femme, votre corps atteint le point critique. point, et vous devez abandonner les autres jeunes filles.

Ce qui suit est une image pratique pour comprendre son principe.

Sur la base de l'image ci-dessus, nous savons que le fonctionnement de LRU n'est rien de plus qu'une insertion, une suppression et un remplacement, si l'espace cache est plein. , puis insérez-le dans la tête et supprimez-le pour la queue. S'il n'est pas plein, il existe deux types. L'un est que si le cache atteint, il vous suffit de déplacer la valeur mise en cache vers head. S'il n'existait pas auparavant, il est inséré dans la tête.

Processus de mise en œuvre

La prochaine étape est la sélection de la structure des données. Le stockage du tableau est un espace mémoire continu, bien que la complexité temporelle de la requête soit O (1), la suppression et l'insertion doivent être déplacées afin de préserver la continuité de l'espace mémoire, donc la complexité temporelle est O (n). ). Afin d'obtenir une suppression rapide, une liste doublement chaînée est utilisée. Mais la complexité temporelle de la requête de la liste chaînée est O (n), une table de hachage est donc nécessaire. Tant de conneries, d’implémentation de code. En fait, j’ai déjà répondu à cette question. Permettez-moi d'en parler spécifiquement.

class LRUCache {
    private $capacity;
    private $list;
    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity=$capacity;
        $this->list=new HashList();
    }
    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if($key<0) return -1;
        return $this->list->get($key);
    }
    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        $size=$this->list->size;
        $isHas=$this->list->checkIndex($key);
        if($isHas || $size+1 > $this->capacity){
            $this->list->removeNode($key);
        }
        $this->list->addAsHead($key,$value);
    }
}
class HashList{
    public $head;
    public $tail;
    public $size;
    public $buckets=[];
    public function __construct(Node $head=null,Node $tail=null){
        $this->head=$head;
        $this->tail=$tail;
        $this->size=0;
    }
    //检查键是否存在
    public function checkIndex($key){
        $res=$this->buckets[$key];
        if($res){
            return true;
        }
        return false;
    }
    public function get($key){
        $res=$this->buckets[$key];
        if(!$res) return -1;
        $this->moveToHead($res);
        return $res->val;
    }
    //新加入的节点
    public function addAsHead($key,$val)
{
        $node=new Node($val);
        if($this->tail==null && $this->head !=null){
            $this->tail=$this->head;
            $this->tail->next=null;
            $this->tail->pre=$node;
        }
        $node->pre=null;
        $node->next=$this->head;
        $this->head->pre=$node;
        $this->head=$node;
        $node->key=$key;
        $this->buckets[$key]=$node;
        $this->size++;
    }
    //移除指针(已存在的键值对或者删除最近最少使用原则)
    public function removeNode($key)
{
        $current=$this->head;
        for($i=1;$i<$this->size;$i++){
            if($current->key==$key) break;
            $current=$current->next;
        }
        unset($this->buckets[$current->key]);
        //调整指针
        if($current->pre==null){
            $current->next->pre=null;
            $this->head=$current->next;
        }else if($current->next ==null){
            $current->pre->next=null;
            $current=$current->pre;
            $this->tail=$current;
        }else{
            $current->pre->next=$current->next;
            $current->next->pre=$current->pre;
            $current=null;
        }
        $this->size--;
    }
    //把对应的节点应到链表头部(最近get或者刚刚put进去的node节点)
    public function moveToHead(Node $node)
{
        if($node==$this->head) return ;
        //调整前后指针指向
        $node->pre->next=$node->next;
        $node->next->pre=$node->pre;
        $node->next=$this->head;
        $this->head->pre=$node;
        $this->head=$node;
        $node->pre=null;
    }
}
class Node{
    public $key;
    public $val;
    public $next;
    public $pre;
    public function __construct($val)
{
        $this->val=$val;
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);

Adresse Github :https://github.com/wuqinqiang/leetcode-php

Pour plus de connaissances sur PHP, veuillez visiter le Site Web PHP chinois!

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!