PHP를 사용하여 LRU 캐시 제거 알고리즘 구현

LRU(캐시)

LRU 소개

캐시는 데이터 읽기 성능을 향상시키는 기술입니다. 그러나 컴퓨터의 경우 모든 데이터를 캐시하는 것은 불가능합니다. 중요한 공간에 도달하면 몇 가지 규칙을 통해 캐시된 데이터의 일부를 새로운 데이터로 교체해야 합니다. 이때 교체를 선택하면 어떻게 되나요?

많은 교체 전략이 있으며 일반적으로 사용되는 전략은 다음과 같습니다.

● FIFO(선입선출 전략)

● LFU(최소 사용 전략)

● LRU(최소 최근 사용 전략)

● NMRU ( 최근 사용하지 않은 캐시에서 대체캐시 랜덤선택 )

이번 글에서는 주로 LRU를 구현하였기 때문에 다른 내용은 소개하지 않으니 직접 배워보시면 좋을 것 같습니다.

당신에게 이미 5명의 여자친구가 있고 새로운 여자친구를 성공적으로 사귀었다고 가정해 보세요. 당신은 여성에 중독되어 있지만 더 이상 어렸을 때처럼 6명과 싸울 수 없다는 사실에 놀랐습니다. 이때 여자친구 여섯 명을 둔 쓰레기인 당신은 쓰레기 성격을 완전히 드러내며 최근 애정이 가장 적은 여자에게 "미안해요. 농구대표팀에 제가 필요해요." 지금은 일어서서 사이드라인 공을 서브하세요. 저는 Nan Ciqiu입니다. 안녕." 이렇게 새로운 젊은 여성과 성공적으로 연결되면 몸이 임계점에 도달하고 다른 젊은 여성을 버려야 합니다. .

다음은 원리를 이해하기 위한 실제 그림입니다.

위 그림을 통해 LRU의 작업은 삽입, 삭제, 교체에 불과하다는 것을 알 수 있습니다. 교체를 위해 캐시 공간이 가득 차면 헤드에 삽입하고 테일에 삭제합니다. 가득 차지 않은 경우에는 두 가지 유형이 있습니다. 하나는 캐시에 도달하면 캐시된 값만 헤드로 옮기면 된다는 것입니다. 이전에 존재하지 않았다면 헤드에 삽입됩니다.

구현 프로세스

다음 단계는 데이터 구조 선택입니다. 배열의 저장은 연속적인 메모리 공간이지만 질의의 시간복잡도는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!