高阶数据结构-LRU Cache

简介: LRU Cache

什么是LRU Cache

LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法

什么是Cache

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


Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容.LRU Cache 的替换原则就是将最近最少使用的内容替换掉

其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容


LRU Cache的实现

实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和哈希表的搭配是最高效和经典的

使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)


LRU缓存OJ:

https://leetcode.cn/problems/lru-cache/


结构设计分析

实现结构1:

private:

   unordered_map<int,int>_hashMap; //hash能做到查找get更新是O(1)

   

   list<pair<int,int>>_LRUList;//假设尾部数据就是最近少用的,最近使用的放在头部

   size_t_capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对

此时:

intget(intkey) {}

voidput(intkey, intvalue) {}

get: 直接查map,时间复杂度是O(1)

put: 如果是新增元素就是O(1),直接插入,  但是如果是修改更新: 就是O(N), 因为要在map查找完成后,在_LRUList中找到该元素key所在位置 ,只能遍历查找,时间复杂度是O(N)  ,然后把该元素key放在头部O(1)


破局点:找到key之后,就要找到key对应存储的数据在链表中的位置

所以: hashMap中可以存list的迭代器!   我们实现过list,所以知道list的迭代器本质是节点的指针

typedeflist<pair<int,int>>::iteratorLtIter;

private:

   unordered_map<int,LtIter>_hashMap; //key:值  Value:list的迭代器,即key对应在list的位置

   list<pair<int,int>>_LRUList;

   size_t_capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对

这个结构,相当于真正的数据在list里面!在map中查找key,就可以直接在链表中找到这个节点, 然后把这个节点转移到链表头部


list的splice函数介绍:

splice函数用于两个list容器之间的拼接(数据转移),其有三种拼接方式:

  1. 将整个容器拼接到另一个容器的指定迭代器位置.
  2. 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置.
  3. 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置.

#include <iostream>

#include <list>

usingnamespacestd;

intmain()

{

   list<int>lt1(4, 2);

   list<int>lt2(4, 6);

   lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头

   for (autoe : lt1)

   {

       cout<<e<<" ";

   }

   cout<<endl; //6 6 6 6 2 2 2 2

   list<int>lt3(4, 2);

   list<int>lt4(4, 6);

   lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头

   for (autoe : lt3)

   {

       cout<<e<<" ";

   }

   cout<<endl; //6 2 2 2 2

   list<int>lt5(4, 2);

   list<int>lt6(4, 6);

   lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头

   for (autoe : lt5)

   {

       cout<<e<<" ";

   }

   cout<<endl; //6 6 6 6 2 2 2 2

   return0;

}

注意: 容器当中被拼接到另一个容器的数据在原容器当中就不存在了.(实际上就是将链表当中的指定结点拼接到了另一个容器当中)

当然也可以把节点转移到自己身上

例如:

#include<list>

intmain()

{

   list<int>lt{ 1,2,3,4,5 };

   lt.splice(lt.begin(), lt, --lt.end());//把尾部的数据放到头部

   for (autoe : lt)

   {

       cout<<e<<" "; // 5 1 2  3  4

   }

   return0;

}


我们待会要用这个函数来把节点转移到链表的头部!

get函数的实现:

1)在map中查找key是否存在 .如果不存在,返回-1

2)如果存在,把该key放到list的头部 -> 转移节点  ,然后返回key对应的值

元素存在list里面, _hashMap中的键:key 值:list的迭代器(LtIter),


如果key对应的值存在,则取出迭代器, 这里就可以看出hashmap的value存的是list的iterator的好处:找到key  也就找到key存的值在list中的iterator,也就直接删除,再进行头插,实现O(1)的数据挪动

intget(intkey)

{

   //_hashMap中的key:key value:list的迭代器(LtIter)

   autoret=_hashMap.find(key);//先查找是否在哈希表中

   if(ret!=_hashMap.end())

   {

       //更新当前元素到链表头部

       LtIterit=ret->second;//该元素在list中的位置

       _LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部,相当于头插,但是这这里不用更新迭代器,因为迭代器里面存的还是这个节点的指针

       

       //it:是链表的迭代器,调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*

       //pair<int,int>  我们要的是第二个成员的值  

       //本来应该是it->->second 但是省略了一个箭头

       returnit->second;//返回key对应的value

   }

   else    //该元素不存在

   {

       return-1;

   }

}


put函数的实现:

1)在map中查找key是否存在 .如果不存在,那就要新增

  • 1.判断是否满了,如果满了,需要先删除list中尾部的数据. 然后在哈希表中也要删除该元素
    2.然后把该该 {key-value}头插到链表中 , 在哈希表中新增键值对{key-该位置在链表的迭代器}

注意点:判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)

2)如果已经存在了,那就修改数据,  然后把该key放到list的头部

voidput(intkey, intvalue)

{

   autoret=_hashMap.find(key);

   //新增

   if(ret==_hashMap.end())

   {

       //判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)

       //if(_capacity == _LRUList.size()) 不建议

       if(_capacity==_hashMap.size()) //容量满了

       {

           pair<int,int>back=_LRUList.back();//取出链表尾部的数据

           //在哈希表中删除该数据 + 在链表弹出该元素

           _hashMap.erase(back.first);//back.first是key

           _LRUList.pop_back();

       }

       //头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}

       _LRUList.push_front(make_pair(key,value));

       _hashMap[key] =_LRUList.begin();

   }

   else

   {

       //修改节点的值 + 当前数据放到链表头部

       LtIterit=ret->second;//it是list的迭代器

       it->second=value;//更新节点的值

       _LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部

   }

}

整体代码:

classLRUCache {

public:

   typedeflist<pair<int,int>>::iteratorLtIter; //list的迭代器重命名为LtIter

   LRUCache(intcapacity) {

       _capacity=capacity;

   }

   

   intget(intkey) {

       //_hashMap中的key:key value:list的迭代器(LtIter)

       autoret=_hashMap.find(key);//先查找是否在哈希表中

       if(ret!=_hashMap.end())

       {

           //更新当前元素到链表头部

           LtIterit=ret->second;//该元素在list中的位置

           _LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部

           

           //it:是链表的迭代器,it-> 调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*

           //pair<int,int>  我们要的是第二个成员的值  

           //本来应该是it->->second 但是省略了一个箭头

           returnit->second;//返回key对应的value

       }

       else    //该元素不存在

       {

           return-1;

       }

   }

   

   voidput(intkey, intvalue)

   {

       autoret=_hashMap.find(key);

       //新增

       if(ret==_hashMap.end())

       {

           //判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)

           //if(_capacity == _LRUList.size()) 不建议

           if(_capacity==_hashMap.size()) //容量满了

           {

               pair<int,int>back=_LRUList.back();//取出链表尾部的数据

               //在哈希表中删除该数据 + 在链表弹出该元素

               _hashMap.erase(back.first);//back.first是key

               _LRUList.pop_back();

           }

           //头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}

           _LRUList.push_front(make_pair(key,value));

           _hashMap[key] =_LRUList.begin();

       }

       else

       {

           //修改节点的值 + 当前数据放到链表头部

           LtIterit=ret->second;//it是list的迭代器

           it->second=value;//更新节点的值

           _LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部

       }

   }

private:

   unordered_map<int,LtIter>_hashMap; //key:值  Value:list的迭代器,即key对应在list的位置

   list<pair<int,int>>_LRUList;

   size_t_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);

*/


其实这里有两种更新常用元素的方式:

1.用内置的splice函数转移节点

2.先保存节点信息,然后erase节点,然后push_front.  然后更新key对应的迭代器, 因为原迭代器指向我们删除的数据,迭代器失效了!!

使用unordered_map,让搜索效率达到O(1) 需要注意:这里最巧的设计就是将unordered_map的value type放成list<pair<int,int>>::iterator,因为这样,当get一个已有的值以后,就可以直接找到key在list中对应的iterator,然后将这个值移动到链表的头部保持LRU

int get(int key)

{

   // 如果key对应的值存在,就可以取出元素位置迭代器,这里就可以看出hashmap的value存的是list的 terator的好处:找到key

       // 也就找到key存的值在list中的iterator,也就直接删除,再进行头插,实现O(1)的数据挪动

    auto hashit = _hashmap.find(key);

   if(hashit != _hashmap.end())

   {

       auto listit = hashit->second;//list的迭代器

       pair<int, int> kv = *listit; //调用operator* 返回节点数据的内容,list的数据是pair


       _list.erase(listit);//通过迭代器删除该节点

       _list.push_front(kv);//然后头插

       _hashmap[key] = _list.begin();//更新迭代器的位置

       return kv.second;//返回key对应的value

   }

   else

   {

       return -1;

   }

}


void put(int key, int value)

{

   // 1.如果没有数据则进行插入数据

   // 2.如果有数据则进行数据更新

   auto hashit = _hashmap.find(key);

   if(hashit == _hashmap.end())

   {

       // 插入数据时,如果数据已经达到上限,则删除链表头的数据和hashmap中的数据,两个删除操作都是O(1)

           if(_list.size() >= _capacity)

           {

               _hashmap.erase(_list.back().first); //在哈希表中删除最后一个节点的信息,通过key删除. _list.back().first:最后一个节点的第一个成员就是key

               _list.pop_back();//尾删最后一个节点

           }


       _list.push_front(make_pair(key,value));//头插

       _hashmap[key] = _list.begin();//新建键值对

   }

   else

   {

       // 更新数据  将数据挪动list前面

       auto listit = hashit->second;//list的迭代器

       pair<int, int> kv = *listit;//调用operator* 返回节点数据的内容,list的数据是pair,先保留数据

       kv.second = value;//更新值


       _list.erase(listit);//通过迭代器删除该节点

       _list.push_front(kv);//头插

       _hashmap[key] = _list.begin();//更新迭代器的位置

   }

}


相关文章
|
7天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
14 0
|
11天前
|
存储 Linux 数据库
【数据结构】二叉搜索树——高阶数据结构的敲门砖
【数据结构】二叉搜索树——高阶数据结构的敲门砖
|
2月前
|
存储 NoSQL 算法
【高阶数据结构】跳表 -- 详解
【高阶数据结构】跳表 -- 详解
|
2月前
|
存储 算法 关系型数据库
【高阶数据结构】 B树 -- 详解
【高阶数据结构】 B树 -- 详解
|
2月前
|
缓存 算法 内存技术
【高阶数据结构】LRU Cache -- 详解
【高阶数据结构】LRU Cache -- 详解
|
2月前
|
算法
【高阶数据结构】图 -- 详解(下)
【高阶数据结构】图 -- 详解(下)
|
2月前
|
存储
【高阶数据结构】图 -- 详解(上)
【高阶数据结构】图 -- 详解(上)
|
2月前
|
存储
【高阶数据结构】并查集 -- 详解
【高阶数据结构】并查集 -- 详解
|
12月前
|
存储 缓存 算法
【数据结构】——LRU Cache
LRU缓存的原理及实现
|
12月前
|
存储 人工智能 算法
【高阶数据结构】B树
B树、B+树和B*树的原理及其功能。