PHPを使用したLRUキャッシュエビクションアルゴリズムの実装

#LRU(キャッシュ)

LRU 概要

キャッシュは、データ読み取りパフォーマンスを向上させるテクノロジーです。しかし、コンピュータの場合、すべてのデータをキャッシュすることは不可能であり、重要な容量に達すると、キャッシュされたデータの一部を何らかのルールに従って新しいデータに置き換える必要があります。この時点で交換することを選択した場合はどうなりますか?

多くの置換戦略​​があり、一般的に使用されるのは次のとおりです:

#● FIFO (先入れ先出し戦略)

● LFU (最も使用されない戦略)

# LRU (最も最近使用されていないポリシー)

● NMRU (最近使用されていないキャッシュ内の置き換えをランダムに選択します)

この記事では主に LRU を実装しているため、いいえ、他のことも紹介しますので、ご自身で学んでください。

あなたにはすでに 5 人のガールフレンドがいて、新しいガールフレンドとうまく付き合うことができたとします。女性に夢中になっている一方で、以前のように互いに争うことができなくなったことに驚いたとします。若いです。6歳になると、何人かの彼女を諦めなければなりません。このとき、6人の彼女を持つクズなあなたは、クズの本性を完全に示し、最近最も愛情を示していない女の子に別れを告げます：「私」 「ごめんなさい、バスケットボール代表チーム。この時間、私は立ち上がってサイドラインボールをサーブしなければなりません。私、ナン・チキ、さよならを言います。」 このようにして、新しい若い女性とうまく接続し、あなたの体が臨界に達したときつまり、他の若い女性を見捨てなければなりません。

以下はその原理を理解するための実践的な図です。

上記の図から、LRU の操作は挿入、削除、置換にすぎないことがわかります。 、次に先頭に挿入し、末尾を削除します。フルでない場合は2種類あり、1つはキャッシュがヒットした場合、キャッシュされた値を先頭に移動するだけで済むものです。以前に存在しなかった場合は、先頭に挿入されます。

実装プロセス

次のステップはデータ構造の選択です。配列のストレージは連続したメモリ空間です。クエリの時間計算量は O (1) ですが、メモリ空間の連続性を維持するには削除と挿入を移動する必要があるため、時間計算量は O (n ). 迅速な削除を実現するために、二重リンクリストが使用されます。ただし、リンク リストのクエリ時間の複雑さは O (n) であるため、ハッシュ テーブルが必要です。コードの実装はでたらめです。実際、私は以前にこの質問に答えたことがあります。具体的にお話しましょう。

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 中国語 Web サイトの他の関連記事を参照してください。