ホームページ >バックエンド開発 >PHPチュートリアル >PHP で LRU アルゴリズムを実装するためのサンプルコード
PHP で LRU アルゴリズムを実装するためのサンプルコード
- WBOY転載
- 2022-07-26 13:59:252854ブラウズ
この記事では、PHP に関する知識を中心に紹介します。LRU は、最も最近使用されたアルゴリズムであり、メモリ管理のためのページ置換アルゴリズムです。LRU アルゴリズムの原理と実装について詳しく説明します以下に、それを見てみましょう。皆さんのお役に立てれば幸いです。
(推奨チュートリアル: PHP ビデオ チュートリアル)
原則
LRU は最も最近使用されていないものです。アルゴリズム。メモリ管理のためのページ置換アルゴリズム。メモリ内にあるが使用されていないデータ ブロック (メモリ ブロック) は LRU と呼ばれます。オペレーティング システムは、どのデータが LRU に属しているかに基づいて、データ ブロックをメモリから移動し、ロード用のスペースを確保します。他のデータ。
LRU アルゴリズムとは何ですか? LRU は、Least Recent Used の略で、長期間使用されていないことを意味し、ページ置換アルゴリズムでよく使用され、仮想ページのストレージ管理を行います。
オペレーティング システムのメモリ管理に関しては、ほとんどのプロセスにリソースを提供するために、どのように小さなメモリを節約して利用するかが常に重要な研究方向です。メモリの仮想ストレージ管理は、現在最も一般的で成功している方法です。メモリが限られている場合、外部メモリの一部が仮想メモリとして拡張され、実メモリには現在の実行時に使用される情報のみが保存されます。これにより、メモリの機能が大幅に拡張され、コンピュータの同時実行性が大幅に向上することは間違いありません。
仮想ページ格納管理とは、プロセスに必要な領域を複数のページに分割し、現在必要なページのみをメモリ上に格納し、残りのページを外部メモリに置く管理方法です。
ただし、利点と欠点があります。仮想ページ ストレージ管理は、プロセスに必要なメモリ領域を削減しますが、実行時間が長くなるという欠点ももたらします。外部メモリに保存されている情報は、すでにメモリ内にある情報と交換されますが、外部メモリの速度が遅いため、このステップにかかる時間は無視できません。
したがって、外部メモリからの読み取り回数を減らすために可能な限り最適なアルゴリズムを採用することは非常に意味があります。
基本原理
シーケンスが 4 3 4 2 3 1 4 2 であると仮定します。物理ブロックが 3 つあり、最初のラウンドの 4 がメモリに転送されます。 3をメモリに転送 3のあと4、4をメモリに転送 4のあと、3をメモリに転送、2をメモリに転送 2のあと、3、3をメモリに転送、3 2、4のあと、1がメモリ 1 3 2 に転送されます (少なくとも 4 が使用されるため、4 は破棄されます)。4、4 がメモリに転送された後、4 1 3 (原理は上記と同じです) ) 最後の 2 がメモリに転送されます。メモリ 2 4 1
値が新しく格納またはアクセスされると、その値はキューの先頭に配置されるというルールです。格納容量が上限を超えた場合は、キューの末尾の要素を削除し、新しい値を格納します。
全体的な設計
配列を使用してキャッシュ オブジェクト (ノード) を保存します;
キャッシュ オブジェクト (ノード) は、nextKey と preKey を通じて双方向のリンク リストを形成します。
リンクリストの先頭と末尾を保存;
処理プロセス
メインコード
Nodeノードクラス
/**
* 缓存值保存类，
* Class Node
* @package app\common\model
*/
class Node{
private $preKey=null;//链表前一个节点
private $nextKey=null;//链表后一个节点
private $value=null;//当前的值
private $key=null;//当前key
public function __construct(string $key,$value)
{
$this->value=$value;
$this->key=$key;
}
public function setPreKey($preValue){
$this->preKey=$preValue;
}
public function setNextKey($nextValue){
$this->nextKey=$nextValue;
}
public function getPreKey(){
return $this->preKey;
}
public function getNextKey(){
return $this->nextKey;
}
public function getValue(){
return $this->value;
}
public function setValue($value){
$this->value=$value;
}
public function setKey(string $key){
$this->key=$key;
}
public function getKey(){
return $this->key;
}
}キャッシュ クラス
/**
* 实现lru缓存
* Class LruCache
* @package app\common\model
*/
class LruCache
{
public $cacheTable =[];
private $headNode=null;
private $lastNode=null;
private $cacheCount=0;
private $cacheMax=100;
/**
* 测试输出使用
*/
public function dumpAllData(){
if (!empty($this->headNode)){
$node=$this->headNode;
while (!empty($node)){
echo 'key='.$node->getKey().' nextKey='.(empty($node->getNextKey())?'null':$node->getNextKey()->getKey()).' preKey='.(empty($node->getPreKey())?'null':$node->getPreKey()->getKey()).' value='.$node->getValue()."</br>";
$node=$node->getNextKey();
}
}
}
/**
* @param int $count
*/
public function setCacheMax(int $count){
$this->cacheMax=$count;
}
/**
* @param string $key
* @param $value
* @return bool
*/
public function set(string $key,$value){
//设置值为null，则认为删除缓存节点
if ($value===null){
$this->del($key);
return true;
}
//判断是否存在表中,存在则更新连表
if (!empty($this->cacheTable[$key])){
$this->updateList($key);
return true;
}
//先判断是否要删除
$this->shiftNode();
$this->addNode($key,$value);
return true;
}
/**
* @param string $key
* @return bool
*/
public function del(string $key){
if (!empty($this->cacheTable[$key])){
$node=&$this->cacheTable[$key];
//摘出节点
$this->jumpNode($node);
//置空删除
$node->setPreKey(null);
$node->setNextKey(null);
unset($this->cacheTable[$key]);
return true;
}
return false;
}
/**
* @param string $key
* @return null
*/
public function get(string $key){
if (!empty($this->cacheTable[$key])){
$this->updateList($key);
return $this->cacheTable[$key]->getValue();
}
return null;
}
//直接添加节点
private function addNode($key,$value){
$addNode=new Node($key,$value);
if (!empty($this->headNode)){
$this->headNode->setPreKey($addNode);
}
$addNode->setNextKey($this->headNode);
//第一次保存最后一个节点为头节点
if ($this->lastNode==null){
$this->lastNode=$addNode;
}
$this->headNode=$addNode;
$this->cacheTable[$key]=$addNode;
$this->cacheCount++;
}
//主动删超出的缓存
private function shiftNode(){
while ($this->cacheCount>=$this->cacheMax){
if (!empty($this->lastNode)){
if (!empty($this->lastNode->getPreKey())){
$this->lastNode->getPreKey()->setNextKey(null);
}
$lastKey=$this->lastNode->getKey();
unset($this->cacheTable[$lastKey]);
}
$this->cacheCount--;
}
}
//更新节点链表
private function updateList($key){
//这里需要使用引用传值
$node=&$this->cacheTable[$key];
//当前结点为头结点 直接不用处理
if ($this->headNode===$node){
return true;
}
//摘出结点
$this->jumpNode($node);
//跟头结点交换
$node->setNextKey($this->headNode);
$this->headNode->setPreKey($node);
$node->setPreKey(null);
$this->headNode=$node;
return true;
}
//将某个节点摘出来
private function jumpNode(Node &$node){
if (!empty($node->getPreKey())){
$node->getPreKey()->setNextKey($node->getNextKey());
}
if (!empty($node->getNextKey())){
$node->getNextKey()->setPreKey($node->getPreKey());
}
//如果是最后一个节点,则更新最后节点为它的前节点
if ($node->getNextKey()==null){
$this->lastNode=$node->getPreKey();
}
//如果是头结点
if ($node->getPreKey()==null){
$this->headNode=$node->getNextKey();
}
}
}テスト コード
public function tt(){
$cath=model("LruCache");
$cath->setCacheMax(3);
$cath->set("aa","aaaaaaaaaaa");
$cath->set("bb","bbbbbbbbbbbb");
$cath->set("cc","ccccccccccccc");
$cath->get("aa");
// $cath->dumpAllData();
$cath->set("dd","ddddddddddddd");
// $cath->del("cc");
// var_dump($cath->cacheTable);
$cath->dumpAllData();
exit();
}実際、PHP 配列は順序付けされており、PHP 配列を使用して直接実装することもできます。ここでは参考のための実装アイデアを示します。のみ
(推奨チュートリアル: PHPビデオチュートリアル)
以上がPHP で LRU アルゴリズムを実装するためのサンプルコードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。