最近最少使用(LRU, Least recently used)缓存算法

在这里插入图片描述

思路

性能限制很高、数据量很大时，cin、cout肯定是不够快的。
（1）可以利用getchar()速度快的特性设计快读函数读取整数，可以做到用scanf()函数5倍的速度读入任意整数：

#include<cstdio>
// 仅正整数可用
#define read(a) {char c;while((c=getchar())>47) a=a*10+(c^48);}
// 正负整数均可用
inline void read(int& a)
{int s = 0, w = 1;char ch = getchar();while (ch < '0' || ch>'9'){//为了避免输入数字之前的空格造成影响以及判断正负if (ch == '-') { w = -1; }ch = getchar();}while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}a = s * w;
}

（2）快写，注意中printf()也比cout快，如果输出不是int类型，可以用printf(“<式样化字符串>”，<参数表>)；

printf( "%s", s );                                                 // 输出string
printf(”%.3s“, hello);或者 printf("message: '%.*s'\n", 3, hello);  // 输出指定宽度的string
bool b=true; if(b) printf("true"); else printf("false");          // 输出bool类型变量
printf("%d",int_num)                                              // 输出整数型变量

#include<cstdio>
inline void write(int n)
{if (n < 0){putchar('-');n *= -1;}if (n > 9){write(n / 10);}putchar(n % 10 + '0');
}

（3）快速存取：使用满足 LRU (最近最少使用) 缓存约束的数据结构

思路：使用一个双指针链表和一个哈希表，所有增删查改复杂度为O(1)
1.双链表表示资源池，存储处于空闲状态的结点；结点包含左右指针，key：value，key表示id编号，value表示此时结点是否处于被占用状态。0表示被占用，1表示空闲。
2.哈希表unordered_map<int,Node*>存储id=key对应的链表中的节点, 用于快速查找链表中结点的位置以便增删改查。
3.初始化：双链表资源池和哈希表key根据资源池范围初始化，value全部设定为空闲状态1；
4.操作：分配的本质是从资源池中删除，释放的本质是添加到资源池的末尾
1>动态分配k个资源：
用双链表遍历前k个node，如果node对应的value为1，则依次置0，并从双链表中删除node
2>指定分配第k个资源
用哈希表查找key=k的node；
如果node对应的value为1，则置0，双链表将该node删除；
3>释放第k个资源：
用哈希表判断key对应的结点；
判断是否被占用（value是否为0）。如果为0，则value置为1表示空闲，同时将key对应的节点放到双链表的最右侧；
5.输出：资源池的第一个空闲资源id即链表的第一个结点的key。注意这题保证每个用例最后都有空闲资源ID。

代码如下：

# include<unordered_map>
# include<cstdio>
# include<iostream>
using namespace std;struct Node {int key;int value;Node* left, * right;Node(int _key, int _value) : key(_key), value(_value), left(NULL), right(NULL) {}
};//双链表的最左和最右节点，不存贮值。class LRUCache {
public:Node* L;Node* R;LRUCache() {L = new Node(-1,-1),R = new Node(-1,-1);L->right = R;R->left = L;    }void remove(Node* p){p->right->left = p->left;p->left->right = p->right;p->value=0;//cout<<"id:"<<p->key<<" remove"<<endl;}void insert(Node *p){p->right = R;p->left = R->left;R->left->right = p;R->left = p;p->value=1;//cout<<"id:"<<p->key<<" insert"<<endl;}};inline void read(int& a)
{int s = 0;char ch = getchar();while (ch < '0' || ch>'9') ch = getchar();while (ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}a = s;
}int main() {int start, end;read(start);read(end);//cout<<"s "<<start<<" e "<<end<<endl;LRUCache* pool = new LRUCache();  //双链表unordered_map<int,Node*>hash;  // 哈希表for (int id =start;id<=end;id++){Node* resource = new Node(id,1);pool->insert(resource);  // 初始化双链表hash[id] = resource;     // 初始化哈希表}int opnums;read(opnums);int opk,opn;for (int op =0;op<opnums;op++){read(opk);  //操作的类型read(opn);  //操作的参数if (opk==1){if (opk>end-start+1) opn=end-start+1;for (int index = 0;index<opn;index++){Node *p=pool->L->right;if (p->value>0) pool->remove(p);}}if (opk==2){//cout<<"操作2指定分配"<<endl;if (hash.count(opn)) {Node *p=hash[opn];if (p->value>0) pool->remove(p);}}if (opk==3){//cout<<"操作2释放"<<endl;if(hash.count(opn)) {Node *p=hash[opn];if (!p->value) pool->insert(p);}}}printf("%d", pool->L->right->key);return 0;
}