问题描述
假设我们有一个大小为m的缓存，能够容纳m个entry，初始为空。同时我们在内存中有一段包含n个entry的数据D，编号从0到n-1。现在给定一个对数据D的访问序列，每次访问一个entry。希望你能够得到一个最佳的缓存置换策略，使“缓存未命中”最少。
聪明的你不难发现，如果我们提前缓存未来将要访问的entry，就能达到100%的缓存命中，这种提前缓存的做法就是预取。本题中，并不要求大家思考预取策略，也就是说，当我们访问一个entry时，只能采取以下行为之一：
- 当缓存中存在该entry，则缓存命中
- 当缓存中不包含该entry，缓存未命中
- 未命中后，直接读取该entry并将该entry加载到缓存中
- 未命中后，直接读取该entry但不将该entry加载到缓存中
注意：当缓存满的时候，加载entry到缓存中需要先淘汰缓存中某一个entry
【输入格式】
第一行两个整数 n，m，分别表示数据D包含的entry数量和缓存最大容纳的entry数量
第二行2n 个整数，表示我们对于数据D的访问序列，每次访问一个entry，entry编号从0到n-1。为了简化题目，访问序列中每个entry都会被访问且只被访问2次。
【输出格式】
一行一个整数，表示缓存命中的最大值
【输入示例】
6 2
0 1 1 2 3 4 0 5 3 4 5 2
【输出示例】
4
【样例解释】
缓存大小为2，访问序列为0 1 1 2 3 4 0 5 3 4 5 2，依次做出如下操作（最佳策略之一）
- 访问0，缓存未命中，将0放入缓存中，此时缓存内容为 [ 0, 空 ]
- 访问1，缓存未命中，，将1放入缓存中，此时缓存内容为 [ 0, 1 ]
- 访问1，缓存命中
- 访问2，缓存未命中，不将2放入缓存中，此时缓存内容为 [ 0, 1 ]
- 访问3，缓存未命中，将3放入缓存中，并将缓存中1淘汰，此时缓存内容为 [ 0, 3 ]
- 访问4，缓存未命中，不将4放入缓存中，此时缓存内容为 [ 0, 3 ]
- 访问0，缓存命中
- 访问5，缓存未命中，将5放入缓存中，并将缓存中0淘汰，此时缓存内容为 [ 5, 3 ]
- 访问3，缓存命中
- 访问4，缓存未命中，不将4放入缓存中，此时缓存内容为 [ 5, 3 ]
- 访问5，缓存命中
- 访问2，缓存未命中，不将2放入缓存中，此时缓存内容为 [ 5, 3 ]
最终命中次数为4
问题分析与思路
缓存替换是常见的计算机问题之一，LRU算法是这个问题的经典解法之一。这道题不是让我们应用某个缓存替换算法，而是设计已知访问序列时最佳的缓存替换算法。简单的LRU算法属于通用算法，在访问模式具有时间和空间局部性时能取得不错的效果，但肯定不是已知访问序列时的最优算法，要设计最优算法，我们可以从题目的例子出发，思考如何让命中次数最大。
我们一旦解出这道题，根据计算理论，我们就证明了“在已知访问序列情况下最优缓存替换”问题是P问题
当缓存大小为2，访问序列为0 1 1 2 3 4 0 5 3 4 5 2时，由于未达到缓存上限，我们肯定要将前两次访问缓存下来（这对我们没有任何损失）。第三次我们命中了，但第四次我们就得决定缓存与否，不缓存我们就失去了后面命中2的可能，缓存就意味着淘汰，幸运的是1已经被访问两次了（题目说每个项最多访问两次），我们就可以用2替换1，这不会给我们带来损失。第五次我们遇到3，但不幸的是0和2都只出现了一次，和3一样未来都会再次出现，非常直接的想法，我们替换掉那个第二次出现最远的项，因为它带来的命中收益是最低的。这样我们就能得出一种贪心的策略，一直添加直到缓存池满，如果当前项之前出现了却不在缓存池中，我们就无视它，如果当前项第一次出现，从缓存池中淘汰现两次的项，否则淘汰第二次出现最远的项。
代码
时间复杂度为O(nm)
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
int n,m;
cin >> n >> m;
vector<int> nums;
map<int, pair<int,int> > positions;
n = 2*n;
for (int i=0;i<n;i++) {
int temp;
cin >> temp;
nums.push_back(temp);
if (!positions.count(temp)) {
positions[temp] = {i,-1};
}
else {
positions[temp].second = i;
}
}
set<int> pool;
int i = 0;
int hits = 0;
for (i=0; pool.size() < m; i++) {
if (pool.count(nums[i])) {
hits++;
}
else {
pool.insert(nums[i]);
}
}
for (;i<n;i++) {
if (pool.count(nums[i])) {
hits++;
}
else {
if (positions[nums[i]].first < i) {
continue;
}
for (auto it = pool.begin();it != pool.end();it++) {
if(positions[*it].second < i) {
it = pool.erase(it);
break;
}
}
if (pool.size() != m) {
pool.insert(nums[i]);
}
else {
int option = nums[i];
for (auto it = pool.begin();it != pool.end();it++) {
if(positions[*it].second > positions[nums[i]].second && positions[*it].second > positions[option].second) {
option = *it;
}
}
if (option != nums[i]) {
pool.erase(option);
pool.insert(nums[i]);
}
}
}
}
cout << hits << endl;
}