数据结构:LRU Cache

这篇具有很好参考价值的文章主要介绍了数据结构:LRU Cache。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是LRU Cache

LRULeast Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 什么是Cache?狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。

数据结构:LRU Cache,C++,数据结构,知识总结,数据结构
Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容

LRU Cache的实现

实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)putget,那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)

数据结构:LRU Cache,C++,数据结构,知识总结,数据结构

LRU缓存

数据结构:LRU Cache,C++,数据结构,知识总结,数据结构

对于底层逻辑来说,哈希表是必不可少的其次要考虑的是如何找最后一次使用的节点,这里可以借助一个链表来实现
每当使用了一个数据的时候就把这个数据加到最前面,那么链表最后的节点就是最久没有使用的内容了
但是又面临的问题是如何精准的定位到需要更改的位置,因此又需要一个迭代器
因此对于哈希表来说,需要存储的内容多了一个这个元素在链表中的定位,因此哈希表中要存储三个内容
1、Key值 2、Value值 3、Key值在链表中的索引文章来源地址https://www.toymoban.com/news/detail-827826.html

class LRUCache 
{
public:
    LRUCache(int capacity) 
        :_capacity(capacity)
    {}
    
    int get(int key) 
    {
        // 对于要得到一个元素,在这个题中需要两步走
        // 1、找这个元素
        // 2、更换这个元素在链表中的位置
        auto it = _HashMap.find(key);
        if(it != _HashMap.end())
        {
            // 说明此时找到了,更新它在链表中的位置
            // 这里使用的是list中的一个splice函数
            // void splice (iterator position, list& x, iterator i);
			auto listit = it->second.second;
			pair<int, int> kv = *listit;
			_lt.splice(_lt.begin(), _lt, listit);
			return kv.second;
        }
        else
        {
            return -1;
        }
    }
    
    void put(int key, int value) 
    {
        // 对于put函数来说有两种场景
        // 1、替换
        // 2、新增
        auto it = _HashMap.find(key);
        if(it != _HashMap.end())
        {
            // 替换
			it->second.second->second = value;
            auto listit = it->second.second;
			_lt.splice(_lt.begin(), _lt, listit);
			return;
        }
        else
        {
            // 新增:有可能会超过缓存中的容量,此时需要清除缓存中最后一个使用的元素,再新增一个新的元素
            if(_lt.size() == _capacity)
            {
                _HashMap.erase(_lt.back().first);
                _lt.pop_back();
            }
            _lt.push_front(make_pair(key, value));
            _HashMap[key] = make_pair(value, _lt.begin());
        }
    }
private:
    // 对于底层逻辑来说,哈希表是必不可少的
    // 其次要考虑的是如何找最后一次使用的节点,这里可以借助一个链表来实现
    // 每当使用了一个数据的时候就把这个数据加到最前面,那么链表最后的节点就是最久没有使用的内容了
    // 但是又面临的问题是如何精准的定位到需要更改的位置,因此又需要一个迭代器
    // 因此对于哈希表来说,需要存储的内容多了一个这个元素在链表中的定位,因此哈希表中要存储三个内容
    // 1、Key值  2、Value值  3、Key值在链表中的索引
    // 因此设计的模式采用下面的设计模式
	unordered_map<int, pair<int, list<pair<int, int>>::iterator>> _HashMap;
	list<pair<int, int>> _lt;
    int _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

到了这里,关于数据结构:LRU Cache的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

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

    2024年02月06日
    浏览(53)
  • 【数据结构】LRU缓存的简单模拟实现(leetcode力扣146LRU缓存)

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。 Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。

    2024年02月03日
    浏览(42)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

    2024年01月24日
    浏览(43)
  • 【设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构】

    LRU是Least Recently Used的缩写,意为最近最少使用。它是一种缓存淘汰策略,用于在缓存满时确定要被替换的数据块。LRU算法认为,最近被访问的数据在将来被访问的概率更高,因此它会优先淘汰最近最少被使用的数据块,以给新的数据块腾出空间。 如图所示: 先来3个元素进入

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

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

    2024年02月12日
    浏览(57)
  • 146. LRU Cache最近最少使用 (LRU) 缓存 Least Recently Used (LRU) cache.

    Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. O

    2024年02月10日
    浏览(55)
  • 数据结构--基础知识

    数据结构是计算机科学中研究数据组织、存储和管理的方法和原则。它涉及存储和操作数据的方式,以便能够高效地使用和访问数据。 数组(Array):数组是一种线性数据结构,由相同类型的元素按顺序排列而成。数组具有固定长度,在内存中占据连续的位置。可以通过索引

    2024年02月14日
    浏览(40)
  • 数据结构理论知识

    遍历原始二维数组,得到有效数据的个数sum 根据sum可以创建稀疏数组 将二维数组有效数据存储到稀疏数组 先读取稀疏数组第一行,根据第一行的数据,创建原始的二维数组 接着再读取稀疏数组后面几行的数据,并赋给原始的二维数组即可 牢记int用throw new RuntimeException, voi

    2024年02月09日
    浏览(36)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(42)
  • LRU Cache

    LRU是Least Recently Used的缩写,意思是最近最少使用,它是 一种Cache替换算法 。 什么是Cache? 狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调

    2024年01月19日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包