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中文網其他相關文章！
