Implementierung des LRU-Cache-Eviction-Algorithmus mit PHP

LRU(cache)

LRU-Einführung

Cache ist eine Technologie, die die Datenleseleistung verbessert. Bei Computern ist es jedoch unmöglich, alle Daten zwischenzuspeichern. Wenn der kritische Speicherplatz erreicht ist, müssen wir mithilfe einiger Regeln einen Teil der zwischengespeicherten Daten durch neue Daten ersetzen. Was wäre, wenn Sie es zu diesem Zeitpunkt ersetzen würden?

Es gibt viele Ersetzungsstrategien, die am häufigsten verwendeten sind wie folgt:

● FIFO (First-In-First-Out-Strategie)

● LFU (Least-Used-Strategie)

● LRU (zuletzt verwendete Richtlinie)

● NMRU (wählen Sie zufällig einen Ersatz im Cache aus, der in letzter Zeit nicht verwendet wurde)

Da dieser Artikel hauptsächlich LRU implementiert, also dort Nein, ich werde andere Dinge vorstellen, Sie können sie selbst kennenlernen.

Angenommen, Sie haben bereits 5 Freundinnen und haben erfolgreich eine neue Freundin gefunden. Während Sie süchtig nach Frauen sind, stellen Sie überrascht fest, dass Sie nicht mehr so ​​gegeneinander kämpfen können wie früher Wenn du sechs bist, musst du ein paar Freundinnen aufgeben. Zu diesem Zeitpunkt zeigst du, der Drecksack mit sechs Freundinnen, deine Drecksnatur und verabschiedest dich von dem Mädchen, das in letzter Zeit die geringste Zuneigung gezeigt hat. Es tut mir leid, Basketball-Nationalmannschaft. Zu diesem Zeitpunkt muss ich aufstehen und den Ball an der Seitenlinie aufschlagen. „Auf diese Weise erreicht Ihr Körper das Kritische.“ Punkt, und Sie müssen andere junge Damen im Stich lassen.

Das Folgende ist ein praktisches Bild, um sein Prinzip zu verstehen.

Anhand des obigen Bildes wissen wir, dass der Vorgang von LRU nichts weiter ist als Einfügen, Löschen und Ersetzen, wenn der Cache-Speicherplatz voll ist , dann für den Kopf einfügen und für den Schwanz löschen. Wenn der Cache nicht voll ist, gibt es zwei Arten: Wenn der Cache erreicht ist, müssen Sie nur den zwischengespeicherten Wert in den Kopf verschieben. Wenn es vorher nicht existierte, wird es in den Kopf eingefügt.

Implementierungsprozess

Der nächste Schritt ist die Auswahl der Datenstruktur. Die Speicherung des Arrays ist ein kontinuierlicher Speicherplatz. Obwohl die zeitliche Komplexität der Abfrage O (1) beträgt, müssen Löschung und Einfügung verschoben werden, um die Kontinuität des Speicherplatzes zu gewährleisten, sodass die zeitliche Komplexität O (n) beträgt ). Um eine schnelle Löschung zu erreichen, wird eine doppelt verknüpfte Liste verwendet. Die Komplexität der Abfragezeit der verknüpften Liste beträgt jedoch O (n), sodass eine Hash-Tabelle erforderlich ist. So viel Blödsinn, Code-Implementierung. Tatsächlich habe ich diese Frage schon einmal beantwortet. Lassen Sie mich konkret darauf eingehen.

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

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

Weitere PHP-Kenntnisse finden Sie auf der PHP-Chinese-Website!

Das obige ist der detaillierte Inhalt vonImplementierung des LRU-Cache-Eviction-Algorithmus mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!