本题需要掌握mapvectorLRU的写法一、梳理题意1. 输入输出题目给出一个组相联缓存以及处理器接下来执行的q条读写指令。缓存初始为空我们需要模拟这些指令输出处理器真正对内存进行的读写操作。输入中的每条指令格式为o ao 0处理器要读取内存块ao 1处理器要写入内存块a。需要注意输入描述的是处理器想要进行的操作输出描述的则是缓存机制处理后真正落到内存上的操作。二者并不完全相同。2. 缓存的基本结构缓存一共有N个组每个组有n个缓存行因此缓存行总数为n × N内存块a只能进入一个固定的组。题目给出的组号计算公式是int groupId (a / n) % N;这是本题非常重要、也很容易写错的地方。它不是常见的a % N必须严格按照题目给出的(a / n) % N计算。例如当n 4N 8时内存块 0、1、2、3 属于组 0 内存块 4、5、6、7 属于组 1 …… 内存块 32、33、34、35 又属于组 03. 命中与未命中处理一条指令时首先在它所属的组中查找对应的内存块。如果已经存在称为缓存命中如果不存在称为缓存未命中。缓存命中时处理器直接访问缓存不需要访问内存因此不会产生输出。缓存未命中时无论原指令是读还是写都必须先把该内存块从内存载入缓存因此一定要输出0 a例如缓存中没有块10现在执行1 10虽然原指令是写操作但处理器仍然要先从内存读取块10再在缓存中修改所以实际内存操作是0 10此时缓存中的块10会被标记为脏块。4. 脏块如果一个缓存行被执行过写操作那么缓存中的数据已经和内存中的原数据不同这个缓存行就是脏块。当脏块一直保留在缓存中时不需要立刻写入内存。只有它被替换出去时才需要先写回内存。假设要载入新块33但是根据 LRU 规则需要替换脏块2那么实际内存操作顺序是1 2 0 33含义分别是把脏块2写回内存从内存读取新块33。5. LRU 替换规则每个组都按照最近使用情况排列其中的缓存行队头最近使用 队尾最久未使用每次读写一个已经存在的缓存行都要把它移动到队头。发生未命中并且该组已满时替换队尾的缓存行因为它最久没有被访问。二、解题流程1. 每条指令的处理流程对于一条指令operation block处理流程可以概括为第一步计算组号int groupId (block / n) % N;第二步查询是否命中我们使用unordered_mapint, int position;记录一个内存块当前位于哪个缓存行。例如position[32] 5;表示内存块32当前保存在编号为5的缓存行中。因此可以使用auto result position.find(block);判断该内存块是否在缓存中。第三步根据命中情况处理如果命中读操作不改变脏标记写操作把缓存行标记为脏把缓存行移动到所在组的队头不产生实际内存操作。如果未命中如果组已满替换队尾缓存行被替换的缓存行是脏块时先输出写回操作输出读取新块的操作把新块放在队头根据原指令是读还是写设置脏标记。2. 为什么不能每次遍历整个组最容易想到的方法是为每个组使用一个数组每次从头到尾查找目标块。但一个组最多可能包含65536个缓存行指令数最多为10^5。如果每条指令都遍历整个组最坏时间复杂度会达到O(q × n)最坏情况下运算次数可能超过几十亿容易超时。所以我们需要同时解决两个问题使用哈希表在平均O(1)时间内判断是否命中使用双向链表在O(1)时间内更新 LRU 顺序。3. 为什么不用复杂的迭代器写法一种常见写法是unordered_mapint, listCacheLine::iterator它可以直接记录一个内存块在链表中的迭代器但这种类型嵌套较多对刚接触 STL 的同学不够直观。本题可以把所有缓存行进行编号改成unordered_mapint, int position;此时哈希表只需要表达内存块编号 → 缓存行编号再在每个缓存行中保存前一个和后一个缓存行编号就可以自己维护双向链表。4. 缓存行结构体每个缓存行保存四项信息struct CacheLine { int block; int previous; int next; bool dirty; };各字段含义如下字段含义block当前缓存行保存的内存块编号previousLRU 队列中的前一个缓存行编号nextLRU 队列中的后一个缓存行编号dirty当前缓存行是否被写过每个组另外维护vectorint head(N, -1); vectorint tail(N, -1); vectorint groupSize(N, 0);head[i]第i组最近使用的缓存行tail[i]第i组最久未使用的缓存行groupSize[i]第i组当前保存了多少个有效块。初始值-1表示该组中还没有缓存行。5. 从 LRU 队列中删除缓存行删除函数如下void removeLine( int groupId, int id, vectorCacheLine cache, vectorint head, vectorint tail ) { int previous cache[id].previous; int next cache[id].next; if (previous ! -1) { cache[previous].next next; } else { head[groupId] next; } if (next ! -1) { cache[next].previous previous; } else { tail[groupId] previous; } }删除一个节点时需要修改它两侧节点的连接关系。如果previous -1说明当前节点原来是队头因此需要更新head[groupId] next;如果next -1说明当前节点原来是队尾因此需要更新tail[groupId] previous;这个函数只修改常数个变量因此时间复杂度是O(1)。6. 把缓存行加入队头加入队头的函数如下void addToFront( int groupId, int id, vectorCacheLine cache, vectorint head, vectorint tail ) { cache[id].previous -1; cache[id].next head[groupId]; if (head[groupId] ! -1) { cache[head[groupId]].previous id; } else { tail[groupId] id; } head[groupId] id; }新队头没有前驱因此cache[id].previous -1;它的后继是原来的队头cache[id].next head[groupId];如果原来的组为空新节点既是队头也是队尾tail[groupId] id;最后更新队头head[groupId] id;该操作的时间复杂度同样是O(1)。7. 缓存命中的代码查询结果不等于position.end()时说明命中if (result ! position.end()) { int id result-second; if (operation 1) { cache[id].dirty true; } if (head[groupId] ! id) { removeLine(groupId, id, cache, head, tail); addToFront(groupId, id, cache, head, tail); } }其中int id result-second;取得该内存块所在的缓存行编号。如果当前是写操作cache[id].dirty true;然后把它移动到队头。移动操作可以理解为先从原位置删除再插入队头。如果它本来就是队头就不需要移动。8. 缓存未命中的代码未命中时先判断当前组是否已满if (groupSize[groupId] n)情况一当前组已满队尾就是要被替换的缓存行id tail[groupId];取得旧内存块编号int oldBlock cache[id].block;如果它是脏块就需要先写回if (cache[id].dirty) { cout 1 oldBlock \n; }然后删除旧内存块的哈希表记录并从 LRU 队列中删除该缓存行position.erase(oldBlock); removeLine(groupId, id, cache, head, tail);这里不需要创建新的缓存行可以直接重复使用被替换的缓存行编号id。情况二当前组未满使用一个从未使用过的新缓存行id usedCacheLines; groupSize[groupId];载入新块无论原指令是读还是写未命中时都需要先读取内存cout 0 block \n;然后覆盖缓存行中的信息cache[id].block block; cache[id].dirty (operation 1);如果原指令是写操作新块载入后会立即在缓存中被修改因此dirty true最后将新块放到队头并记录它所在的缓存行编号addToFront(groupId, id, cache, head, tail); position[block] id;9. 样例关键过程样例中n 4N 8内存块0、1、2、32、33、34都属于组0。前六条指令执行后组0的 LRU 顺序为队头 32 → 0 → 1 → 2 队尾此时执行1 33块33未命中并且组0已满因此替换队尾的块2。块2之前执行过写操作是脏块所以先输出1 2然后读取新块330 33载入后新的 LRU 顺序为队头 33 → 32 → 0 → 1 队尾由于原指令是写操作因此块33被标记为脏块。三、总结1. 整体思路这道题需要同时模拟三件事根据(block / n) % N确定内存块所属的缓存组使用哈希表快速判断内存块是否已经在缓存中使用双向链表维护每个组的 LRU 顺序。哈希表采用unordered_mapint, int position;记录内存块编号 → 缓存行编号LRU 队列规定队头是最近使用队尾是最久未使用处理指令时命中写操作标脏并移动到队头未命中且组未满读取新块并插入队头未命中且组已满替换队尾脏块先写回再读取新块。2. 容易出错的地方错误一写错组号公式正确写法是int groupId (block / n) % N;错误二认为写未命中要直接写内存题目采用写回法。写未命中时要先从内存载入数据0 block然后只在缓存中修改并标脏不会立刻输出1 block错误三替换时先读取新块再写回旧块正确顺序是先写回被替换的脏块 再读取新块错误四命中后没有更新 LRU无论读命中还是写命中都代表该块刚刚被使用必须将它移动到队头。3. 复杂度分析哈希表查询、插入和删除的平均时间复杂度为O(1)双向链表的删除和队头插入也是O(1)。因此时间复杂度平均 O(q) 空间复杂度O(n × N)能够满足q ≤ 10^5 n × N ≤ 655364. 完整 C 代码#include iostream #include unordered_map #include vector using namespace std; struct CacheLine { int block; // 当前保存的内存块编号 int previous; // LRU 队列中的前一个缓存行 int next; // LRU 队列中的后一个缓存行 bool dirty; // 是否被写过 }; // 从第 groupId 组的 LRU 队列中删除编号为 id 的缓存行 void removeLine( int groupId, int id, vectorCacheLine cache, vectorint head, vectorint tail ) { int previous cache[id].previous; int next cache[id].next; if (previous ! -1) { cache[previous].next next; } else { // id 原来是队头 head[groupId] next; } if (next ! -1) { cache[next].previous previous; } else { // id 原来是队尾 tail[groupId] previous; } } // 将编号为 id 的缓存行插入第 groupId 组的队头 void addToFront( int groupId, int id, vectorCacheLine cache, vectorint head, vectorint tail ) { cache[id].previous -1; cache[id].next head[groupId]; if (head[groupId] ! -1) { cache[head[groupId]].previous id; } else { // 原来的组为空id 同时是队头和队尾 tail[groupId] id; } head[groupId] id; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, N, q; cin n N q; int totalCacheLines n * N; // 保存所有缓存行 vectorCacheLine cache(totalCacheLines); // 每个组的队头、队尾和当前大小 vectorint head(N, -1); vectorint tail(N, -1); vectorint groupSize(N, 0); // position[内存块编号] 缓存行编号 unordered_mapint, int position; position.reserve(totalCacheLines * 2); // 已经分配过多少个缓存行 int usedCacheLines 0; for (int i 0; i q; i) { int operation, block; cin operation block; // 计算该内存块所属的缓存组 int groupId (block / n) % N; auto result position.find(block); if (result ! position.end()) { // 缓存命中 int id result-second; if (operation 1) { // 写操作将缓存行标记为脏 cache[id].dirty true; } // 将被访问的缓存行移动到队头 if (head[groupId] ! id) { removeLine(groupId, id, cache, head, tail); addToFront(groupId, id, cache, head, tail); } } else { // 缓存未命中 int id; if (groupSize[groupId] n) { // 当前组已满选择队尾的缓存行进行替换 id tail[groupId]; int oldBlock cache[id].block; if (cache[id].dirty) { // 脏块被替换前需要先写回内存 cout 1 oldBlock \n; } // 删除旧块的哈希表记录和 LRU 记录 position.erase(oldBlock); removeLine(groupId, id, cache, head, tail); } else { // 当前组未满分配一个新的缓存行 id usedCacheLines; groupSize[groupId]; } // 未命中时需要从内存读取新块 cout 0 block \n; // 将新块保存到缓存行中 cache[id].block block; cache[id].dirty (operation 1); // 新块是最近使用的加入队头 addToFront(groupId, id, cache, head, tail); // 记录新块所在的缓存行 position[block] id; } } return 0; }转载注明出处