欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

PHP實(shí)現(xiàn)LRU算法的示例代碼

 更新時(shí)間：2022年06月30日 09:23:14   作者：PHP開(kāi)源社區(qū)  
LRU是Least Recently Used 近期最少使用算法， 內(nèi)存管理的一種頁(yè)面置換算法。本文將詳解LRU算法的原理以及實(shí)現(xiàn)，感興趣的小伙伴可以學(xué)習(xí)一下

原理

LRU是Least Recently Used 近期最少使用算法。 內(nèi)存管理的一種頁(yè)面置換算法，對(duì)于在內(nèi)存中但又不用的數(shù)據(jù)塊（內(nèi)存塊）叫做LRU，操作系統(tǒng)會(huì)根據(jù)哪些數(shù)據(jù)屬于LRU而將其移出內(nèi)存而騰出空間來(lái)加載另外的數(shù)據(jù)。

什么是LRU算法？LRU是Least Recently Used的縮寫，即最近最久未使用，常用于頁(yè)面置換算法，是為虛擬頁(yè)式存儲(chǔ)管理服務(wù)的。

關(guān)于操作系統(tǒng)的內(nèi)存管理，如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源，一直是研究的重要方向。而內(nèi)存的虛擬存儲(chǔ)管理，是現(xiàn)在最通用，最成功的方式—— 在內(nèi)存有限的情況下，擴(kuò)展一部分外存作為虛擬內(nèi)存，真正的內(nèi)存只存儲(chǔ)當(dāng)前運(yùn)行時(shí)所用得到信息。這無(wú)疑極大地?cái)U(kuò)充了內(nèi)存的功能，極大地提高了計(jì)算機(jī)的并發(fā)度。

虛擬頁(yè)式存儲(chǔ)管理，則是將進(jìn)程所需空間劃分為多個(gè)頁(yè)面，內(nèi)存中只存放當(dāng)前所需頁(yè)面，其余頁(yè)面放入外存的管理方式。

然而，有利就有弊，虛擬頁(yè)式存儲(chǔ)管理減少了進(jìn)程所需的內(nèi)存空間，卻也帶來(lái)了運(yùn)行時(shí)間變長(zhǎng)這一缺點(diǎn)：進(jìn)程運(yùn)行過(guò)程中，不可避免地要把在外存中存放的一些信息和內(nèi)存中已有的進(jìn)行交換，由于外存的低速，這一步驟所花費(fèi)的時(shí)間不可忽略。

因而，采取盡量好的算法以減少讀取外存的次數(shù)，也是相當(dāng)有意義的事情。

基本原理

假設(shè) 序列為 4 3 4 2 3 1 4 2物理塊有3個(gè) 則首輪 4調(diào)入內(nèi)存 4次輪 3調(diào)入內(nèi)存 3 4之后 4調(diào)入內(nèi)存 4 3之后 2調(diào)入內(nèi)存 2 4 3之后 3調(diào)入內(nèi)存 3 2 4之后 1調(diào)入內(nèi)存 1 3 2（因?yàn)樽钌偈褂玫氖?，所以丟棄4）之后 4調(diào)入內(nèi)存 4 1 3（原理同上）最后 2調(diào)入內(nèi)存 2 4 1

規(guī)律就是，如果新存入或者訪問(wèn)一個(gè)值，則將這個(gè)值放在隊(duì)列開(kāi)頭。如果存儲(chǔ)容量超過(guò)上限cap，那么刪除隊(duì)尾元素，再存入新的值。

整體設(shè)計(jì)

用數(shù)組保存緩存對(duì)象(Node);

緩存對(duì)象(Node)之間通過(guò)nextKey,preKey組成一個(gè)雙向鏈表;

保存鏈表頭 跟尾;

處理流程

主要代碼

Node 節(jié)點(diǎn)類

/**
?*?緩存值保存類，
?*?Class?Node
?*?@package?app\common\model
?*/
class?Node{
????private?$preKey=null;//鏈表前一個(gè)節(jié)點(diǎn)
????private?$nextKey=null;//鏈表后一個(gè)節(jié)點(diǎn)
????private?$value=null;//當(dāng)前的值
????private?$key=null;//當(dāng)前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;
????}
}

緩存類

/**
?*?實(shí)現(xiàn)lru緩存
?*?Class?LruCache
?*?@package?app\common\model
?*/
class?LruCache
{
????public?$cacheTable?=[];
????private?$headNode=null;
????private?$lastNode=null;
????private?$cacheCount=0;
????private?$cacheMax=100;


????/**
?????*?測(cè)試輸出使用
?????*/
????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){

????????//設(shè)置值為null，則認(rèn)為刪除緩存節(jié)點(diǎn)
????????if?($value===null){
????????????$this->del($key);
????????????return?true;
????????}

????????//判斷是否存在表中,存在則更新連表
????????if?(!empty($this->cacheTable[$key])){
????????????$this->updateList($key);
????????????return?true;
????????}

????????//先判斷是否要?jiǎng)h除
????????$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];

????????????//摘出節(jié)點(diǎn)
????????????$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;
????}


????//直接添加節(jié)點(diǎn)
????private?function?addNode($key,$value){
????????$addNode=new?Node($key,$value);
????????if?(!empty($this->headNode)){
????????????$this->headNode->setPreKey($addNode);
????????}
????????$addNode->setNextKey($this->headNode);

????????//第一次保存最后一個(gè)節(jié)點(diǎn)為頭節(jié)點(diǎn)
????????if?($this->lastNode==null){
????????????$this->lastNode=$addNode;
????????}
????????$this->headNode=$addNode;
????????$this->cacheTable[$key]=$addNode;
????????$this->cacheCount++;
????}


????//主動(dòng)刪超出的緩存
????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--;
????????}

????}

????//更新節(jié)點(diǎn)鏈表
????private?function?updateList($key){
????????//這里需要使用引用傳值
????????$node=&$this->cacheTable[$key];

????????//當(dāng)前結(jié)點(diǎn)為頭結(jié)點(diǎn)?直接不用處理
????????if?($this->headNode===$node){
????????????return?true;
????????}

????????//摘出結(jié)點(diǎn)
????????$this->jumpNode($node);
????????//跟頭結(jié)點(diǎn)交換
????????$node->setNextKey($this->headNode);
????????$this->headNode->setPreKey($node);
????????$node->setPreKey(null);
????????$this->headNode=$node;

????????return?true;

????}


????//將某個(gè)節(jié)點(diǎn)摘出來(lái)
????private?function?jumpNode(Node?&$node){
????????if?(!empty($node->getPreKey())){
????????????$node->getPreKey()->setNextKey($node->getNextKey());
????????}

????????if?(!empty($node->getNextKey())){
????????????$node->getNextKey()->setPreKey($node->getPreKey());
????????}

????????//如果是最后一個(gè)節(jié)點(diǎn),則更新最后節(jié)點(diǎn)為它的前節(jié)點(diǎn)
????????if?($node->getNextKey()==null){
????????????$this->lastNode=$node->getPreKey();
????????}

????????//如果是頭結(jié)點(diǎn)
????????if?($node->getPreKey()==null){
????????????$this->headNode=$node->getNextKey();
????????}
????}



}

測(cè)試代碼

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();

}

其實(shí)php的數(shù)組就是有序的,也可以直接用php數(shù)組實(shí)現(xiàn),這里只是提供一個(gè)實(shí)現(xiàn)的思路，僅供參考哈！

以上就是PHP實(shí)現(xiàn)LRU算法的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于PHP LRU算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

最新評(píng)論