`

146 LRU Cache——leetcode

lruleetcode双向链表hash表 
阅读更多
146 LRU Cache

这个基于双向链表+Map表

  • 第一步：分析LRU特点

2大特点：

  1. 保持顺序，即访问顺序FIFO。保持顺序的只有顺序类型如链表、数组
  2. 快速查找，给定的KEY，能够快速查找的有：二叉搜索树、Hash表、跳表SkipList

再细化各特点

 

《1》链表特点是：插入、删除、移动都是O(1)操作，随机访问O(N)

《2》数组特点是：插入、删除、移动都是O(N)，只有当都是头、尾元素时，才是O(1)。 随机访问O(1)。

而Cache不需要随机访问第K个元素，而需要频繁的移动、删除。因此，需要用链表。为了便于插入，使用双双向链表，又为了实际代码中便于书写各函数，改成带头结点的双向循环链表，这样的好处是不用考虑在队头、队尾。插入，删除等特殊情况。

 

快速查找，方便使用，因此选用标准的map表，也可以使用hash表，甚至自行设计的hash表，而且，性能应该更好些。

 

  • 第二步：实际设计

带头节点的循环双向链表，为自行设计，和标准的list操作很多一样。可作为基本素材。

 

在实际设计过程中，有些小细节，可用于提高性能。

《1》改用链表的删除为断开连接，这样减少 new 和delete操作

《2》这主要是用于重复访问上一次的（这个在实际的cache中会经常遇到，即刚刚访问的，下次继续访问，但在leetcode中，加入该句，性能反而更低）

          if(cachePriority.begin()!=p)           
          {
                cachePriority.clean_link(p);
                cachePriority.link_after(cachePriority.get_head(),p);
            }

 

 

#pragma  once
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <vector>
using namespace std;

template<typename T>
struct dlist_node{
    dlist_node*prev;
    dlist_node*next;
    T data;
};
template <typename T>
struct dlinkedlist{
    dlist_node<T>*head;
public:
    dlinkedlist():head(NULL){
        head=new dlist_node<T>;
        head->prev=head->next=head;
    }
    ~dlinkedlist(){
        dlist_node<T>*next=NULL;
        for(dlist_node<T>*p=head->next;p!=head;p = next){
            next=p->next;
            delete p;
        }
        delete head;
    }
public:
    dlist_node<T>* advance(int n){
        return (n>0)?shiftRight(n):shiftLeft(-n);
    }
    void pop_back(){
        dlist_node<T>* tail = head->prev;
        erase(tail);
    }

    T& back(){
        return head->prev->data;
    }
    //删除p后，返回p的前驱
    dlist_node<T>* erase(dlist_node<T>* p){
        dlist_node<T>* pPrev = p->prev;
        p->prev->next=p->next;
        p->next->prev=p->prev;
        delete p;
        return pPrev;
    }
    //只断开链接，返回p的前驱，不同于erase
    dlist_node<T>* clean_link(dlist_node<T>* p){
        dlist_node<T>* pPrev = p->prev;
        p->prev->next=p->next;
        p->next->prev=p->prev;
        return pPrev;
    }

    void push_front(const T &data){
        dlist_node<T> *pNew = new dlist_node<T>;
        pNew->data = data;

        head->next->prev=pNew;
        pNew->prev=head;

        pNew->next=head->next;
        head->next=pNew;
    }
    //因为带头结点，等价于end()方法
    dlist_node<T>* get_head(){
        return head;
    }
    dlist_node<T>* begin(){
        return head->next;
    }
    dlist_node<T>* end(){
        return head;
    }
    void link_after(dlist_node<T>*pPrev,dlist_node<T>* p){
        p->next = pPrev->next;
        p->prev = pPrev;
        pPrev->next->prev=p;
        pPrev->next=p;
    }
private:
    dlist_node<T>* shiftLeft(unsigned int n){
        dlist_node<T>*prev = head;
        for(;n--;prev=prev->prev);
        head = prev;
        return prev->next;
    }
    dlist_node<T>* shiftRight(unsigned int n){
        dlist_node<T>*prev = head;
        for(;n--;prev=prev->next);
        head = prev;
        return prev->next;
    }
    
};

class LRUCache{
    typedef dlist_node<int> DNODE;
public:
    static void test(){
        {
            dlinkedlist<int> l;
            l.push_front(1);
            l.push_front(2);
            l.push_front(3);
            l.pop_back();
            l.pop_back();
            l.pop_back();
        }
        {
            LRUCache lru(1);
            lru.set(2,1);
            if(lru.get(2)!=1){
                printf("error\n");
            }
            lru.set(3,2);
            if(lru.get(2)!=-1){
                printf("error\n");
            }
            if(lru.get(3)!=2){
                printf("error\n");
            }
        }
        {
            LRUCache lru(50);
            srand(109);
            for(int i=0;i<1000;i++)
            {
                lru.set(rand()%100,i);
            }
            for(int i=0;i<10000;i++){
                if(rand()%2){
                    lru.get(rand()%100);
                }
                else{
                    lru.set(rand()%100,i);
                }
            }
        }

    }
public:
    LRUCache(int capacity)
    {
        cap=capacity;
    }
    ~LRUCache(){

    }
    int get(int key) {
        map<int,pair<DNODE*,int> >::iterator it = cacheMap.find(key);
        if(it!=cacheMap.end())
        {
            //swap,将最近访问的移动到最前面
            DNODE*p= it->second.first;
            if(cachePriority.begin()!=p)
            {
                cachePriority.clean_link(p);
                cachePriority.link_after(cachePriority.get_head(),p);
            }
            return (it->second).second;
        }
        return -1;
    }

    void set(int key, int val) {
        map<int,pair<DNODE*,int> >::iterator it= cacheMap.find(key);
        if(it==cacheMap.end())
        {
            //如果不存在，需要加入到cache中
            //这里有个小技巧，如果队列满了，而且是不断增加新元素，那么只需要循环左移1位
            if(cacheMap.size()>=cap)
            {
                int replaceKey = cachePriority.back();
                cacheMap.erase(replaceKey);
                //循环←1位
                DNODE* pHead = cachePriority.advance(-1);
                pHead->data = key;
            }
            else
            {
                cachePriority.push_front(key);
            }
            pair<DNODE*,int> posval =  pair<DNODE*,int> (cachePriority.begin(),val);
            cacheMap.insert(pair<int,pair<DNODE*,int> >(key,posval));
        }
        else
        {
            //already exist
            DNODE *p = it->second.first;
            cachePriority.clean_link(p);
            cachePriority.link_after(cachePriority.get_head(),p);
            it->second.second= val;
            
        }
    }
    map<int,pair<DNODE*,int> > cacheMap;
    dlinkedlist<int> cachePriority;
    int cap;
};

 

  •  更新在leetcode中更快的实现（设计不变）

在贴一个，设计原理没有变。但仅适用于leetcode的。accept为80ms

（1）用unordered_map代替红黑树的map，如果结合特点，自行设计的hash表应该更快。

（2）去掉 模板，将模板类的双向链表改成普通的。

实际性能提高20%。

 

 

#pragma  once
#include <map>
using namespace std;


struct dlist_node{
    dlist_node*prev;
    dlist_node*next;
    int data;
};

struct dlinkedlist{
    dlist_node *head;
public:
    dlinkedlist():head(NULL){
        head=new dlist_node;
        head->prev=head->next=head;
    }
    ~dlinkedlist(){
        dlist_node *next=NULL;
        for(dlist_node *p=head->next;p!=head;p = next){
            next=p->next;
            delete p;
        }
        delete head;
    }
public:
    dlist_node* advance(int n){
        return (n>0)?shiftRight(n):shiftLeft(-n);
    }
    void pop_back(){
        dlist_node* tail = head->prev;
        erase(tail);
    }

    int& back(){
        return head->prev->data;
    }
    //删除p后，返回p的前驱
    dlist_node* erase(dlist_node* p){
        dlist_node* pPrev = p->prev;
        p->prev->next=p->next;
        p->next->prev=p->prev;
        delete p;
        return pPrev;
    }
    //只断开链接，返回p的前驱，不同于erase
    dlist_node* clean_link(dlist_node* p){
        dlist_node* pPrev = p->prev;
        p->prev->next=p->next;
        p->next->prev=p->prev;
        return pPrev;
    }

    void push_front(const int &data){
        dlist_node *pNew = new dlist_node;
        pNew->data = data;

        head->next->prev=pNew;
        pNew->prev=head;

        pNew->next=head->next;
        head->next=pNew;
    }
    //因为带头结点，等价于end()方法
    dlist_node* get_head(){
        return head;
    }
    dlist_node* begin(){
        return head->next;
    }
    dlist_node* end(){
        return head;
    }
    void link_after(dlist_node*pPrev,dlist_node* p){
        p->next = pPrev->next;
        p->prev = pPrev;
        pPrev->next->prev=p;
        pPrev->next=p;
    }
private:
    dlist_node* shiftLeft(unsigned int n){
        dlist_node*prev = head;
        for(;n--;prev=prev->prev);
        head = prev;
        return prev->next;
    }
    dlist_node* shiftRight(unsigned int n){
        dlist_node*prev = head;
        for(;n--;prev=prev->next);
        head = prev;
        return prev->next;
    }
    
};

class LRUCache{
    typedef dlist_node DNODE;
    typedef unordered_map<int,pair<DNODE*,int> > MAP;
public:
    LRUCache(int capacity)
    {
        cap=capacity;
    }
    ~LRUCache(){

    }
    int get(int key) {
        MAP::iterator it = cacheMap.find(key);
        if(it!=cacheMap.end())
        {
            //swap,将最近访问的移动到最前面,判断是否是头结点，如果是，不需要操作
            DNODE*p= it->second.first;
            //if(cachePriority.begin()!=p)
            {
                cachePriority.clean_link(p);
                cachePriority.link_after(cachePriority.get_head(),p);
            }
            return (it->second).second;
        }
        return -1;
    }

    void set(int key, int val) {
       MAP::iterator it= cacheMap.find(key);
        if(it==cacheMap.end())
        {
            //如果不存在，需要加入到cache中
            //这里有个小技巧，如果队列满了，而且是不断增加新元素，那么只需要循环左移1位
            if(cacheMap.size()>=cap)
            {
                int replaceKey = cachePriority.back();
                cacheMap.erase(replaceKey);
                //循环←1位
                DNODE* pHead = cachePriority.advance(-1);
                pHead->data = key;
            }
            else
            {
                cachePriority.push_front(key);
            }
            pair<DNODE*,int> posval =  pair<DNODE*,int> (cachePriority.begin(),val);
            cacheMap.insert(pair<int,pair<DNODE*,int> >(key,posval));
        }
        else
        {
            //already exist
             //swap,将最近访问的移动到最前面,判断是否是头结点，如果是，不需要操作
            DNODE *p = it->second.first;
            //if(p!=cachePriority.begin())
            {
                cachePriority.clean_link(p);
                cachePriority.link_after(cachePriority.get_head(),p);
            }
            it->second.second= val;
            
        }
    }
    MAP cacheMap;
    dlinkedlist cachePriority;
    int cap;
};
分享到：
| 56 Merge Intervals——leetcode
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    最近最少使用cache，提取leveldb的lru cache部分，增加过期时间，过期失效

    它使用LRU Cache作为其内部的数据缓冲机制，以加速对数据的读取。在原始的LevelDB实现中，LRU Cache主要关注数据的访问频率，而不涉及数据的过期策略。 在这个项目中，开发者将LevelDB的LRU Cache部分提取出来，...

    创新Cache ——内存页面置换算法 LRU_FIFO

    操作系统中的Cache与内存间的置换算法有LRU，FIFO等经典算法，作者首先程序实现了此2种算法，并在此2者的基础上创新出一个新的置换算法LRU_FIFO算法，获得高校教师很高评价，该算法结合LRU与FIFO的特点，也可单独...

    LRU Cache的简单C++实现

    　LRU Cache是一个Cache的置换算法，含义是“近少使用”，把满足“近少使用”的数据从Cache中剔除出去，并且保证Cache中第一个数据是近刚刚访问的，因为这样的数据更有可能被接下来的程序所访问。 　LRU的应用比较...

    backports.functools_lru_cache-1.5.tar

    python源码安装包backports.functools_lru_cache-1.5.tar 解压后python setup.py install 进行安装

    ARM高速缓存(Cache)Verilog代码 包含ISE工程

    Cache替换策略: LRU I_Cache的工作就是在cpu需要指令时将指令从主存中搬进I_Cache，再传给CPU，而D_Cache在解决数据读外，还要注意数据写入的问题。本工程可以与arm.v 中的arm 核协同工作，主存使用dram_ctrl_sim。

    FIFO&LRU——先进先出 最久未使用 页面置换算法

    本代码通过了老师的检查，测试平台是：vc++6.0,并提交了实验报告，如果您有什么建议，请告诉我，一起进步。

    LRU更新Cache

    LRU（Least Recently Used）缓存更新策略是一种广泛应用于计算机系统中的内存管理技术，尤其是在操作系统、数据库系统和编程语言的缓存实现中。LRU的基本思想是：当内存空间有限时，最近最少使用的数据应该优先被...

    glide_disklrucache

    其中，`glide_disklrucache` 提到的是Glide库在磁盘缓存方面所采用的一种机制——Disk LRU Cache，它是Android开发中的一个关键知识点。 Disk LRU Cache是一种基于Least Recently Used（LRU，最近最少使用）算法的...

    Python实现的一个简单LRU cache

    LRU (Least Recently Used) 缓存是一种常用的内存管理策略，用于在有限的存储空间内高效地存储数据。当缓存满时，最近最少使用的数据将被移除以腾出空间给新数据。这里我们将讨论如何使用Python实现一个简单的LRU...

    让你Python到很爽的加速递归函数的装饰器

    @functools.lru_cache——进行函数执行结果备忘，显著提升递归函数执行时间。 示例：寻找宝藏。在一个嵌套元组tuple或列表list中寻找元素’Gold Coin’ import time from functools import lru_cache def find_...

    资源异步加载和缓存

    3. **LRU Cache（Least Recently Used Cache）**：LRU Cache是一种常用的内存缓存策略，当缓存满时，会优先淘汰最近最少使用的数据。在Android中，LRU Cache常用于图片缓存，可以有效减少网络请求，提高用户体验。...

    高速缓存(Cache)的Verilog代码

    Cache替换策略: LRU I_Cache的工作就是在cpu需要指令时将指令从主存中搬进I_Cache，再传给CPU，而D_Cache在解决数据读外，还要注意数据写入的问题。本工程可以与arm.v 中的arm 核协同工作，主存使用dram_ctrl_sim。

    前端开源库-lrucache

    在前端开发中，LRU Cache库可以帮助我们高效地管理和存储有限数量的数据，尤其在处理大量数据或者频繁访问相同数据的情况下，能显著提升性能。 `lrucache`是一个针对Node.js和浏览器环境的开源库，它实现了LRU缓存...

    cache性能分析实验报告.docx

    5. 比较和分析LRU和随机替换算法对Cache性能的影响。 实验步骤涉及： 1. 使用SimpleScalar模拟器运行基础配置的程序，统计总失效次数和不同类型的失效次数。 2. 修改Cache容量，观察失效次数的变化，分析容量与性能...

    东南大学操作系统实验——实现LRU算法及其近似算法

    实验的主要数据结构是一个模板类`lru_cache`，它基于关联容器`std::unordered_map`和双向链表`std::list`实现。`unordered_map`用于快速查找页面，而`list`则保持页面的访问顺序。`put()`方法用于插入或更新页面，`...

    Verilog-caches:用 Verilog-HDL 编写的各种缓存

    4way_4word 缓存4路组相联高速缓存行大小为 4 个字缓存替换策略是 LRU 8way_4word 缓存8路组相联高速缓存行大小为 4 个字缓存替换策略为 Pseudo-LRU free_config_cache 默认缓存配置为 8 路组关联您可以通过发送 ...

    logisim及全相联cache设计.rar

    全相联Cache（ Fully-Associative Cache）是Cache组织方式的一种，与直接映射Cache和组相联Cache不同，它的每一个块都可以映射到Cache的任何一个位置上，这提供了更大的灵活性，但也带来了更高的复杂性。 全相联...

    头歌计算机组成原理2路组相联cache设计

    4. 淘汰算法：2路组相联Cache通常使用LRU（最近最少使用）算法来决定替换哪个块。LRU基于历史使用频率，认为最近最不常用的数据未来被访问的可能性最小，因此优先淘汰这类数据。 工作流程： 1. CPU发出内存访问请求...

    多 Cache 一致性实验介绍.docx

    实验配置阶段，需要设定多个参数，包括但不限于Cache的大小、Cache块的大小、映射方式（如直接映射、全相联映射、组相联映射）、替换策略（如LRU、LFU、随机替换等）以及内存一致性协议（如MSI、MESI、MOESI等）。...

    cache性能分析实验

    ### Cache性能分析实验知识点 #### 实验背景与目标 本实验旨在通过使用SimpleScalar模拟器对Cache性能进行深入分析，以此来加深对Cache基础知识、结构及其工作原理的理解。此外，还将探讨并量化Cache的主要参数...

Magicbox
Global site tag (gtag.js) - Google Analytics