PHP에서 LRU 알고리즘을 구현하기 위한 샘플 코드
- WBOY앞으로
- 2022-07-26 13:59:252735검색
이 글에서는 PHP 관련 지식을 주로 소개합니다. LRU는 메모리 관리를 위한 페이지 교체 알고리즘인 LRU 알고리즘에 대해 자세히 살펴보겠습니다. 모두에게 도움이 되기를 바랍니다.
(권장 튜토리얼: PHP 비디오 튜토리얼)
Principle
LRU는 가장 최근에 사용된 알고리즘입니다. 메모리 관리를 위한 페이지 교체 알고리즘입니다. 메모리에 있지만 사용되지 않는 데이터 블록(메모리 블록)을 LRU라고 합니다. 운영 체제는 로드할 공간을 확보하기 위해 LRU에 속한 데이터를 메모리 밖으로 이동합니다. 다른 데이터.
LRU 알고리즘이란 무엇인가요? LRU는 Least Recent Used의 약자로 가장 오랫동안 사용되지 않았다는 의미로 페이지 교체 알고리즘에 자주 사용되며 가상 페이지 저장 관리 역할을 합니다.
운영체제의 메모리 관리와 관련하여, 가장 많은 프로세스에 자원을 제공하기 위해 작은 메모리를 어떻게 저장하고 활용하는지는 항상 중요한 연구 방향이었습니다. 메모리의 가상 스토리지 관리는 현재 가장 일반적이고 성공적인 방법입니다. 메모리가 제한되면 외부 메모리의 일부가 가상 메모리로 확장되고 실제 메모리는 현재 런타임 동안 사용되는 정보만 저장합니다. 이는 의심할 여지없이 메모리 기능을 크게 확장하고 컴퓨터의 동시성을 크게 향상시킵니다.
가상 페이지 저장 관리는 프로세스에 필요한 공간을 여러 페이지로 나누어 현재 필요한 페이지만 메모리에 저장하고, 나머지 페이지는 외부 메모리에 넣는 관리 방법입니다.
그러나 장점과 단점이 있습니다. 가상 페이지 저장 관리는 프로세스에 필요한 메모리 공간을 줄이지만 실행 시간이 길어진다는 단점도 있습니다. 프로세스가 실행 중일 때 외부 메모리에 저장할 수밖에 없습니다. 일부 정보는 이미 메모리에 있는 것과 교환됩니다. 외부 메모리의 속도가 느리기 때문에 이 단계에서 소요되는 시간을 무시할 수 없습니다.
따라서 외부 메모리에서 읽는 횟수를 줄이기 위해 가능한 최고의 알고리즘을 채택한다는 것은 매우 의미가 있습니다.
기본 원리
순서가 4 3 4 2 3 1 4 2라고 가정합니다. 그러면 4의 첫 번째 라운드가 메모리로 전송됩니다. 4 이후에는 4가 메모리로 전송됩니다. 3 이후에는 2가 메모리로 전송됩니다. 2 4 3 이후에는 3이 메모리 3으로 전송됩니다. 2 4 이후에는 1이 메모리 1 3 2로 전송됩니다. 사용된 1은 4이므로 4는 버려집니다), 4는 메모리 4 1 3으로 전송되고(원리는 위와 동일) 마지막으로 2가 메모리 2 4 1로 전송됩니다
규칙은 다음과 같습니다. 새로 저장되거나 액세스되면 값은 대기열의 시작 부분에 배치됩니다. 저장 용량이 상한을 초과하는 경우 대기열 끝의 요소를 삭제하고 새 값을 저장합니다.
전체 디자인
배열을 사용하여 캐시 개체(노드)를 저장합니다.
캐시 개체(노드)는 nextKey 및 preKey를 통해 양방향 연결 목록을 형성합니다.
연결 목록의 머리 부분과 끝 부분을 저장합니다. 처리 과정
메인 코드
노드 노드 클래스
/**
* 缓存值保存类，
* 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!