当前位置： 首页 > article >正文

leetcode - LRU缓存

article 2024/11/27 12:34:37

什么是 LRU

LRU (最近最少使用算法),

最早是在操作系统中接触到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略.

LRU算法基于局部性原理, 即最近被访问的数据在未来被访问的概率更高, 因此应该保留最近被访问的数据.

最近最少使用的解释

LRU (最近最少使用算法), 中的 "最近" 不是其绝对值的修饰, 而是一个范围.
如: 你最近去了那些地方, 最近看了哪些书.
而不是: 离你最近的人是谁, 离你最近的座位是哪一个. 

了解了最近的意义, 那么串联起来就是: 最近使用的一堆数据中, 哪一个数据使用的是最少的

LRU原理

下面展示了 LRU 算法的基本原理.

可以看到, 在 LRU 算法中, 涉及到了对象的移动, 如果使用 数组 来作为缓存, 那么移动对象的效率很慢. 因为在这个算法中, 经常涉及到头插元素, 数组 的头插是O(n^2), 非常的慢.

所以推荐使用 双向链表 来实现.

146. LRU 缓存 - 力扣（LeetCode）

但是在题目中, 要求查找和插入的时间复杂度为O(1);
双向链表的插入删除时间复杂度为O(1), 但是查找的时间复杂度为O(n).

双向链表 + 哈希表

单使用双向链表, 查找的时间复杂度为O(n), 那么数据结构的查找操作的时间复杂度为O(1)?
答案很明显: 哈希表

 定义链表节点 ListNode

struct ListNode
{
public:
    ListNode()
    {}
    ListNode(int k, int v)
    :key(k),
    value(v)
    {}

    ~ListNode()
    {}
    int key;
    int value;
    // 节点中不仅存储 value, 还存储 key, 这在后面的 put 函数中有用
    ListNode* next;
    ListNode* prev;
};

LRUcache 成员属性

class LRUCache {
public:
    int _size = 0; // 记录缓存中已经缓存了多少数据
    int _capacity = 0; // 记录缓存大小 (可缓存的数据个数)
    ListNode* head = nullptr; // 双向链表的头节点
    ListNode* tail = nullptr; // 双向链表的尾节点
    unordered_map<int, ListNode*> table;
    // 底层是通过 hashtable 实现的map, 用来通过 kev 查找节点
}

LRUcache 成员方法

构造 / get / put 函数

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity; // 记录缓存的大小
        // 初始化链表的 头节点 和 尾节点
        head = new ListNode;
        tail = new ListNode;
        // 将头尾节点连接起来
        head->next = tail;
        head->prev = tail;
        tail->next = head;
        tail->prev = head;

    }
    // 通过 key 获取对应的 value. 如果 key 不存在, 则返回 -1
    int get(int key) {
        auto it = table.find(key); // 通过 hashtable 查找 key 是否存在
        if(it == table.end())
        {
            return -1; // 不存在对应的 [key, value], 返回 -1
        }
        // 存在 key, 记录value, 然后更新这个节点, 将这个节点移动到链表头部
        int ret = it->second->value;
        MoveToHead(it->second); // 将这个节点移动到头部
        return ret;
    }
    // 插入一对键值对 [key, value]
    void put(int key, int value) {
        auto it = table.find(key); // 在 hashtable 中查找是否已经存在 key
        if(it != table.end()) // 已经存在 key 则更新节点的值, 并且将这个节点移动到链表头部
        {
            // 更新节点
            it->second->value = value;
            MoveToHead(it->second); // 将节点移动到链表头部
            return; // 直接返回, 下面是进行插入的操作
        }
        
        // key 不存在, 判断 空间是否已满, 满了就需要删除 链表末尾的节点
        if(_size == _capacity)
        {
            // ListNode 中记录的 key 就起作用了, 如果只有 value, 那么就还需要遍历 table
            int back = tail->prev->key;
            table.erase(back); // 删除 hashtable 中这个节点的记录
            pop_back(); // 删除尾部节点
            --_size;
        }
        // 链表末尾的节点已被删除, 现在需要向 链表头部 插入 新的节点
        ListNode* node = push_front(key, value);
        table[key] = node; // 在 hashtable 中记录这个新的节点
        ++_size;
    }
};

MoveToHead / push_front / pop_back 函数

class LRUCache {
public:
    // 将 node 移动到链表头部
    void MoveToHead(ListNode* node)
    {
        if(node == head->next) // 如果这个节点就是头部, 那么就不移动
        {
            return;
        }
        ListNode* node_next = node->next; // 记录 node 节点的后一个节点
        ListNode* node_prev = node->prev; // 记录 node 节点的前一个节点
        node_prev->next = node_next; // 将 node 的前后节点连接起来
        node_next->prev = node_prev;
        // 将 node 节点链接到链表首部
        node->prev = head; 
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    // 头插
    ListNode* push_front(int key, int value)
    {
        ListNode* node = new ListNode(key, value);
        ListNode* next = head->next;
        head->next = node;
        node->prev = head;
        next->prev = node;
        node->next = next;
        return node;
    }
    // 尾删
    void pop_back()
    {
        ListNode* prev = tail->prev->prev;
        ListNode* cur = tail->prev;
        prev->next = tail;
        tail->prev = prev;
        delete cur;
    }
};

 

 

完整代码

class LRUCache {
public:
    struct ListNode
    {
    public:
        ListNode()
        {}
        ListNode(int k, int v)
        :key(k),
        value(v)
        {}

        ~ListNode()
        {}
        int key;
        int value;
        ListNode* next;
        ListNode* prev;
    };

    int _size = 0;
    int _capacity = 0;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    unordered_map<int, ListNode*> table;

    LRUCache(int capacity) {
        _capacity = capacity;
        head = new ListNode;
        tail = new ListNode;
        head->next = tail;
        head->prev = tail;
        tail->next = head;
        tail->prev = head;

    }
    
    int get(int key) {
        auto it = table.find(key);
        if(it == table.end())
        {
            return -1;
        }
        int ret = it->second->value;
        MoveToHead(it->second); // 将这个节点移动到头部
        return ret;
    }
    
    void put(int key, int value) {
        auto it = table.find(key);
        if(it != table.end())
        {
            // 更新节点
            it->second->value = value;
            MoveToHead(it->second);
            return;
        }

        if(_size == _capacity)
        {
            int back = tail->prev->key;
            table.erase(back); // 删除 hashtable 中的键值对
            pop_back(); // 删除尾部节点
            --_size;
        }

        ListNode* node = push_front(key, value);
        table[key] = node;
        ++_size;
    }

    void MoveToHead(ListNode* node)
    {
        if(node == head->next)
        {
            return;
        }
        ListNode* node_next = node->next;
        ListNode* node_prev = node->prev;
        node_prev->next = node_next;
        node_next->prev = node_prev;
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    ListNode* push_front(int key, int value)
    {
        ListNode* node = new ListNode(key, value);
        ListNode* next = head->next;
        head->next = node;
        node->prev = head;
        next->prev = node;
        node->next = next;
        return node;
    }

    void pop_back()
    {
        ListNode* prev = tail->prev->prev;
        ListNode* cur = tail->prev;
        prev->next = tail;
        tail->prev = prev;
        delete cur;
    }

};


http://www.kler.cn/a/411352.html

相关文章：

  • AIGC-----AIGC在虚拟现实中的应用前景
  • QT 跨平台实现 SSDP通信 支持多网卡
  • Delphi ADO组件中的 ADOTable、ADOQurey 无SQL语句实现增、删、改、查
  • STM32F103外部中断配置
  • 利用开源图床的技巧与实践
  • cocos creator 3.8 物理碰撞器Collider+刚体RigidBody 8
  • Python数据分析实例五、US 大选捐款数据分析
  • 【数据分析】基于GEE解析2000-2020年武汉市FVC时空变化特征
  • Jenkins-Ansible 插件相关用法
  • ReentrantLock(可重入锁) Semaphore(信号量) CountDownLatch
  • Windows下安装FreeSurfer教程
  • Linux进程信号保存/操作系统运行原理
  • 【第三讲】Spring Boot 3.4.0 新特性详解：增强的配置属性支持
  • 无人机：智能航点规划技术！
  • jQuery-Json-AJAX-跨域
  • 【前端】javaScript
  • Excel与PPT：职场两大软件的应用比拼
  • 调用 AWS Lambda 时如何传送字节数组
  • 关于IDE的相关知识之三【插件安装、配置及推荐的意义】
  • Python语法基础（一）
  • 【C++】C++的nullptr和NULL
  • vue的理解
  • 鸿蒙学习自由流转与分布式运行环境-价值与架构定义(1)
  • 【C++】顺序容器（二）：顺序容器操作
  • C++11新特性探索：Lambda表达式与函数包装器的实用指南
  • 极狐GitLab 17.6 正式发布几十项与 DevSecOps 相关的功能【四】