ホームページ バックエンド開発 PHPチュートリアル PHPを使用したLRUキャッシュエビクションアルゴリズムの実装

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

Sep 30, 2019 pm 02:43 PM
php

#LRU(キャッシュ)

LRU 概要

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

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

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

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

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

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

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

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

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

PHPを使用したLRUキャッシュエビクションアルゴリズムの実装上記の図から、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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットな記事タグ

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

CakePHP の日付と時刻 CakePHP の日付と時刻 Sep 10, 2024 pm 05:27 PM

CakePHP の日付と時刻

Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Dec 24, 2024 pm 04:42 PM

Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド

CakePHP ファイルのアップロード CakePHP ファイルのアップロード Sep 10, 2024 pm 05:27 PM

CakePHP ファイルのアップロード

CakePHP ルーティング CakePHP ルーティング Sep 10, 2024 pm 05:25 PM

CakePHP ルーティング

CakePHP について話し合う CakePHP について話し合う Sep 10, 2024 pm 05:28 PM

CakePHP について話し合う

CakePHP プロジェクトの構成 CakePHP プロジェクトの構成 Sep 10, 2024 pm 05:25 PM

CakePHP プロジェクトの構成

CakePHP クイックガイド CakePHP クイックガイド Sep 10, 2024 pm 05:27 PM

CakePHP クイックガイド

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法

See all articles