缓存模拟时间限制1.0 秒空间限制512 MiB相关文件题目目录题目背景西西艾弗岛半导体制造厂近期正在研发一种新型的处理器产品。该处理器的缓存计划采用组相连的方式。 为了选定合适的组相连参数我们需要对缓存的工作过程进行模拟进而推算其性能。处理器的缓存存储着内存中的部分数据。当处理器的运行需要访问内存中的数据时如果所需数据已经存储在缓存中则可以用更为快捷的缓存访问代替内存访问来提高处理器性能。处理器的缓存包含若干缓存行每个缓存行存储特定大小的数据。为了便于叙述我们认为处理器对内存的访问也是以缓存行为单位进行的。 以缓存行的大小为单位将全部内存空间划分为若干块编号从 00 开始这样每个内存块的数据便可以恰好存储在一个缓存行中。nn-路组相联是这样的一种缓存结构每 nn 个缓存行划分为一组。假设共有 NN 个这样的组编号从 00 到 N−1N−1那么编号为 kk 的内存块仅可以被存储在编号为 (k÷n)(k÷n) 的组这 nn 个缓存行的任意一个中。其中÷÷ 表示忽略余数的整除运算 表示整除取余数运算。一般而言nn 和 NN 是 22 的幂次。例如当 n4n4、N8N8 时编号为 0、1、2、3、32、33、34、35 的内存块可以被存储在组0 的任意缓存行中编号为 4、5、6、7、36、37、38、39 的内存块可以被存储在组1 的任意缓存行中。题目描述具体而言给定要读取或写入的内存块编号即可确定该内存块可能位于的缓存行组的编号。此时可能存在的情况有两种该缓存行组的某个缓存行已经存储了该内存块的数据即命中该缓存行组的所有缓存行都没有存储该内存块的数据即未命中。当发生命中时处理器可以直接使用或修改该缓存行中的数据而不需要实际读写内存。 当发生未命中时处理器需要从内存中读取数据并将其存储到该缓存行组中的一个缓存行中然后再使用或修改该缓存行中的数据。这个将内存中的数据读入到缓存的过程称为载入。当执行载入操作时如果该缓存行组中有尚未存储数据的缓存行那么将数据存储到其中一个尚未存储数据的缓存行中并在缓存行中记录所存储的数据块的编号否则按照一定方法选择该组中的一个缓存行并将数据存储到其中这一过程称为替换。当发生替换时需要考虑被替换的缓存行是否发生过修改即执行过写操作。如果发生过修改则需要先将缓存行中的数据写入内存中的对应位置然后忽略该缓存行中的数据、将新读入的数据存入其中并记录所存储数据块的编号。在一个缓存行组中选择被替换的缓存行的方法有很多种该种处理器采用的是最近最少使用LRU方法。该方法将一个缓存行组中存有数据的缓存行排成一队每次读或写一个缓存行时都将该缓存行移动到队列的最前端。当需要替换缓存行时选择队列的最后一个缓存行最久没被读写进行替换。本题目中将给出一系列的处理器运行时遇到的对内存的读写指令并假定初始时处理器的缓存为空。你需要根据上文描述的缓存工作过程给出处理器对内存的实际读写操作序列。输入格式从标准输入读入数据。输入的第一行包含空格分隔的三个整数 n,N,qn,N,q分别表示组相联的路数 nn 和组数 NN以及要处理的读写指令的数量 qq。接下来 qq 行每行包含空格分隔的两个整数 oo 和 aa。其中oo 表示读写指令的类型aa 表示要读写的内存块的编号。oo 为 00 或 11分别表示读和写操作。输出格式输出到标准输出。输出若干行每行包含空格分隔的两个整数 o′o′ 和 a′a′表示实际处理器对内存的读写操作。o′o′ 为 00 或 11分别表示读和写操作a′a′ 表示要读写的内存块的编号。样例输入4 8 8 0 0 0 1 1 2 0 1 1 0 0 32 1 33 0 34样例输出0 0 0 1 0 2 0 32 1 2 0 33 0 34样例解释该处理器的缓存为 4 路组相联共有 8 组。初始时处理器的缓存为空。共需要处理 8 条指令第 1 条指令为读取内存块 0未命中要实际读取内存块 0并存储到组 0 的一个缓存行第 2 条指令为读取内存块 1未命中要实际读取内存块 1并存储到组 0 的另一个缓存行第 3 条指令为写入内存块 2未命中要实际读取内存块 2并存储到组 0 的第三个缓存行然后根据指令在缓存中对其进行修改第 4 条指令为读取内存块 1命中直接从缓存中调取数据第 5 条指令为写入内存块 0命中直接修改缓存中的数据第 6 条指令为读取内存块 32未命中要实际读取内存块 32并存储到组 0 的第四个缓存行第 7 条指令为写入内存块 33未命中此时组 0 中的 4 个缓存行都保存了数据最近使用的是保存有内存块 32 的缓存行其次是保存有内存块 0 的缓存行然后是 1最后是 2因此选择替换保存有内存块 2 的缓存行。注意到该缓存行在执行第 3 条指令时被修改过因此需要先将其写入内存然后再读取内存块 33 的数据存储到该缓存行中第 8 条指令为读取内存块 34未命中此时组 0 中的 4 个缓存行都保存了数据按照同样的办法选择保存有内存块 1 的缓存行替换。注意到该缓存行未被修改过因此可以直接读取内存块 34 的数据存储到该缓存行中。子任务对于 20% 的数据有 n1,N1n1,N1对于 40% 的数据有 n1n1另外 20% 的数据有 N1,q≤nN1,q≤n对于 100% 的数据有 1≤n,N,n×N≤655361≤n,N,n×N≤65536且 n,Nn,N 为 2 的幂次1≤q≤1051≤q≤1050≤a2300≤a230。#includeiostream #includevector #includeunordered_map #includelist #includecstring using namespace std; #define dashu 100005 int n,N,q;//n cachesize; N cacheline amount; q amount of command struct danyuan{ listint::iterator weizhi;//队列内部的迭代器end()是无效的 int dirty; //int bianhao;//对应的内存块编号 //int val;//模拟不需要考虑 }; struct custom_hash { size_t operator()(int x) const { x ((x 16) ^ x) * 0x45d9f3b; x ((x 16) ^ x) * 0x45d9f3b; x (x 16) ^ x; return (size_t)x; } }; struct cache_line{ listint que; unordered_mapint,danyuan,custom_hash xuhaozhi; }; void out(cache_line hang){ coutlist: ---------endl; for(auto it:hang.que){ coutit ; }coutendl; couthash: ---------endl; for(auto it:hang.xuhaozhi){ int valit.first; coutval ; }coutendl; coutendl; } //cache_line zuxianglian[dashu]; void read(int num){ printf(0 %d\n,num); } void write(int num){ printf(1 %d\n,num); } //输入序号O(1)时间查到内存块是否在缓存行中 bool hit(int xuhao,cache_line hang){ auto ithang.xuhaozhi.find(xuhao); if(ithang.xuhaozhi.end()){ //coutxuhaonot in dictendl; return false; } //string res(it-second.weizhi!hang.que.end())? hit: not hit; //coutxuhaoresendl; return (it-second.weizhi!hang.que.end()); } //通过哈希表找到list中相应的迭代器保证list头插入该迭代器 void hitmod(int caozuo,int xuhao,cache_line hang){ auto ithang.xuhaozhi[xuhao].weizhi; hang.que.splice(hang.que.begin(),hang.que,it); if(hang.xuhaozhi[xuhao].dirty0caozuo1) hang.xuhaozhi[xuhao].dirty1; } void addnode(int caozuo,int xuhao,cache_line hang){ read(xuhao); hang.que.push_front(xuhao); auto ithang.que.begin(); hang.xuhaozhi[xuhao]{it,caozuo}; //coutxuhao (*it)endl; } int LRUvic(cache_line hang){ return *hang.que.rbegin(); } void delmod(int victim){ write(victim); } //忽略缓存单元旧的值把新的值放上去顺便换到队首 void delnode(int caozuo,int xuhao,int victim,cache_line hang){ read(xuhao); auto ithang.xuhaozhi[victim].weizhi; *itxuhao; //链表把删除的节点替换到最前面 hang.que.splice(hang.que.begin(),hang.que,it); //哈希表删除旧内存块索引更新新的内存块索引 hang.xuhaozhi.erase(victim); hang.xuhaozhi[xuhao]{it,caozuo}; } void solve(int caozuo,int xuhao,cache_line hang){ //coutcaozuo xuhaoendl; if(hit(xuhao,hang)) { hitmod(caozuo,xuhao,hang); return; } //load if((signed)hang.que.size()n){ addnode(caozuo,xuhao,hang); //coutaddnode caozuo xuhao (hang)endl; return; } //replace int victimLRUvic(hang);//返回队尾的内存块编号 //未命中满队列替换写回绝对要考虑脏位 //队列里绝对没有这个内存块 danyuan victhang.xuhaozhi[victim]; if(vict.dirty){ delmod(victim); } delnode(caozuo,xuhao,victim,hang); return; } int main(){ //freopen(1.in,r,stdin); ios_base::sync_with_stdio(0); cin.tie(0); scanf(%d %d %d,n,N,q); //试试模块化一步步来 //初始化一下 vectorcache_line zuxianglian(N); for (int i 0; i N; i) { zuxianglian[i].xuhaozhi.reserve(n * 2); // 提前分配足够桶 zuxianglian[i].xuhaozhi.max_load_factor(0.25); // 降低负载率减少碰撞 } for(int i1;iq;i){ int caozuo,xuhao;//操作 序号 scanf(%d %d,caozuo,xuhao); int formatxuhaoxuhao%(n*N); int gnformatxuhao/n; auto hangzuxianglian[gn]; //coutstart----- caozuo xuhaoendl; solve(caozuo,xuhao,hang); //out(hang); //coutcaozuo xuhao gnendl; } return 0; }非常奇怪不使用哈希表是90分用了哈希表也是90红黑树也是90Claude生成了双向链表和手搓哈希表加快读都没过非常奇怪不知道性能瓶颈在哪里。也构造了新的哈希函数避免哈希被卡。太奇怪了百思不得其解
CCF-202412-T3缓存模拟90分
发布时间：2026/5/26 22:00:02
缓存模拟时间限制1.0 秒空间限制512 MiB相关文件题目目录题目背景西西艾弗岛半导体制造厂近期正在研发一种新型的处理器产品。该处理器的缓存计划采用组相连的方式。 为了选定合适的组相连参数我们需要对缓存的工作过程进行模拟进而推算其性能。处理器的缓存存储着内存中的部分数据。当处理器的运行需要访问内存中的数据时如果所需数据已经存储在缓存中则可以用更为快捷的缓存访问代替内存访问来提高处理器性能。处理器的缓存包含若干缓存行每个缓存行存储特定大小的数据。为了便于叙述我们认为处理器对内存的访问也是以缓存行为单位进行的。 以缓存行的大小为单位将全部内存空间划分为若干块编号从 00 开始这样每个内存块的数据便可以恰好存储在一个缓存行中。nn-路组相联是这样的一种缓存结构每 nn 个缓存行划分为一组。假设共有 NN 个这样的组编号从 00 到 N−1N−1那么编号为 kk 的内存块仅可以被存储在编号为 (k÷n)(k÷n) 的组这 nn 个缓存行的任意一个中。其中÷÷ 表示忽略余数的整除运算 表示整除取余数运算。一般而言nn 和 NN 是 22 的幂次。例如当 n4n4、N8N8 时编号为 0、1、2、3、32、33、34、35 的内存块可以被存储在组0 的任意缓存行中编号为 4、5、6、7、36、37、38、39 的内存块可以被存储在组1 的任意缓存行中。题目描述具体而言给定要读取或写入的内存块编号即可确定该内存块可能位于的缓存行组的编号。此时可能存在的情况有两种该缓存行组的某个缓存行已经存储了该内存块的数据即命中该缓存行组的所有缓存行都没有存储该内存块的数据即未命中。当发生命中时处理器可以直接使用或修改该缓存行中的数据而不需要实际读写内存。 当发生未命中时处理器需要从内存中读取数据并将其存储到该缓存行组中的一个缓存行中然后再使用或修改该缓存行中的数据。这个将内存中的数据读入到缓存的过程称为载入。当执行载入操作时如果该缓存行组中有尚未存储数据的缓存行那么将数据存储到其中一个尚未存储数据的缓存行中并在缓存行中记录所存储的数据块的编号否则按照一定方法选择该组中的一个缓存行并将数据存储到其中这一过程称为替换。当发生替换时需要考虑被替换的缓存行是否发生过修改即执行过写操作。如果发生过修改则需要先将缓存行中的数据写入内存中的对应位置然后忽略该缓存行中的数据、将新读入的数据存入其中并记录所存储数据块的编号。在一个缓存行组中选择被替换的缓存行的方法有很多种该种处理器采用的是最近最少使用LRU方法。该方法将一个缓存行组中存有数据的缓存行排成一队每次读或写一个缓存行时都将该缓存行移动到队列的最前端。当需要替换缓存行时选择队列的最后一个缓存行最久没被读写进行替换。本题目中将给出一系列的处理器运行时遇到的对内存的读写指令并假定初始时处理器的缓存为空。你需要根据上文描述的缓存工作过程给出处理器对内存的实际读写操作序列。输入格式从标准输入读入数据。输入的第一行包含空格分隔的三个整数 n,N,qn,N,q分别表示组相联的路数 nn 和组数 NN以及要处理的读写指令的数量 qq。接下来 qq 行每行包含空格分隔的两个整数 oo 和 aa。其中oo 表示读写指令的类型aa 表示要读写的内存块的编号。oo 为 00 或 11分别表示读和写操作。输出格式输出到标准输出。输出若干行每行包含空格分隔的两个整数 o′o′ 和 a′a′表示实际处理器对内存的读写操作。o′o′ 为 00 或 11分别表示读和写操作a′a′ 表示要读写的内存块的编号。样例输入4 8 8 0 0 0 1 1 2 0 1 1 0 0 32 1 33 0 34样例输出0 0 0 1 0 2 0 32 1 2 0 33 0 34样例解释该处理器的缓存为 4 路组相联共有 8 组。初始时处理器的缓存为空。共需要处理 8 条指令第 1 条指令为读取内存块 0未命中要实际读取内存块 0并存储到组 0 的一个缓存行第 2 条指令为读取内存块 1未命中要实际读取内存块 1并存储到组 0 的另一个缓存行第 3 条指令为写入内存块 2未命中要实际读取内存块 2并存储到组 0 的第三个缓存行然后根据指令在缓存中对其进行修改第 4 条指令为读取内存块 1命中直接从缓存中调取数据第 5 条指令为写入内存块 0命中直接修改缓存中的数据第 6 条指令为读取内存块 32未命中要实际读取内存块 32并存储到组 0 的第四个缓存行第 7 条指令为写入内存块 33未命中此时组 0 中的 4 个缓存行都保存了数据最近使用的是保存有内存块 32 的缓存行其次是保存有内存块 0 的缓存行然后是 1最后是 2因此选择替换保存有内存块 2 的缓存行。注意到该缓存行在执行第 3 条指令时被修改过因此需要先将其写入内存然后再读取内存块 33 的数据存储到该缓存行中第 8 条指令为读取内存块 34未命中此时组 0 中的 4 个缓存行都保存了数据按照同样的办法选择保存有内存块 1 的缓存行替换。注意到该缓存行未被修改过因此可以直接读取内存块 34 的数据存储到该缓存行中。子任务对于 20% 的数据有 n1,N1n1,N1对于 40% 的数据有 n1n1另外 20% 的数据有 N1,q≤nN1,q≤n对于 100% 的数据有 1≤n,N,n×N≤655361≤n,N,n×N≤65536且 n,Nn,N 为 2 的幂次1≤q≤1051≤q≤1050≤a2300≤a230。#includeiostream #includevector #includeunordered_map #includelist #includecstring using namespace std; #define dashu 100005 int n,N,q;//n cachesize; N cacheline amount; q amount of command struct danyuan{ listint::iterator weizhi;//队列内部的迭代器end()是无效的 int dirty; //int bianhao;//对应的内存块编号 //int val;//模拟不需要考虑 }; struct custom_hash { size_t operator()(int x) const { x ((x 16) ^ x) * 0x45d9f3b; x ((x 16) ^ x) * 0x45d9f3b; x (x 16) ^ x; return (size_t)x; } }; struct cache_line{ listint que; unordered_mapint,danyuan,custom_hash xuhaozhi; }; void out(cache_line hang){ coutlist: ---------endl; for(auto it:hang.que){ coutit ; }coutendl; couthash: ---------endl; for(auto it:hang.xuhaozhi){ int valit.first; coutval ; }coutendl; coutendl; } //cache_line zuxianglian[dashu]; void read(int num){ printf(0 %d\n,num); } void write(int num){ printf(1 %d\n,num); } //输入序号O(1)时间查到内存块是否在缓存行中 bool hit(int xuhao,cache_line hang){ auto ithang.xuhaozhi.find(xuhao); if(ithang.xuhaozhi.end()){ //coutxuhaonot in dictendl; return false; } //string res(it-second.weizhi!hang.que.end())? hit: not hit; //coutxuhaoresendl; return (it-second.weizhi!hang.que.end()); } //通过哈希表找到list中相应的迭代器保证list头插入该迭代器 void hitmod(int caozuo,int xuhao,cache_line hang){ auto ithang.xuhaozhi[xuhao].weizhi; hang.que.splice(hang.que.begin(),hang.que,it); if(hang.xuhaozhi[xuhao].dirty0caozuo1) hang.xuhaozhi[xuhao].dirty1; } void addnode(int caozuo,int xuhao,cache_line hang){ read(xuhao); hang.que.push_front(xuhao); auto ithang.que.begin(); hang.xuhaozhi[xuhao]{it,caozuo}; //coutxuhao (*it)endl; } int LRUvic(cache_line hang){ return *hang.que.rbegin(); } void delmod(int victim){ write(victim); } //忽略缓存单元旧的值把新的值放上去顺便换到队首 void delnode(int caozuo,int xuhao,int victim,cache_line hang){ read(xuhao); auto ithang.xuhaozhi[victim].weizhi; *itxuhao; //链表把删除的节点替换到最前面 hang.que.splice(hang.que.begin(),hang.que,it); //哈希表删除旧内存块索引更新新的内存块索引 hang.xuhaozhi.erase(victim); hang.xuhaozhi[xuhao]{it,caozuo}; } void solve(int caozuo,int xuhao,cache_line hang){ //coutcaozuo xuhaoendl; if(hit(xuhao,hang)) { hitmod(caozuo,xuhao,hang); return; } //load if((signed)hang.que.size()n){ addnode(caozuo,xuhao,hang); //coutaddnode caozuo xuhao (hang)endl; return; } //replace int victimLRUvic(hang);//返回队尾的内存块编号 //未命中满队列替换写回绝对要考虑脏位 //队列里绝对没有这个内存块 danyuan victhang.xuhaozhi[victim]; if(vict.dirty){ delmod(victim); } delnode(caozuo,xuhao,victim,hang); return; } int main(){ //freopen(1.in,r,stdin); ios_base::sync_with_stdio(0); cin.tie(0); scanf(%d %d %d,n,N,q); //试试模块化一步步来 //初始化一下 vectorcache_line zuxianglian(N); for (int i 0; i N; i) { zuxianglian[i].xuhaozhi.reserve(n * 2); // 提前分配足够桶 zuxianglian[i].xuhaozhi.max_load_factor(0.25); // 降低负载率减少碰撞 } for(int i1;iq;i){ int caozuo,xuhao;//操作 序号 scanf(%d %d,caozuo,xuhao); int formatxuhaoxuhao%(n*N); int gnformatxuhao/n; auto hangzuxianglian[gn]; //coutstart----- caozuo xuhaoendl; solve(caozuo,xuhao,hang); //out(hang); //coutcaozuo xuhao gnendl; } return 0; }非常奇怪不使用哈希表是90分用了哈希表也是90红黑树也是90Claude生成了双向链表和手搓哈希表加快读都没过非常奇怪不知道性能瓶颈在哪里。也构造了新的哈希函数避免哈希被卡。太奇怪了百思不得其解
