Implementing LRU cache eviction algorithm using PHP

LRU(cache)

LRU Introduction

Cache is a technology that improves data reading performance. But for computers, it is impossible to cache all data. When its critical space is reached, we need to replace part of the cached data with new data through some rules. What if you choose to replace it at this time?

There are many replacement strategies, the following are commonly used:

● FIFO (first in, first out strategy)

● LFU (least used strategy)

● LRU (Least Recently Used Policy)

● NMRU (Randomly select a replacement in the cache that has not been used recently)

Since this article mainly implements LRU, so there is no I’m going to introduce other things, you can learn about them by yourself.

Suppose you already have 5 girlfriends, and you successfully hook up with a new girlfriend. While you are addicted to women, you are surprised to find that you can no longer fight against each other like you did when you were young. When you are six, you have to give up a few girlfriends. At this time, you, the scumbag with six girlfriends, completely show your scumbag nature and say goodbye to the girl who has shown the least affection recently: "I'm sorry, National Basketball Team At this time, I need to stand up and serve the sideline ball. I, Nan Ciqi, say goodbye." In this way, when you successfully hook up with a new young lady and your body reaches the critical point, you must abandon other young ladies.

The following is a practical picture to understand its principle.

Based on the above picture, we know that the operation of LRU is nothing more than insertion, deletion, and replacement. For replacement, if the cache space If it is full, then insert to head and delete for tail. If it is not full, there are two types. One is that if the cache hits, you only need to move the cached value to head. If it didn't exist before, it's insert to head.

Implementation process

The next step is the selection of data structure. The storage of the array is a continuous memory space. Although the time complexity of the query is O (1), deletion and insertion need to be moved in order to preserve the continuity of the memory space, so the time complexity is O (n). In order to achieve For quick deletion, a doubly linked list is used. But the query time complexity of the linked list is O (n), so a hash table is needed. So much bullshit, code implementation. In fact, I have answered this question before. Let me talk about it specifically.

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 arrangement address:https://github.com/wuqinqiang/leetcode-php

For more PHP knowledge, please visit PHP中文网!

The above is the detailed content of Implementing LRU cache eviction algorithm using PHP. For more information, please follow other related articles on the PHP Chinese website!