| 146 | LRU Cache |
这个基于双向链表+Map表
- 第一步：分析LRU特点
2大特点：
- 保持顺序，即访问顺序FIFO。保持顺序的只有顺序类型如链表、数组
- 快速查找，给定的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;
};
相关推荐
算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU Cache 算法面试通关40讲完整课件 57-58 LRU ...
lru算法实现leetcode Progress Every Day LeetCode => 传送门
146 LRU Cache in Java 我很喜欢这个问题。 我在康奈尔大学的第一个 CS 课程涉及队列和其他数据结构。 对于其中一个课堂项目，我们必须开发基于队列的模拟。 在工作中，我开发了广泛的队列库。 我能说什么； 我喜欢...
LRU_cache (Leetcode 146) 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作：get 和 set。 get(key) – 如果键存在于缓存中，则获取键的值（将始终为正），否则返回 -1。 set(key, value) – ...
146. LRU Cache 数据结构 双向链表的删除和插入节点 20200525 190. Reverse Bits 二进制位数 二进制的&和>> << >>== 20200525 172. Factorial Trailing Zeroes 数学分析 递归和循环 20200525 191. Number of 1...
操作系统中的Cache与内存间的置换算法有LRU，FIFO等经典算法，作者首先程序实现了此2种算法，并在此2者的基础上创新出一个新的置换算法LRU_FIFO算法，获得高校教师很高评价，该算法结合LRU与FIFO的特点，也可单独...
lru cache leetcode LeetCode-Tencent50 Task0 最小栈 Task1 有效的括号 Task2 数组中的第K个最大元素 Task3 合并K个有序链表 Task4 买卖股票的最佳时机 II Task5 排序链表 Task6 子集 Task7 只出现一次的数字 Task8...
提取google开源软件leveldb的lru cache部分，独立出来，并增加过期时间，过期失效，可独立使用。仅供参考。
谷歌官方视频
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) – Get the value (will always be positive) of the key if ...
lru cache leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from Sorted Array 2 Remove Duplicates from Sorted Array ...
lru cache leetcode LeetCode LeetCode刷题训练 算法 链表 字符串 二叉树 图 有趣的题目 动态规划
lru cache leetcode leetcode leetcode solutions in C++ 微信公众号：曲奇泡芙 （互联网&车联网技术） solutions for problems(0001~0200) ./0001-two-sum.cpp ./0002-add-two-numbers.cpp ./0003-longest-...
lru缓存leetcode LRU_Cache LRU_Cache 是一个 leetcode 问题，需要深入了解数据结构。 在 LRU_Cache 的实现中，使用了 LinkedHashTable。
LRU Cache是一个Cache的置换算法，含义是“近少使用”，把满足“近少使用”的数据从Cache中剔除出去，并且保证Cache中第一个数据是近刚刚访问的，因为这样的数据更有可能被接下来的程序所访问。 LRU的应用比较...
lru cache leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机...
lru cache leetcode leetcode AC题目汇总 目前AC题目有: other AC题目 打印沙漏
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的题目, 分为一些子项 bytedance daily：每日一题 struct-algorithm：数据结构/算法先关 top-100：leetcode 热题100 .go文件以题目url后缀...
lru cache leetcode LeetCode-go leetcode中文网站 目录 序号 名字 中文名字 备注 0 binarySearch 二分查找法 1 两数之和 2 两数相加 3 longestSubstr 无重复最长字串 4 findMedianSortedArrays 寻找两个有序数组的...
lru cache leetcode leetcode 序号 名称 难度 标签 链接 备注 排名 1 easy N Sum 2 medium 3 medium 4 hard 5 medium 6 medium 7 easy 8 medium 9 easy 10 hard 11 medium 12 medium 13 easy 14 easy 15 medium N ...