PHP怎么實(shí)現(xiàn) LRU 緩存淘汰算法

這篇文章將為大家詳細(xì)講解有關(guān)PHP怎么實(shí)現(xiàn) LRU 緩存淘汰算法，小編覺得挺實(shí)用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

LRU(cache)

緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)。但是對于計(jì)算機(jī)來說，并不可能緩存所有的數(shù)據(jù)，在達(dá)到它的臨界空間時，我們需要通過一些規(guī)則用新的數(shù)據(jù)取代掉一部分的緩存數(shù)據(jù)。這時候你會如果選擇替換呢？

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

● FIFO (先進(jìn)先出策略)

● LFU (最少使用策略)

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

● NMRU (在最近沒有使用的緩存中隨機(jī)選擇一個替換)

介于我這篇主要實(shí)現(xiàn) LRU，所以就不去介紹其他的了，可以自行去了解。

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

下面來張實(shí)際點(diǎn)的圖搞清楚他的原理。

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

實(shí)現(xiàn)過程

接下來就是數(shù)據(jù)結(jié)構(gòu)的選擇了。數(shù)組的存儲是連續(xù)的內(nèi)存空間，雖然查詢的時間復(fù)雜度是 O (1), 但是刪除和插入為了保存內(nèi)存空間的連續(xù)性，需要進(jìn)行搬移，那么時間復(fù)雜度就是 O (n), 為了實(shí)現(xiàn)能快速刪除，故而采用雙向鏈表。但是鏈表的查詢時間復(fù)雜度是 O (n), 那么就需要 hash table。屁話說了這么多，代碼實(shí)現(xiàn)。其實(shí)之前刷過這道題目。特地拿出來講一下。

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;
    }
    //新加入的節(jié)點(diǎn)
    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]);
        //調(diào)整指針
        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--;
    }
    //把對應(yīng)的節(jié)點(diǎn)應(yīng)到鏈表頭部(最近get或者剛剛put進(jìn)去的node節(jié)點(diǎn))
    public function moveToHead(Node $node)
{
        if($node==$this->head) return ;
        //調(diào)整前后指針指向
        $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);

關(guān)于PHP怎么實(shí)現(xiàn) LRU 緩存淘汰算法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。