LRU 介紹

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

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

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

● LFU (最少使用策略)

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

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

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

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

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

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

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

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

html' target='_blank'>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++;    }    //移除指針(已存在的鍵值對(duì)或者刪除最近最少使用原則)    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--;    }    //把對(duì)應(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);

Github 整理地址:https://github.com/wuqinqiang/leetcode-php

更多PHP知識(shí)，請(qǐng)?jiān)L問PHP中文網(wǎng)！

以上就是使用 PHP 實(shí)現(xiàn) LRU 緩存淘汰算法的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注 其它相關(guān)文章！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。