缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

这篇具有很好参考价值的文章主要介绍了缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章简介

  • CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考
  • 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org)
  • 在网上都找不到其他参考,只有这一篇1993年的论文

算法解析

LRU-K替换策略

  • LRU-K是LRU算法的一种衍生。强烈建议先做一下这一道题146. LRU 缓存 - 力扣(LeetCode)
  • 先看题目对该算法的描述

The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with less than k historical accesses is given +inf as its backward k-distance. When multipe frames have +inf backward k-distance, the replacer evicts the frame with the earliest timestamp.

  • 大意是,每次替换会优先替换k-距离最远的一个数。

  • 假如这个k是3,简单画一下一个实例,依次加入下面几个数

  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

  • 如果一个数出现次数达到了K次,那么k-distance就是倒数第K次出现的位置

  • 如果一个数出现不到K次,那么k-distance就是+inf

  • 这是对K-distance严谨的定义缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

驱逐策略

优先驱逐距离为 + i n f +inf +inf的frame,如果有多个这样的数,其实LRU-K是有多种策略来决定下一个驱逐谁的(比如用LRU),在本题目中

When multipe frames have +inf backward k-distance, the replacer evicts the frame with the earliest timestamp.

使用的先进先出(FIFO)策略,比如在上图中,4和1都出现了不足K次,如果要驱逐就驱逐先出现的4。
如果没有k-distance为正无穷的frame,优先驱逐该距离最大的。

一些重要的概念

我们需要理解为什么需要用LRU-K而非LRU策略

  • 假设:读取页的序列是随机的,但是每个页有一个比较稳定的概率被读取到,假设p被读取的概率是 b p b_p bp,那么我们可以预测,两次p被读取的间隔是 I p I_p Ip,并且 I p I_p Ip ( b p ) − 1 (b_p)^-1 (bp)1是正相关的(它们是反比关系)
  • 接下来列举一些情况,请思考它们(我不知道英文该怎么准确翻译,大概意会一下)
    • 内部事务(Intra-Transaction) :比如一个事务先读取一个页,然后在提交之前再次访问这个页。其实就是:用于更新的事务,先读取一列,再更新这列
    • 事务重试(Transaction-Retry):一个事务访问一个页然后中止。接下来重试这个事务并且再次访问这个页。
    • 内部流程(Intra-Process): 一个事务访问一个页面,并且成功提交了。然后下一个同样流程的事务再次访问这个页。这种模式的访问通常是由进行大量更新的程序引起的,比如连续更新100条记录
    • (Inter-Process)这个名字不知道怎么翻译了,注意上一个是Intra表达在一个Process里面,Inter表示在两个Process之间。这个例子是说:一个事务访问一个页,然后另外一个不同流程的事务也访问这个页。这两个事务之前是完全独立的,目的也不一样。
  • 上述四个例子的前三个被称作correlated reference-pair type,这种类型暂时被我叫做关联访问对,注意第四个例子是不关联的,如果我们通过这些关联访问对来估计前面提到的间隔时间 I p I_p Ip,通常会得到错误的结果。为什么这么说呢,考虑上面提到的例子一:我们要在一个事务更新时访问一个page两次,如果我们第一次访问后,估计 I p I_p Ip + i n f +inf +inf那么就会丢掉这个page,在第二次访问时又通过IO读入缓存造成浪费。如果我们通过这两次间隔时间来估计 I p I_p Ip,那么这个间隔时间是非常短的!我们就会造成一个误解:这个page很常用。但事实上这个更新事务已经结束了,可能很长一段时间内这个page不会被再次用到。
  • 所以我们可以得到这样一个结论:缓存系统不应该直接丢弃一个page,而是应该保留到下一次访问或者是保留到下一次访问的可能性变到很小的时候。
  • 在另外一方面,我们估计两次使用page的间隔时,不应该使用关联访问对来估计。
  • 如何判断两次访问是不是关联访问呢?一个方法是设置一个时间阈值,在阈值之下就是关联访问。
  • 关联访问可能是一连串的访问,而不只是两次。比如一百次对同一个页上记录的更新。我们把这一连串称为关联访问时期。在估计一个页两次使用间隔时,应该时计算一次关联访问的结束下一段关联访问开始之间的时间间隔。
  • 即使一个页面被驱逐,我们也需要保留这个访问历史一段时间。比如我们在第1秒访问了p,第二秒驱逐了p,第3秒又访问了p,第4秒驱逐了p,第5秒访问了p(这里不一定是秒,可以理解为很快)。那么实际上我们是以一个很高的频率在访问p,但是如果没有历史记录,我们是无法意识到这个事实的。这个历史保留时间被称为 R e t a i n e d I n f o r m a t i o n P e r i o d Retained Information Period RetainedInformationPeriod,论文中给出的建议时间是200s(一个拇指法则)

具体实现

数据结构约定

缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1文章来源地址https://www.toymoban.com/news/detail-411039.html

  • 在这里,首先定义了两个函数
    • 第一个是HIST(p),是关于p的访问记录(history)的。HIST(p,n)就是页面p倒数第n次被访问的时间。例如HIST(2,1)就是2号页面最后一次被访问的时间(这个是不算关联访问的,也就是说每段关联访问只被记录一次)
    • LAST(p)就是页面p最后一次被访问的时间,这个是无论关联访问的

伪代码实现

  • 每当我们新增一次访问记录,如果p已经被记录了,有两种情况
    • 这次访问在关联访问中,(也就是在他的前面已经有了其他关联访问),那么我们只需要更新LAST(p)就好了
    • 如果是一段新的访问,那么关闭旧的访问,并且计算 L A S T ( p ) − H I S T ( p , 1 ) LAST(p)-HIST(p,1) LAST(p)HIST(p,1)将他缩为一个点。
  • 如果这个page没有在buffer中,那么我们需要丢弃另外一个page(buffer满了的情况)
    • 一个正在关联访问时期中的page是不应该被丢掉的。
    • 优先选择K-distance最大的。也就是 b t ( q , K ) b_t(q,K) bt(q,K)最大,或者说是 H I S T ( q , K ) HIST(q,K) HIST(q,K)最小的。(之前看这个地方不理解,后来想通了:HIST是记录的时间,时间戳越小访问的越早,也就是距离越大)
  • 伪代码是长这样的
    缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1
  • 它这里的实现就是用了一个队列记录HIST不同的page出现时间,然后用了循环来寻找满足条件最小的时间戳。如果被驱逐的是个被修改过的页面,还需要将它写回硬盘。
  • 在实际的实现中,我们可以考虑用堆来优化这个寻找最大K-distance的过程。
  • 然后就是一些实验证明,有兴趣的可以去看下原文。这里就先不讲了缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1
    缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

C++实现

  • 这里我没有实现论文中区分关联访问的情况,而是将所有访问都视作独立的。

解析

  • 首先来看我们有哪些数据结构
  size_t current_timestamp_{0};
  size_t curr_size_{0};
  size_t max_size_;
  size_t replacer_size_;
  size_t k_;
  std::mutex latch_;

  using timestamp = std::list<size_t>;//记录单个页时间戳的列表
  using k_time = std::pair<frame_id_t,size_t>;
  std::unordered_map<frame_id_t,timestamp> hist;//用于记录所有页的时间戳
  std::unordered_map<frame_id_t,size_t> recorded_cnt_;//用于记录,访问了多少次
  std::unordered_map<frame_id_t,bool> evictable_;//用于记录是否可以被驱逐

  std::list<frame_id_t> new_frame_;//用于记录不满k次的页
  std::unordered_map<frame_id_t,std::list<frame_id_t>::iterator> new_locate_;

  std::list<k_time> cache_frame_;//用于记录到达k次的页
  std::unordered_map<frame_id_t,std::list<k_time>::iterator> cache_locate_;
名称 作用
current_timestamp_ 当前的时间戳,每进行一次record操作加一
curr_size_ 当前存放的可驱逐页面数量
max_size 最多可驱逐页面数量(去掉被pin住的页面)
replacer_size_ 整个主存大小(包括被pin的页面)
k_ lru-k中的k值
latch_ 用于维护多线程的锁
timestamp 单个页面的一连串时间戳
k_time 页面和kth时间戳
hist 所有页面的访问记录
recorded_cnt_ 被访问次数的记录
evictable 记录一个页面是否可以被驱逐
new_frame_ 记录不满足k次访问页的页号
new_locate_ 页号到上面这个链表迭代器的哈希表
cache_frame 到达k次页的链表
cache_locate_ 哈希表,解释同上
  • 对于满足访问过k次的和没到达k次的,我们可以通过两个链表来管理
  • 第一个链表是不满足k次的,我们每次通过头插法加入新的页面,如果要在这里面驱逐一个页面,采用reverse_iterator反向迭代器从后往前遍历,查找允许被驱逐的页面缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1
  • 接着我们定义一个新的类型,using k_time = std::pair<frame_id_t,size_t>;这个表示页面对应的倒数第k次访问的时间戳。
  • std::list<k_time> cache_frame_;//用于记录到达k次的页
    std::unordered_map<frame_id_t,std::list<k_time>::iterator> cache_locate_;
    
    • 我们定义一个新的链表,这个链表是按照时间戳从小到大排列的
    • 也就是说,越前面的页它的k-distance越大
  • 我们通过二分查找维护这个cache_frame_的稳定性
	auto kth_time = hist[frame_id].front();//获取当前页面的倒数第k次出现的时间
     k_time new_cache(frame_id,kth_time);

     auto it = std::upper_bound(cache_frame_.begin(),cache_frame_.end(),new_cache, CmpTimestamp);//找到该插入的位置
     it = cache_frame_.insert(it,new_cache);
     cache_locate_[frame_id] = it;
  • 然后来看方法列表
方法原型 作用
LRUKReplacer(size_t num_frames, size_t k) 生成器,num_frames是最大缓存,k是lru_k中的k值
auto Evict(frame_id_t *frame_id) -> bool 驱逐一个页面,并保存到frame_id中
void RecordAccess(frame_id_t frame_id); 增加一个页面的访问记录
void SetEvictable(frame_id_t frame_id, bool set_evictable); 设置一个页面是否可以被驱逐
void Remove(frame_id_t frame_id); 移除指定页面
auto Size() -> size_t; 返回可驱逐页面的大小

源码

LRU-K.h
//
// Created by Anti on 2022/12/27.
//

#ifndef LRU_K_H
#define LRU_K_H
#include <limits>
#include <list>
#include <mutex>
#include <unordered_map>
#include <vector>
#include <algorithm>

class  LRUKReplacer {
public:
    using frame_id_t = int;
    explicit LRUKReplacer(size_t num_frames, size_t k);
    ~LRUKReplacer()=default;


    auto Evict(frame_id_t *frame_id) -> bool;

    void RecordAccess(frame_id_t frame_id);

    void SetEvictable(frame_id_t frame_id, bool set_evictable);

    void Remove(frame_id_t frame_id);

    auto Size() -> size_t;

private:
    size_t current_timestamp_{0};
    size_t curr_size_{0};
    size_t max_size_;
    size_t replacer_size_;
    size_t k_;
    std::mutex latch_;

    using timestamp = std::list<size_t>;//记录单个页时间戳的列表
    using k_time = std::pair<frame_id_t,size_t>;
    std::unordered_map<frame_id_t,timestamp> hist;//用于记录所有页的时间戳
    std::unordered_map<frame_id_t,size_t> recorded_cnt_;//用于记录,访问了多少次
    std::unordered_map<frame_id_t,bool> evictable_;//用于记录是否可以被驱逐

    std::list<frame_id_t> new_frame_;//用于记录不满k次的页
    std::unordered_map<frame_id_t,std::list<frame_id_t>::iterator> new_locate_;

    std::list<k_time> cache_frame_;//用于记录到达k次的页
    std::unordered_map<frame_id_t,std::list<k_time>::iterator> cache_locate_;
    static auto CmpTimestamp(const k_time &f1,const k_time &f2) -> bool;
};
#endif //LRU_K_H

LRU-K.cpp
//
// Created by Anti on 2022/12/27.
//

#include "LRU_K.h"
LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {
    max_size_=num_frames;
}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
    std::lock_guard<std::mutex> lock(latch_);
    /**
     * 如果没有可以驱逐元素
     */
    if(Size()==0)
    {
        return false;
    }
    /**
     * 首先尝试删除距离为无限大的缓存
     */
    for(auto it = new_frame_.rbegin();it!=new_frame_.rend();it++)
    {
        auto frame = *it;
        if(evictable_[frame])//如果可以被删除
        {
            recorded_cnt_[frame] = 0;
            new_locate_.erase(frame);
            new_frame_.remove(frame);
            *frame_id = frame;
            curr_size_--;
            hist[frame].clear();
            return true;
        }
    }
    /**
     * 再尝试删除已经访问过K次的缓存
     */
    for(auto it =cache_frame_.begin();it!=cache_frame_.end();it++)
    {
        auto frame = (*it).first;
        if(evictable_[frame])
        {
            recorded_cnt_[frame] = 0;
            cache_frame_.erase(it);
            cache_locate_.erase(frame);
            *frame_id = frame;
            curr_size_--;
            hist[frame].clear();
            return true;
        }
    }
    return false;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id)
{
    std::lock_guard<std::mutex> lock(latch_);

    if(frame_id>static_cast<frame_id_t>(replacer_size_))
    {
        throw std::exception();
    }
    current_timestamp_++;
    recorded_cnt_[frame_id]++;
    auto cnt = recorded_cnt_[frame_id];
    hist[frame_id].push_back(current_timestamp_);
    /**
     * 如果是新加入的记录
     */
    if(cnt==1)
    {
        if(curr_size_==max_size_)
        {
            frame_id_t frame;
            Evict(&frame);
        }
        evictable_[frame_id] = true;
        curr_size_++;
        new_frame_.push_front(frame_id);
        new_locate_[frame_id] = new_frame_.begin();
    }
    /**
     * 如果记录达到k次,则需要从新队列中加入到老队列中
     */
    if(cnt==k_)
    {
        new_frame_.erase(new_locate_[frame_id]);//从新队列中删除
        new_locate_.erase(frame_id);

        auto kth_time = hist[frame_id].front();//获取当前页面的倒数第k次出现的时间
        k_time new_cache(frame_id,kth_time);
        auto it = std::upper_bound(cache_frame_.begin(),cache_frame_.end(),new_cache,CmpTimestamp);//找到该插入的位置
        it = cache_frame_.insert(it,new_cache);
        cache_locate_[frame_id] = it;
        return;
    }
    /**
     * 如果记录在k次以上,需要将该frame放到指定的位置
     */
    if(cnt>k_)
    {
        hist[frame_id].erase(hist[frame_id].begin());
        cache_frame_.erase(cache_locate_[frame_id]);//去除原来的位置
        auto kth_time = hist[frame_id].front();//获取当前页面的倒数第k次出现的时间
        k_time new_cache(frame_id,kth_time);

        auto it = std::upper_bound(cache_frame_.begin(),cache_frame_.end(),new_cache, CmpTimestamp);//找到该插入的位置
        it = cache_frame_.insert(it,new_cache);
        cache_locate_[frame_id] = it;
        return;
    }
    /**
     * 如果cnt<k_,是不需要做更新动作的
     */
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable)

{
    std::lock_guard<std::mutex> lock(latch_);
    if(recorded_cnt_[frame_id]==0)
    {
        return ;
    }
    auto status = evictable_[frame_id];
    evictable_[frame_id] = set_evictable;
    if(status&&!set_evictable)
    {
        --max_size_;
        --curr_size_;
    }
    if(!status&&set_evictable)
    {
        ++max_size_;
        ++curr_size_;
    }
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
    std::lock_guard<std::mutex> lock(latch_);
    if (frame_id > static_cast<frame_id_t>(replacer_size_)) {
        throw std::exception();
    }
    auto cnt = recorded_cnt_[frame_id];
    if (cnt == 0)
    {
        return ;
    }
    if(!evictable_[frame_id])
    {
        throw std::exception();
    }
    if(cnt<k_)
    {
        new_frame_.erase(new_locate_[frame_id]);
        new_locate_.erase(frame_id);
        recorded_cnt_[frame_id] = 0;
        hist[frame_id].clear();
        curr_size_--;
    }
    else
    {
        cache_frame_.erase(cache_locate_[frame_id]);
        cache_locate_.erase(frame_id);
        recorded_cnt_[frame_id] = 0;
        hist[frame_id].clear();
        curr_size_--;
    }
}

auto LRUKReplacer::Size() -> size_t { return curr_size_; }
auto LRUKReplacer::CmpTimestamp(const LRUKReplacer:: k_time &f1,const LRUKReplacer:: k_time &f2) -> bool {
    return f1.second<f2.second;
}

测试

  • 通过GoogleTest进行测试,下面是我写的测试实例
TEST(LRUKReplacerTest, AntiO2)
{
 LRUKReplacer lru_replacer(3, 3);
 frame_id_t frame;
 ASSERT_EQ(lru_replacer.Size(),0);
 lru_replacer.RecordAccess(1);
 lru_replacer.RecordAccess(1);
 lru_replacer.RecordAccess(1);
 lru_replacer.RecordAccess(2);
 lru_replacer.RecordAccess(2);
 lru_replacer.RecordAccess(2);
 lru_replacer.RecordAccess(1);
 ASSERT_EQ(lru_replacer.Size(),2);
 lru_replacer.RecordAccess(3);
 lru_replacer.Evict(&frame);
 ASSERT_EQ(frame,3);
 lru_replacer.Evict(&frame);
 EXPECT_EQ(frame,1);

 lru_replacer.RecordAccess(1);
 lru_replacer.RecordAccess(3);
 lru_replacer.RecordAccess(1);
 lru_replacer.Evict(&frame);
 EXPECT_EQ(frame,1);
 lru_replacer.RecordAccess(3);
 lru_replacer.RecordAccess(3);
 lru_replacer.Evict(&frame);
 EXPECT_EQ(frame,2);
 lru_replacer.Evict(&frame);
 EXPECT_EQ(frame,3);
}
  • 测试结果
    缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

结语

  • LRU-K是对LRU算法的改进,规避了一些访问上实际的问题,同时带来的额外开销也是可以接受的,是一个值得学习的算法
  • 在实际应用中,还应当考虑关联访问时期造成的影响。

到了这里,关于缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

    关于LRU缓存 LRU - Lease Recently Used 最近使用 如果内存优先,只缓存最近使用的,删除 ‘沉睡’ 数据 核心 api: get set 分析 使用哈希表来实现, O(1) 必须是有序的,常用放在前面,沉睡放在后面, 即:有序,可排序 这样 {} 不符合要求;Map是可以排序的,按照设置顺序 不用 Map 如何

    2024年02月06日
    浏览(54)
  • 面试遇到算法题:实现LRU缓存

    请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 这是一道大厂面试高频出现的算法题,难度为⭐️⭐️⭐️,属于中等,老铁们来一起看看这个题该怎么解? 没有废话,翠花,上酸菜! 为了实现一个满足 LRU (最近最少使用)缓存约束的数据结构,我们需

    2024年04月25日
    浏览(41)
  • 如何用链表实现LRU缓存淘汰算法

    缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存 等等 大小有限,当缓存被用满时,哪些数据应该被清理掉,哪些数据又应该保留呢? 先进先出策略 FIFO 最少使用策略 LFU 最近最少使用策略

    2024年02月01日
    浏览(63)
  • cache教程1.LRU 缓存淘汰策略

    这一节实现LRU算法,要理解明白其使用的数据结构。 Cache的缓存全部存储在内存中,内存是有限的,因此不可能无限制地添加数据。当占用内存超过了给定的内存大小时候,就需要从缓存中移除一条或多条数据了。我们肯定希望尽可能移除“没用”的数据,那如何判定数据“

    2024年02月04日
    浏览(47)
  • 【golang项目-GeeCache】动手写分布式缓存 day1 - 实现LRU算法

    【go项目-geecache】动手写分布式缓存 - day1 - 实现LRU算法 【go项目-geecache】动手写分布式缓存 - day2 - 单机并发缓存 【go项目-geecache】动手写分布式缓存 - day3 - HTTP 服务端 【go项目-geecache】动手写分布式缓存 - day4 - 一致性哈希(hash) 【go项目-geecache】动手写分布式缓存 - day5 - 分布

    2023年04月20日
    浏览(39)
  • A-2 LRU-K(攀拓(PAT)- 程序设计(甲级)2023年春季考试仿真卷)

    A-2 LRU-K 分数 25 作者 陈越 单位 浙江大学 Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn\\\'t been used for the longest amount of time) when the cache is full and a new page is referenced which is not there in cache. LRU-K is a variant of the LRU algorithm, where K represents the number of recent uses

    2024年02月08日
    浏览(31)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(60)
  • [算法与数据结构]:LRU Cache 的原理与C++实现

    ​ LRU全称是Least Recently Used,即 最近最久未使用,是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。 ​ 那么什么是缓存(Cache)呢?缓存是一种提高数据读取性能的技术,可以有效解决存储器性能和容量的矛盾,是一种空间换时间的设计思想,比

    2024年01月20日
    浏览(46)
  • 初识Go语言25-数据结构与算法【堆、Trie树、用go中的list与map实现LRU算法、用go语言中的map和堆实现超时缓存】

      堆是一棵二叉树。大根堆即任意节点的值都大于等于其子节点。反之为小根堆。   用数组来表示堆,下标为 i 的结点的父结点下标为(i-1)/2,其左右子结点分别为 (2i + 1)、(2i + 2)。 构建堆   每当有元素调整下来时,要对以它为父节点的三角形区域进行调整。 插入元素

    2024年02月12日
    浏览(59)
  • Python算法题集_LRU 缓存

    本文为Python算法题集之一的代码示例 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果 key 存在于缓存中,则返回的值,否则返回 -1 。 void put(int

    2024年02月21日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包