搜索
首页后端开发php教程使用 PHP 实现 LRU 缓存淘汰算法

LRU(cache)

LRU 介绍

缓存是一种提高数据读取性能的技术。但是对于计算机来说,并不可能缓存所有的数据,在达到它的临界空间时,我们需要通过一些规则用新的数据取代掉一部分的缓存数据。这时候你会如果选择替换呢?

替换的策略有很多种,常用的有以下几种:

● FIFO (先进先出策略)

● LFU (最少使用策略)

● LRU (最近最少使用策略)

● NMRU (在最近没有使用的缓存中随机选择一个替换)

介于我这篇主要实现 LRU,所以就不去介绍其他的了,可以自行去了解。

假设你已经有 5 个女朋友了,此时你成功勾搭上一个新女朋友,在你沉迷女色的同时,你惊奇的发现,你已经不能像年轻时一样以一敌六了,你必须舍弃若干个女朋友,这时候,身拥六个女朋友的渣男你,彻底展示出你的渣男本色,和最近最少秀恩爱的小姐姐说再见:“对不起,国篮此时需要我挺身发边线球,我楠辞琦咎,再见。”,就这样在你成功勾搭一个新小姐姐,你的身体临界点的同时,你就必须舍弃其他的小姐姐。

下面来张实际点的图搞清楚他的原理。

9ace0279c955cd4b1f070ade5df7ffe.png

基于上述图片,我们知道,对于 LRU 的操作,无非在于插入 (insert), 删除 (delete),以及替换,针对替换来说,如果缓存空间满了,那么就是 insert to head and delete for tail。如果未满,也分为两种,一种是缓存命中的话,只需要把缓存的值 move to head。如果之前不存在,那么就是 insert to head。

实现过程

接下来就是数据结构的选择了。数组的存储是连续的内存空间,虽然查询的时间复杂度是 O (1), 但是删除和插入为了保存内存空间的连续性,需要进行搬移,那么时间复杂度就是 O (n), 为了实现能快速删除,故而采用双向链表。但是链表的查询时间复杂度是 O (n), 那么就需要 hash table。屁话说了这么多,代码实现。其实之前刷过这道题目。特地拿出来讲一下。

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中文网其他相关文章!

声明
本文转载于:learnku。如有侵权,请联系admin@php.cn删除
您如何防止与会议有关的跨站点脚本(XSS)攻击?您如何防止与会议有关的跨站点脚本(XSS)攻击?Apr 23, 2025 am 12:16 AM

要保护应用免受与会话相关的XSS攻击,需采取以下措施:1.设置HttpOnly和Secure标志保护会话cookie。2.对所有用户输入进行输出编码。3.实施内容安全策略(CSP)限制脚本来源。通过这些策略,可以有效防护会话相关的XSS攻击,确保用户数据安全。

您如何优化PHP会话性能?您如何优化PHP会话性能?Apr 23, 2025 am 12:13 AM

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显着提升应用在高并发环境下的效率。

什么是session.gc_maxlifetime配置设置?什么是session.gc_maxlifetime配置设置?Apr 23, 2025 am 12:10 AM

thesession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceIsiseededeedeedeedeedeedeedto to to avoidperformance andununununununexpectedLogOgouts.3)

您如何在PHP中配置会话名?您如何在PHP中配置会话名?Apr 23, 2025 am 12:08 AM

在PHP中,可以使用session_name()函数配置会话名称。具体步骤如下:1.使用session_name()函数设置会话名称,例如session_name("my_session")。2.在设置会话名称后,调用session_start()启动会话。配置会话名称可以避免多应用间的会话数据冲突,并增强安全性,但需注意会话名称的唯一性、安全性、长度和设置时机。

您应该多久再生一次会话ID?您应该多久再生一次会话ID?Apr 23, 2025 am 12:03 AM

会话ID应在登录时、敏感操作前和每30分钟定期重新生成。1.登录时重新生成会话ID可防会话固定攻击。2.敏感操作前重新生成提高安全性。3.定期重新生成降低长期利用风险,但需权衡用户体验。

如何在PHP中设置会话cookie参数?如何在PHP中设置会话cookie参数?Apr 22, 2025 pm 05:33 PM

在PHP中设置会话cookie参数可以通过session_set_cookie_params()函数实现。1)使用该函数设置参数,如过期时间、路径、域名、安全标志等;2)调用session_start()使参数生效;3)根据需求动态调整参数,如用户登录状态;4)注意设置secure和httponly标志以提升安全性。

在PHP中使用会议的主要目的是什么?在PHP中使用会议的主要目的是什么?Apr 22, 2025 pm 05:25 PM

在PHP中使用会话的主要目的是维护用户在不同页面之间的状态。1)会话通过session_start()函数启动,创建唯一会话ID并存储在用户cookie中。2)会话数据保存在服务器上,允许在不同请求间传递数据,如登录状态和购物车内容。

您如何在子域中分享会议?您如何在子域中分享会议?Apr 22, 2025 pm 05:21 PM

如何在子域名间共享会话?通过设置通用域名的会话cookie实现。1.在服务器端设置会话cookie的域为.example.com。2.选择合适的会话存储方式,如内存、数据库或分布式缓存。3.通过cookie传递会话ID,服务器根据ID检索和更新会话数据。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。