admin管理员组文章数量:1031255
【数据结构与算法】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) 的查找。
这分别对应到 stl 中的 list 和 unordered_map ，其中要注意的是，为了能达到 O(1) 的效果，我们在 unordered_map 中存放的 value 值是 list 的迭代器 list<int, int>::iterator ，这样子就能快速找到链表中每个节点。
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：
-
LRUCache(int capacity)以 正整数 作为容量capacity初始化LRU缓存 -
int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。 -
void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。 - 函数
get和put必须以O(1)的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示： 1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105
代码实现：
代码语言：javascript代码运行次数：0运行复制class LRUCache {
public:
LRUCache(int capacity)
:_capacity(capacity)
{}
int get(int key)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
return -1;
}
else
{
// 存在的话，先要将其更新到链表的首位，有两种方法
// 1、使用 push_front + erase 但是容易迭代器失效问题
// 2、使用 splice 函数进行转移
// 这里采用第二种方法
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
return it->second->second;
}
}
void put(int key, int value)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
// 找不到说明要新增
// 需要判断一下是否需要逐出LRU
if(_capacity == _hashMap.size())
{
// 删掉LRU
_hashMap.erase(_LRUList.back().first);
_LRUList.pop_back();
}
// 插入新增元素，记得哈希表也要存
_LRUList.push_front(make_pair(key, value));
_hashMap.insert(make_pair(key, _LRUList.begin()));
}
else
{
// 找到的话则更新到链表头并修改value即可
it->second->second = value;
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
}
}
private:
// 容量是为了判断是否已经满了
size_t _capacity;
// 哈希表为查找、更新时提供O(1)的时间复杂度
typedef list<pair<int, int>>::iterator LTiter;
unordered_map<int, LTiter> _hashMap;
// 双向链表提供O(1)的插入
list<pair<int, int>> _LRUList;
};【数据结构与算法】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) 的查找。
这分别对应到 stl 中的 list 和 unordered_map ，其中要注意的是，为了能达到 O(1) 的效果，我们在 unordered_map 中存放的 value 值是 list 的迭代器 list<int, int>::iterator ，这样子就能快速找到链表中每个节点。
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：
-
LRUCache(int capacity)以 正整数 作为容量capacity初始化LRU缓存 -
int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。 -
void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。 - 函数
get和put必须以O(1)的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示： 1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105
代码实现：
代码语言：javascript代码运行次数：0运行复制class LRUCache {
public:
LRUCache(int capacity)
:_capacity(capacity)
{}
int get(int key)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
return -1;
}
else
{
// 存在的话，先要将其更新到链表的首位，有两种方法
// 1、使用 push_front + erase 但是容易迭代器失效问题
// 2、使用 splice 函数进行转移
// 这里采用第二种方法
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
return it->second->second;
}
}
void put(int key, int value)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
// 找不到说明要新增
// 需要判断一下是否需要逐出LRU
if(_capacity == _hashMap.size())
{
// 删掉LRU
_hashMap.erase(_LRUList.back().first);
_LRUList.pop_back();
}
// 插入新增元素，记得哈希表也要存
_LRUList.push_front(make_pair(key, value));
_hashMap.insert(make_pair(key, _LRUList.begin()));
}
else
{
// 找到的话则更新到链表头并修改value即可
it->second->second = value;
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
}
}
private:
// 容量是为了判断是否已经满了
size_t _capacity;
// 哈希表为查找、更新时提供O(1)的时间复杂度
typedef list<pair<int, int>>::iterator LTiter;
unordered_map<int, LTiter> _hashMap;
// 双向链表提供O(1)的插入
list<pair<int, int>> _LRUList;
};本文标签： 数据结构与算法LRU Cache 算法实现
版权声明：本文标题：【数据结构与算法】LRU Cache 算法实现 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747718497a2208373.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论