使用 PHP 實作 LRU 快取淘汰演算法

LRU(cache)

LRU 介紹

快取是一種提高資料讀取效能的技術。但是對於電腦來說，並不可能快取所有的數據，在達到它的臨界空間時，我們需要透過一些規則用新的數據取代掉一部分的快取數據。這時候你會如果選擇替換呢？

替換的策略有很多種，常用的有以下幾種:

● FIFO (先進先出策略)

● LFU (最少使用策略)

● LRU (最近最少使用策略)

● NMRU (在最近沒有使用的快取中隨機選擇一個替換)

介於我這篇主要實現LRU，所以就不去介紹其他的了，可以自行去了解。

假設你已經有5 個女朋友了，此時你成功勾搭上一個新女朋友，在你沉迷女色的同時，你驚奇的發現，你已經不能像年輕時一樣以一敵六了，你必須捨棄若干個女朋友，這時候，身擁六個女朋友的渣男你，徹底展示出你的渣男本色，和最近最少秀恩愛的小姐姐說再見：“對不起，國籃此時需要我挺身發邊線球，我楠辭琦咎，再見。”，就這樣在你成功勾搭一個新小姐姐，你的身體臨界點的同時，你就必須捨棄其他的小姐姐。

下面來張實際點的圖搞清楚他的原理。

基於上述圖片，我們知道，對於LRU 的操作，無非在於插入(insert), 刪除(delete)，以及替換，針對替換來說，如果快取空間滿了，那麼就是insert to head and delete for tail。如果未滿，也分為兩種，一種是快取命中的話，只需要把快取的值 move to head。如果之前不存在，那麼就是 insert to head。

實作過程

接下來就是資料結構的選擇了。陣列的儲存是連續的記憶體空間，雖然查詢的時間複雜度是O (1), 但是刪除和插入為了保存記憶體空間的連續性，需要進行搬移，那麼時間複雜度就是O (n), 為了實現能快速刪除，故而採用雙向鍊錶。但是鍊錶的查詢時間複雜度是 O (n), 那就需要 hash table。屁話說了這麼多，程式碼實作。其實之前刷過這題。特地拿出來講一下。

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 整理網址:https://github.com/wuqinqiang/leetcode-php

更多PHP知識，請造訪PHP中文網！

以上是使用 PHP 實作 LRU 快取淘汰演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！