水平很次，成绩很差，没有拿到毕业证（差一门课学分要明年重修成功才能拿到），非本专业转码，无项目，找工作也晚，属于debuff拉满的底层人士。可能唯一好点就是学校牌子在这边比较好用（说起这点真是汗颜，高中的努力居然有这么长远的帮助，要说现在我感觉我根本不配这个牌子）。所以主要面的小厂。卓漫科技 2023.6.29第一次线下面试，机会由hr主动联系提供，面试岗位是算法工程师。我提前了20分钟到，到了以后给了份个人信息表和一些模型训练相关的问题（全都不会），这时已经感觉很不妙了。等了40分钟面试官才出现。由一个3,40岁天大的学长和hr共同面试，由于我人工智能一窍不通，很明显气氛很尴尬。学长看了我简历半天，问了我几个问题：1，c和c++有什么区别？答：c++是c的超集，c++好像还有面向对象特性，其他不知道。2，c和c++有哪些传值方式，有什么区别？答：不会。复盘：值传递，指针传递，引用传递。c没有引用传递。3，这个是c里面最基础的东西啊……这样吧，我再问问……（考虑一会）算了不问了，好像不太幸运没考到你会的啊。那讲讲你的故事吧，你擅长什么？答：（支吾）自学英文课程的计算机基础课，考了PAT，主要考试内容是数据结构。4，你讲那么多我可以概括说英语比较好是吧。答：嗯，大概是的……5，你学过的计算机专业课主要学了什么？答：数据结构和算法，链表啊，二叉树啊，迪杰斯特拉算法这些。6，介绍一下链表和跳表吧。答：链表就是一个个节点连接在一起，跳表不会。7，（沉默了一会）对我们有什么问题。问：您前面问的c和c++有什么区别……答：（打断）这个我们今天就不讨论技术了吧，主要是你对我们公司有没有什么问题……答：没有……8，你应该参加面试比较少吧，我给你个建议就是你要好好做好准备再来面试，至少你引导面试官问的东西你得会，不要这样挥霍机会了。9，hr问了一些问题，略。10，那就到这里吧，有消息我们会进一步通知你的。（结束了，20分钟不到）总结：面错岗位了，很难受。上来先给份人工智能的题，什么对什么参数有什么看法，有什么心得之类的，直接交白卷。面试官上来三板斧把我干懵了，我真的对c是一点也不会。传值方式我三种都用了无数遍了，但是我不知道它们具体叫什么……引导也有问题，数据结构与算法里面我比较自信的是dfs这块，链表跳表完全没复习。面试前重点突击c++语言特性继承多态封装一点没问。总的来说还是面错岗位了，气馁了一晚上。宇视科技 2023.6.30公司挺大挺正式的，做的是安保方面，有特别的保密要求背包不能带进办公区。应聘岗：前端一部嵌入式开发一面面试官三十岁左右，给我印象挺好的，给了份卷子，有几道题：1，写出下列数据类型占几个字节：char, int, short，如果在一个struct里，这个struct占几个字节.答：1,4,2,7复盘：7不对，应该是122，函数传值题3，简介strncpy和memcpy（不会）4，简单指针题做完以后，面试官说大概都是对的（指出了第一题7的错误，然后我想起来应该是最长端对齐）。做完以后问了点项目，因为我自己也没吃透我简历上的项目，总之就是一问三不知。唉……问题有：1.内存泄漏了解过吗。答：指针管理不当会内存泄漏复盘：内存泄漏（Memory Leak）是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。2.Linux有哪些操作？怎么删除文件夹？怎么编辑文档。答：ls列出文档，rm -rf，编辑我一般用vim。3.介绍一下你简历里面搭建的服务器，有什么功能。答：（支吾）利用socket，实现一个前端输入命令后端作简单反应的功能。4.介绍一下socket编程服务端和客户端有什么操作。复盘：然后让写个排序吧，随便哪种都行。很意外要写这个，很生疏，写了半天写了个冒泡，因为白纸写code又紧张又不习惯还把判断给漏了，最终也不知道代码写完有没有什么问题。面试官倒是也没说啥。很怪，这种题我平时正眼都不会看一眼的，居然卡得我这么狼狈。5.有什么问题吗？问：我看岗位上是前端一部，又是嵌入式开发，这个和前端有什么关系？答：我们做安保的。比如说监控摄像头，控制它转动，那部分代码就是前端负责的。问：网络编程在工作中有什么应用？答：摄像头数据流向后端传播要用到。二面面试官很拽。（问了一些学业方面的问题，以及pat是什么）1.写下反转链表。力扣有写过吧。答：力扣写过，原题不记得写没写过了。（写了很久，快写完时被打断了，说没时间）2.先序遍历是什么，写一下。（很快写完）3.给int a,b;把a的第二个字节赋值给b的第一个字节。b=(a>>8) & (0xFF)（0xFF那里原来写的是511，面试官说我看不懂你换种写法，然后答错了两遍才答对，忘记F是4个bit了）三面hr面，问了些职业规划，今后打算，期望薪资的问题，反问阶段我我问了些工作内容的问题。总结：很意外能不停进入下一轮，因为我觉得自己答得挺烂的。收获倒是有，经历了一次完整的面试流程，有点准备的方向了。九云物联 2023.7.220人小公司，老板是天大的。进去先带我去见hr，hr整个态度突出一个佛系，说了一下工作时间，然后对上班摸鱼也是毫不避讳，说你想干嘛就干嘛……接着老板带我去他办公室，然后开始抽烟（很猛，抽了半盒）泡茶讲故事，什么深圳合作什么什么的，讲了蛮久，等到另一个老板来了一问，数电模电没学过，才知道方向不一样。老板面露难色，但是还是说，你自己考虑考虑，真要入这行的话我们可以领你进门，毕竟学弟嘛结结善缘。但是会很辛苦，因为你差得有点多。公司开在天大下属一个产业园里，做的是给上游公司的业务提供方案的，薪资开得也不高。感觉这个小公司哪哪都很奇怪……天津普智芯 2023.7.4hr先了解了我的情况以后说明了劳动局规定没有毕业证不能签劳动合同，只能给到实习的岗位，一天100这样子。然后进入技术面环节，面试官过来看了看简历，从上到下认真看了，一点点问了都做了什么，然后说明了这家公司做芯片的，需要对数电模电有一定了解（而我完全是零基础）。面试官一直一脸笑容，给我印象非常好，我就多问了点个人发展方面的问题。对他说的几点我印象非常深刻，一个是做这个岗位要么你就是正统科班出身，学个差不多来应聘，像我这种放下本专业完全自学的，就会要求更高一点，必须做出点有特色能证明个人能力的东西，才能证明自己的竞争力。一个是公司在考虑招我的时候肯定是有顾虑的，因为我说不定还要投入时间精力去应付毕业的学分，这就不能保证你在工作上能保证质量。回想起来，说得确实是很中肯，我很感谢这位面试官给到我的视角。忠言逆耳，我心里也很不好受，确实我技术上就没什么积累，科班混混日子出来有学历背板，我真的是什么也没有，这怎么证明我是能干活的呢。这种两头不到岸的情况，应该是我态度有问题了。2024.7拿到毕业证了，面试计划重新启动！个人情况：试图考研二战，数学爆炸，后面摆烂半年。华为odboss 直聘上上传了简历，被华为 od 的人刷爆了，一天 4,5 条消息问这里工作机会看看吗，非常意外。联系了好几个部门的 hr，最终决定走车 bu 部门。还有另外一个华为欧拉的也很感兴趣，不过就不折腾了。2025.12.2补充：其实一开始一直都是欧拉部的在联系我。不过欧拉部的推流程不是很积极，我估计我的简历就在华子内部招聘里面挂着，然后被haoqing哥看到了，给我捞了一手。怎么捞的呢，就是一个电话打过来，先是问问我有没有兴趣来车bu，然后吹了一番前途无限，接着问我有没有什么疑虑，我说我面试不太有信心，haoqing哥直接手把手教我如何面试，怎么背八股，重点关注tcpip握手挥手一定要搞会（说实话我现在也不敢说自己很会，捂脸）。这就让我感觉haoqing哥很实在，这确实是做实事的部门，那就来吧。然后haoqing哥一推，马上流程就走起来了。机试 7.15机试前有个小坑。华为 od 同时有华为本部，外企德科，科锐的 hr 在做，尽量联系华为自己的 hr。我因为去年参加过 od 机考，简历锁科锐了，只能在这边走。说回机试，一共 3 题，前两题各 100 分，比较简单，忘了。第三题200 分，如下链接，通过 90% 样例然后超时了，我 pq 都用了偏偏没想到这是 dijkstra 算法，属实是太久没刷题生疏了（对，我就是裸考，半年没刷算法题了）。https://www.nowcoder.com/discuss/643390084632309760机试后还有个性格测试，懂得都懂，不谈。资格面试（hr面） 7.24确定一下意向城市和岗位，未来规划之类的。感觉设置这一面就是为了确认是个正常人……比较值得吐槽的是面试时间是晚8:20，加班.jpg。2025.12.2补充：面我的是影姐，听说我第五年摆烂了以后锐评了一番，认为我应该走秋招春招的流程，同时应该多面几家拿多一些offer，这样可以有更好的选择。其实现在想想她说得也对，不过我能力有限吧，那段时间只想着把考不过的化工流质与传热给考过去，远的真的没想了。技术一二面 7.26上午一面下午二面上午：1.自我介绍2.主要是对简历聊了聊，诸如做过什么项目，项目中遇到什么困难，如何克服之类的3.一个c++文件是如何运行的4.你对操作系统有什么理解（汗流浃背了）5.手撕：给两个数组arr1, arr2，arr2 数各不相同，arr1 包含 arr2 所有数，返回一个数组，使得 arr1 的数出现顺序按 arr2 的出现顺序排列，arr2 中没出现的数在尾部升序排列。（写了个时间 O(n2)空间 O(n)）追问：写得挺快啊（大概用了 5 分钟），有没有时间空间复杂度更好的办法下午：面试官开会，迟到半小时。but 面试官开了摄像头，胖胖的，感觉很好说话（事实上也确实如此）1.自我介绍2.读了 5 年怎么回事3.大学生计算机设计大赛是什么4.没问 pat，他好像是我这么多次面试唯一一次认识 pat 的（后面聊了聊才知道他是硕士，啊怪不得）5.手撕：用递归写斐波那契数列吐槽：没想到这么简单，给我整懵了，哎，偏偏还不熟。实在没思路了，想着暴力点吧参数全给我传进去，面试官当场打断：哈哈，你是不是 pat 动态规划做多了，不用这么写的，写递归吧。你试试把递推公式写出来。我还懵了会，感觉面试官比我还急，拼命给提示，就差帮我写了。后面写完我还想看看有没有问题，他直接就说对了不用看（笑哭）反问时间聊得比较长，面试官当场表示肯定给你过的不用担心，并且表示自己也是 od 转正。于是我就问了些转正的问题。面试完通知两场评价不一，要加面技术三面 7.29来了个 40 岁左右的面试官，非常专业，话不多说直接开问，答得好或者不好都没有任何表示。不过一开始答不出来的话会有提示引导，多少都能说点话。1.自我介绍2.进程线程有什么共同点3.对 cpu 来说进程线程有什么区别4.tcp 断链如何进行，为何要 4 次挥手5.socket 如何实现，socket 状态机有了解过吗6.一个文件从文字到运行经过哪些具体步骤7.一个可运行文件的数据结构是怎样的8.c++三大特性是什么9.多态如何实现10.内联会吗，有什么优缺点11.你说内联会复制代码，所有的东西都会复制吗12.malloc 和 new 有什么区别13.对 const 有什么理解14.const int *p 和 int const *p有什么区别15.二叉树的中序遍历是什么16.通过怎样的遍历可以还原出二叉树17.设计模式了解吗18.手撕：给 n 个站点，给个 n 阶邻接矩阵表示站点之间通路，求设置几个主站点可以覆盖所有站点。先说思路再做题。结束自评：寄。超级八股开启，感觉是一问三不知，手撕没见过邻接矩阵，半个小时只撕出来用例。邻接矩阵真蛋疼啊，我下次见到必先数据预处理，管你三七二十一先存图里先，艹。说实话面试的时候状态真不差的，但这和前两次面试相比强度也太大了（不过说实话这才是我觉得面试应有的样子）。唉。也就这样了。主管面 7.31（2025.12.2补充，后面的内容也都是今天补的了）jiaxi哥面的。没开摄像头，我感觉有点那个，不过我也是进来才知道这个部门发放办公用具不发摄像头，有的部门会发。不过也是来了才知道jiaxi哥挺帅挺年轻挺，儒雅，的。对，儒雅，就是这个词。现在回忆起来的话，也没聊啥特别的吧，就走个流程，jiaxi哥问我有啥要问的，我说前面几轮都问得差不多了。问了下工作节奏的事，我说我很不喜欢没事还要在公司硬坐的这种作风，jiaxi哥说没有的事，事干完就可以走了，没人强求的，进来也确实如此。但是事干不完才是比较经常的状态）定薪沟通 8.1~9科锐的HR和我沟通的，我哪知道我值什么价，随口报了个15k。最后是算上B绩效给14k。差不多得了，狮子大开口我也不太好意思，干就干吧。入职 8.29一入OD深似海~一不小心就接天莲叶无穷B了，man！前几个月和另一个OD聊天不小心聊到学历，知道我学历以后他大为震惊，问我为啥要来干OD，“你不应该一手一大把offer吗”。我能说啥呢，只能苦笑了~唉~
​A-1 Trap分数 20A robot is designed to move on a map from South toward North. When some obstacle is encountered, the robot can only turn toward West and moves until it can turn toward North and continue.Given a squared map with n×n blocks, a robot can start from any position below the bottom line (South) and its target is to reach the top line (North). (By the way, kindly remind you that the left-hand-side of the map is West and the right-hand-side is East.)If some obstacles are placed in the map, the robot might get trapped if it starts from certain positions and can never reach the North line. For example, in the situation given by the following figure, the robot will be trapped if it starts from either position 7 or 8.Your job is to point out those starting positions which will get the robot trapped.Note: it is assumed that a robot can move out of the map boundary, and all the blocks around the map are open, without any obstacle. Hence if the robot starts from any position out of the West or East boundary, it can certainly reach North without any problem. Therefore we only have to consider the positions between the West and East boundaries (e.g. the positions from 1 to 10 below the South line in the above figure). Besides, as long as the robot can reach the North line, it is considered successful even of it ends up at out of the boundary (e.g. the robot will have to move out of the map if starts from either the positions 1 or 2, but it can still reach the North line).Input Specification:Each input file contains one test case. Each case starts from a positive integer n (≤100) in a line, which is the size of the map. Then n lines follow, each contains n characters, which are either 0 for an open block, or 1 for a block with obstacle. The first line corresponds to the North boundary and the last line the South.Output Specification:Output in a line all the starting positions which can get the robot trapped, in increasing order. The positions are indexed from West to East, starting from 1. It is guaranteed that there is at least one output.All the numbers must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.Sample Input:10 0000000000 0000111010 1100100011 0000110001 0000000011 0000000000 0100000100 0001000000 0001000000 0001100000Sample Output:7 8题意：给个正方形的长为n的网格图，从第n+1行出发，能往北走往北走，不能往北走就往西走，直到能往北走为止。求从哪几列出发能到达第1行。网格图外所有地方可以到达。标签：模拟解析：难点在于题目很绕，不太好懂。由于只有往上往左两种走法，因此超出边界只可能是超出左边界，而一旦超出左边界，一定能到达最北端。所以一旦到达第一列即可返回true。#include <bits/stdc++.h> using namespace std; bool f(const vector<string>& g, int i, int j, int n) { if (i == 0 || j == 0) return 1; if (g[i-1][j] == '0') return f(g, i-1, j, n); else if (g[i][j-1] == '0') return f(g, i, j-1, n); return 0; } int main() { int n; cin >> n; vector<string> g(n+1, string(n, '0')); for (int i = 0; i < n; ++i) { cin >> g[i]; } bool b = 0; for (int j = 0; j < n; ++j) { if (!f(g, n, j, n)) { if (b == 1) cout<<' '; cout<<j+1; b=1; } } return 0; }A-2 Queue Using Two Stacks分数 25A queue (FIFO structure) can be implemented by two stacks (LIFO structure) in the following way:Start from two empty stacks s1 and s2When element e is enqueued, it is actually pushed onto s1When we are supposed to dequeue, s2 is checked first. If s2 is empty, everything in s1 will be transferred to s2 by popping from s1 and immediately pushing onto s2. Then we just pop from s2 -- the top element of s2 must be the first one to enter s1, thus is the first element that was enqueued.Assume that each operation of push or pop takes 1 unit of time. You job is to tell the time taken for each dequeue.Input Specification:Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^3 ), which are the number of operations. Then N lines follow, each gives an operation in the formatOperation Elementwhere Operation being I represents enqueue and O represents dequeue. For each I, Element is a positive integer that is no more than 10^6. No Element is given for O operations.It is guaranteed that there is at least one O operation.Output Specification:For each dequeue operation, print in a line the dequeued element and the unites of time taken to do this dequeue. The numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.In case that the queue is empty when dequeue is called, output in a line ERROR instead.Sample Input:10 I 20 I 32 O I 11 O O O I 100 I 66 OSample Output:20 5 32 1 11 3 ERROR 100 5题意：两个栈实现队列，并统计操作数。具体操作题目已给出。入队即push给s1，出队先检查s2是不是空，不是的话s2直接pop，是的话s1中元素一pop后马上push给s2，到s1为空为止，然后s2再pop。标签：栈，队列解析：模拟即可。#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; stack<int> s1, s2; for (int i = 0; i < n; ++i) { char op; cin >> op; if (op == 'I') { int ele; cin >> ele; s1.push(ele); } else { if (s1.empty() && s2.empty()) cout<<"ERROR"; else { if (!s2.empty()) { cout << s2.top() << ' ' << "1"; s2.pop(); } else { int cnt = s1.size() * 2 + 1; while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } cout << s2.top()<< ' ' << cnt; s2.pop(); } } if (i != n-1) cout<<endl; } } return 0; }A-3 Rank of Binary Tree分数 25Here we define the rank of a binary tree as n1×n2 /n0 where ni is the number of nodes of degree i for i=0,1,2.For example, given a tree shown by the figure, its rank is 2×3/4=1.5.Given the inorder and preorder traversal sequences of a binary tree, you are supposed to calculate its rank.Input Specification:Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.Output Specification:For each case, print in a line the way we calculate the rank, and the integer part of the rank. The format is:n1 * n2 / n0 = rankSample Input:9 2 3 1 5 4 7 8 6 9 1 2 3 6 7 4 5 8 9Sample Output:2 * 3 / 4 = 1题意：由前序和中序遍历构造二叉树，然后统计有1个孩子，2个孩子，0个孩子的节点有几个，按要求输出。标签：二叉树，前序遍历，中序遍历解析：由遍历构造树PAT不是第一次考了。这题思路是前序遍历中第一个节点必为根节点，在中序遍历中找到这一节点，其中序遍历数组左侧必为左子树，右侧必为右子树。对于左子树和右子树，可以用同样的方法处理，直到只有1个节点或节点为空，这就变成一个递归问题。事实上这是经典数据结构题，各大算法网站上都有，同类型题也能方便地找到，贴一个力扣的：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/统计孩子遍历一遍树即可。#include <bits/stdc++.h> using namespace std; int n0 = 0, n1 = 0, n2 = 0; unordered_map<int, int> idx; vector<int> in, pre; struct Node { Node *left, *right; int val; Node(int v){val = v;} }; Node* buildTree(int pl, int pr, int il, int ir) { if (pl > pr) return nullptr; int proot = pl; int iroot = idx[pre[proot]]; Node* root = new Node(pre[proot]); int slt = iroot - il;//size of left subtree root->left = buildTree(pl+1, pl+slt, il, iroot-1); root->right = buildTree(pl+slt+1, pr, iroot+1, ir); return root; } void nCounter(Node* node) { if (!node) return; if (!node->left && !node->right) { ++n0; return; } nCounter(node->left); nCounter(node->right); if (node->left) { if (node->right) { ++n2; } else {++n1;} } else if (node->right) { ++n1; } } int main() { int n; cin >> n; in.resize(n); pre.resize(n); for (int i = 0; i < n; ++i) cin >> in[i]; for (int i = 0; i < n; ++i) cin >> pre[i]; for (int i = 0; i < n; ++i) idx[in[i]] = i; auto root = buildTree(0, n-1, 0, n-1); nCounter(root); printf("%d * %d / %d = %d", n1, n2, n0, n1*n2/n0); return 0; }A-4 Big Number分数 30How to generate a big number of N digits randomly? One way is to find N kids, give each one a card with one's index written on one side (hence it is assumed that the kids are indexed from 1 to N), and ask them to write down a 1-digit number randomly on the other side. Then let the kids pin their digits in a line, on the wall, one by one in ascending order of their indices.However, it's very difficult to let hundreds of thousands of kids to follow the order. The result is that we have cards pinned randomly all over the wall, some even show the wrong sides. For example, if the 23rd kid has written down 8, we are supposed to find the number 8 on the wall. But instead we might find 23... Your job is to rearrange these cards so that we can obtain the big number as required.Input Specification:Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^5). Then N lines follow, each describes a card in the format n1 n2 where the two numbers are the numbers written on the two sides of a card.Output Specification:For each test case, print in a line the N-digit number as required. That is, print the digits written by the kids in ascending order of their indices. In case that there are 1-digit numbers written on both sides, it would be hard to tell which one is the index and which one is the number written by the kid. Hence the solution may not be unique. In this case, just output the smallest resulting number.It is guaranteed that a solution exists.Sample Input:12 7 11 8 9 3 1 2 12 4 6 10 0 5 1 2 5 6 8 1 4 7 2 9 3Sample Output:359114268072题意：有N组数，每组数有2个数，可能是下标也可能是数值（数值只能是0~9中一个），输出由这N组数表示的最小N位数。标签：贪心，深度优先搜索dfs解析：显然，对于一组数，只要出现2位以上的数，它就必定表示这一组数的数位，那么另一个数就是这一位的数值。因此，出现不同情况的只可能是下标为1到9的9组数。数据规模很小，所以算法的时间复杂度可以很奢侈。在这里我使用贪心，对每组的两个数哪个是下标哪个是数值，既然不知道，那就都试试。怎么试？建立数组tv存这9组数，借助dfs从1到9逐渐完善tv。每试完一组，用集合cap来记住这一组的信息已经用掉了，把它erase掉，用完的信息存入tv，进入下一层dfs。考试过程中看到27,28,29分的同学都有，这里给出我试出来的一个排查用例：2 1 2 1 2有个1分用例是两组中元素相同，如果输入时没有都记下来就会丢掉这1分。对于另一个2分的用例，可能是数据并没有10个以上，所以对10个以下的数据输出和dfs时做一些处理即可。还有前导0可能也有测试点，因为题目要求确切的n位数，所以不能有前导0.#include <bits/stdc++.h> using namespace std; int n; void dfs(int cur, vector<int>& tv, vector<int>& res, set<pair<int,int>>& cap) { //printf("\ndfs:cur=%d", cur); if (cur == 10 || cur > n) { res = min(res, tv); return; } for (int i = 0; i < 10; ++i) { if (cur==1&&i==0) continue; if (cap.count({cur, i})) { cap.erase({cur, i}); tv[cur] = i; dfs(cur+1, tv, res, cap); cap.emplace(cur, i); } if (cap.count({i, cur})) { cap.erase({i, cur}); tv[cur] = i; dfs(cur+1, tv, res, cap); cap.emplace(i, cur); } } } int main() { cin >> n; set<pair<int,int>> cap; vector<int> v(n+1);//storage: index >= 10 for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; if (a >= 10) { v[a] = b; } else if (b >= 10) { v[b] = a; } else { if (cap.count({a, b})) cap.emplace(b, a); else cap.emplace(a, b); } } vector<int> res(10, 0x3f3f3f3f); vector<int> tv(10, 0x3f3f3f3f);//temp vector dfs(1, tv, res, cap); for (int i = 1; i < 10 && i <= n; ++i) { cout<<res[i]; } for (int i = 10; i <= n; ++i) cout<<v[i]; return 0; }一点想说的话：我个人也是非常的菜，这是我第4次考PAT了，前3次不仅都没到60，而且还越考越低orz。PAT我完全是靠运气在考，因为出题人默认你知道数据结构和算法的一些知识点，比如前中后序遍历顺序，快速排序如何实现等等。此外，我还因为题目关键处出现生词寄过，也经常出现读题不仔细，做了一大半发现题读错了全部重来等等等等的问题。前3次的失败也是真的很难受，本来我就在很早之前就试过真题1小时全ac了，一直都是发挥不出来。而且题目分值很大，基本上一个读不懂，一个读错题，或者涉及到不会的知识点，那就是几十分几十分的掉，就算我自认为有8，90分水准，实际上打出来却总是4，50分的成绩。当然，这次运气真的很好，题目简单，而且恰好我都会。第一题读懂就很简单（不过读懂也是真不容易，我做了20来分钟还没拿满分，直接跳了，后面回来再看题才发现往西走不是到底的，而是一次一步），第二题更是啥都告诉你了照做就行，第三题leetcode原题做过（之前PAT也刚考过类似的，那次是中序和后序构建二叉树），第四题恰好是我最擅长的dfs，贪心那一步卡了思路，最后开考2小时达到97分时不会debug但是随手编了几个样例刚好发现了问题。最终离收卷还剩15分钟的时候达到了满分。还是很意外的吧，毕竟前面考那么烂，这次完全一点积极性也没有了，报名都是卡着截止前一天才报的，想着考6，70不错了，居然干满了，真的非常意外。不过这次心态也真有点不一样，开考前就感觉自己状态真的很好，也早早准备好了考场环境，带着数据结构的书重点看了看基础知识，重点备战了dijkstra算法（虽然完全没考）。开考后第一题有点绕，其实有点慌的，不过卡很久跳过以后看到2，3题，那真是狂喜，一看就知道我肯定会，起码能60分保底了。最后一题倒是一开始就想到10位以后不用管了，但是贪心思路有误，等纠正过来写出能拿部分样例的代码时已经剩下不到半小时了。当时心里就告诉自己一定要冷静，满分还是很有机会的，然后debug15分钟，最终是搞定了。实时排名大概看了几次，全程都是保持在20多30名，除了最后一题写出第一份代码前到了50名左右，但是写出以后又是27左右了。再然后，一发ac，噢！好兴奋，第一耶~开心地截了个图，然后复制一下题目，准备写写题解了。最后剩下的15分钟，没有直接退出考场，而是享受了一下胜利的喜悦，哈哈哈哈。真的很开心，不过可能也是太紧张了，考完以后傻了一天一夜，啥也没动力。几次考下来还对出题方向有点心得，pat最近考试的思路和甲级题集前几十道还是不太一样，第2,3题像图书管理系统那种设计struct的题型变少了几乎没考过（一般在中间两题），树很喜欢考几乎从不缺席（一般不在第一题），最短路径也常考但比树少（一般在后两题），纯coding的模拟题每次必有（一般在前两题）。第一题一般是模拟，字符串或者最小公因数之类简单算法。二三题一般是经典数据结构。第四题上难度的方式就3种，一种是上图相关题拉起代码量；一种是类似这次考考思维，想明白就很简单；一种是考点高级些的数据结构，比如平衡BST，并查集。最后，给还在努力刷甲级的朋友们两个推荐：PAT甲级题【真题】全讲解 (Advanced Level) Practice_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Mt4y197kCGitHub - liuchuo/PAT: https://github.com/liuchuo/PAT
速查常用vim命令https://vimhelp.org/:w save:x :wq save and quit:q! quit not save/string find "string", use n/N to find next/previous one:{作用范围}s/{目标}/{替换}/{替换的标志} 作用范围：%所有行第一次，'<,'>可视范围 替换标志：i 大小写不敏感，I 大小写敏感，g全局 h左 j下 k上 l右 yycopy line p paste u undo ctrl + r redo
2023还是不会的数据结构与算法题集结
我的力扣主页：https://leetcode.cn/u/cutesnake/我的PAT仓库：https://github.com/suchacutesnake/pat2023.1.1然而竞赛积分还是掉了1分……做太慢也不行吗……2023.1.6花了很多时间，还是好菜，难受~~PAT 1064 Complete Binary Search Treehttps://pintia.cn/problem-sets/994805342720868352/exam/problems/994805407749357568难点：1.对于以层序遍历数组表示的树，如何进行各种遍历。2.对BST，中序（左根右）遍历结果是递增的。3.对CBST的某一节点i，其左右子树分别表示为2i，2i+1。Leetcode 1803. Count Pairs With XOR in a Range (hard)https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/字典树。答案都看不懂，可以竞争我遇到过最难的力扣题。倒不是不明白字典树这个数据结构，就是想不明白为什么要用字典树？？？有没有人来教教我啊~~~2023.1.9Leetcode 6306. Time to Cross a Bridge (hard)https://leetcode.cn/problems/time-to-cross-a-bridge/周赛327场的hard，比起力扣感觉更像PAT的题目，涉及很繁琐的数据结构设计。周赛做完T3只剩10分钟了，时间不够就没做。这种复杂的模拟题对大家来说原来都很困难，头一次见到周赛接近半小时大佬们才全通的。2023.1.11Leetcode753. Cracking the Safe(hard)https://leetcode.cn/problems/cracking-the-safe/初见欧拉回路题，只能看答案。算法看明白了，但是代码实现是怎么做到的看不明白……2023.1.14Leetcode 1819. Number of Different Subsequences GCDs (H)https://leetcode.cn/problems/number-of-different-subsequences-gcds/比较有趣的暴力枚举，杂了一点数学2023.1.16题外话，前几天折腾xray，第一次GitHub上交了pull request，秒merge了，还挺兴奋的。2023.1.18Finding MK Average (H)https://leetcode.cn/problems/finding-mk-average/很多讨论的有序集合+队列题， 奋斗数小时后tle，耻辱看答案。不是自己写的代码真的不想cv提交啊，这每日一题打卡不打也罢！明明就是不会嘛，不会的题却显示通过给一种自欺欺人的感觉……评论区acm爷普遍用的树状数组，我什么时候能学学这个数据结构啊……2023.3.23https://leetcode.cn/problems/word-ladder-ii/solution/dan-ci-jie-long-ii-by-leetcode-solution/要做吐了，错了一遍又一遍，到后面几乎和题解一模一样的写法就差cv了，还是超时。时间复杂度肯定是一样的，卡剪枝了，好难受啊真的好难受。错误的代码先贴着。class Solution { public: void backtrack(unordered_map<string, unordered_set<string>>& from, vector<vector<string>>& res, vector<string>& cur, string beginWord) { for (auto& next : from[cur.back()]) { cur.emplace_back(next); if (next == beginWord) { res.emplace_back(cur); reverse(res.back().begin(), res.back().end()); } backtrack(from, res, cur, beginWord); cur.pop_back(); } } vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict({wordList.begin(), wordList.end()}); unordered_map<string, int> steps; unordered_map<string, unordered_set<string>> from; queue<string> q; vector<vector<string>> res; int ansSize = 0x3f3f3f3f; if (dict.find(endWord) == dict.end()) return res; q.emplace(beginWord); steps[beginWord] = 1; int step = 1; while (!q.empty()) { step++; int n = q.size(); for (int j = 0; j < n; ++j) { string s = move(q.front()); string ss = s; q.pop(); for (char& ch : s) { char temp = ch; for (int i = 0; i < 26; ++i) { ch = i + 'a'; if (ch == temp || !dict.count(s) || (steps.count(s) && steps[s] < step)) continue; steps[s] = step; from[s].emplace(ss); if (s == endWord) { break; } q.emplace(s); } ch = temp; } } } vector<string> cur({endWord}); backtrack(from, res, cur, beginWord); return res; } };
我的力扣主页：https://leetcode-cn.com/u/cutesnake/4.20388中等https://leetcode-cn.com/problems/longest-absolute-file-path/乍一看简单，仔细一想不会做。本来想用遍历，看了答案知道用哈希表，但还是太难办，写了一个小时，wa一次，有点理解屎山是如何堆成的了……class Solution { public: int lengthLongestPath(string input) { int res = 0, curLen = 0, subCnt = 0, n = input.size(); bool isFile = 0; unordered_map<int, int> subNum; for (int i = 0; i < n; ++i) { char& ch = input[i]; if (ch == '\n') { isFile = 0; subNum[subCnt] = curLen; subCnt = 0; continue; } if (ch == '\t') { ++subCnt; } else { if (i && (input[i-1] == '\t' || (input[i-1] == '\n' && subCnt == 0))) curLen = subNum[subCnt-1]; if (ch == '.') isFile = 1; ++curLen; if (isFile) res = max(res, curLen + subCnt); } } return res; } };
2021-11-20 20:18:09 星期六发现我真的是不会c语言……就连最简单的字符串比较都不会，还要上网去查才知道有strcmp这个函数……在对各种c库函数一无所知的情况下，感觉要实现些什么真的举步维艰啊……不过，也真的觉得这次的lab不是很难（可能经过了pat三十多道题的洗礼有进步了），就愈发想要自己独立完成。然而，越是有这样的心，就越在简单的地方（指知识性的地方，了解过就几行搞定，没了解过就卡住的地方）就进行不下去了，到底还是水平太次了orz2021-11-20 22:31:11 星期六看了一下博客，完全是一点也不懂……太硬了，英文课本也看不懂，什么时候才能学下来啊……2021-11-22 20:49:51 星期一一个坑：需要到http://csapp.cs.cmu.edu/3e/code.html 把csapp.h的代码复制然后include进来。开始有点明白了。按着16个trace一步一步走就行。前3个trace照抄课堂上课件的代码即可。![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-22 at 8.48.55 PM.jpg)到trace05卡住了。理论上./myspin 2 & 和./myspin 3 &所分配到的jid应该是1和2，但我这里是2和4。2021-11-26 15:41:05 星期五是2和4的原因在于没有waitfg。把waitfg函数完成即可。2021-11-26 13:20:07 星期五错误：![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-26 at 1.50.14 PM.jpg)Makefile里加上CFLAGS = -Wall -O2 -pthread#include "csapp.h"然后把tsh.c里重复定义的代码都注释掉。test07：信号掩蔽exit总是会把主函数return掉，想要杀掉进程而不退出tsh，用kill。csapp.c里面的Kill支持不了-pid参数，只能用kill。在sigint_handler里用了exit(0)的话，会有以下结果（上面是我的输出，下面是参考输出）：![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-26 at 3.46.22 PM.jpg)如果不掩蔽，则前后台的process都会terminate掉。2021-11-27 12:45:43 星期六![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-27 at 12.46.59 PM.jpg)对test08的jobs命令显示不了Stopped的进程：1，在waitfg里面的waitpid用上WUNTRACED这个option，使得一旦有子进程terminate或者stop都会被watipid捕捉到，再通过WIFSTOPPED(status)（图中用的WIFEXITED，会过不了test07）进行判断，把stopped掉的进程状态设置为ST。![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-27 at 12.53.39 PM.jpg)2，对应handout PDF的Hints最后一条，在合适的位置加上setpgid(0, 0)，使得后台的进程一定拥有一个独立的进程组。2022-01-23 19:40:50 星期日放假了十几天了，捡回来接着做。发现之前直到test09的输出结果都是没问题的，但是进程回收一块完全是一塌糊涂，根本没做，导致所有进程就算结束了也还会在jobs命令下有所显示。还得再看看书。
题目集网址：https://pintia.cn/problem-sets/994805342720868352/problems/type/7我的代码网址，附尽量详细的英文注释：https://github.com/suchacutesnake/pat2021-11-16 16:44:21 星期二这两天饭也吃不香，觉也睡不好，都是因为这道傻逼题目（指1026），也不讲讲清楚，就tm纯靠猜是吧![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-16 at 4.40.48 PM.jpg)做一题8小时，真心累，这题目多少有点大病。我还以为我代码有问题，结果网上一搜才知道全是题目没讲清楚的地方case不过，我真的是醉了，我写的代码从一开始就一点问题都没有……这考的是编程能力还是猜出题人意思的能力？2021-11-21 21:28:59 星期日今天打算19:30~21:30做个pat甲级的模拟考，正好1035~1038的分值加起来是100.结果我93分钟就全ac了，前3题每题都刚好只用13分钟。太兴奋了，信心一下就来了，我直接膨胀起来了。今早力扣周赛只做出两题的阴霾一扫而光，我甚至开始考虑是否在今年12月9日前报名12月19日的pat甲级测试了。2021-11-23 19:09:13 星期二今天模拟了2020春季的PAT真题，得分83/100，排名396/1588。还挺失望的。比较有趣的是我模拟考时正好赶上服务器迁移，看不到实时排名，最后钱就退回给我了，相当于我白嫖了一次考试。![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-23 at 7.10.56 PM.jpg)本来在用Windows考试的，结果vs2019一个更新以后直接开机五分钟必卡崩，只好切回Mac，这里大概浪费了半个小时。真气死我了。这里心态就已经不太好了。或许开考前认真一点做好准备会有更好的结果吧。这次考试一三题ac了，第二题tle，第四题两个tle一个wa。考试过程中我以为会有更高端的算法，就想到别处去了。结果看了看别人的解析，我的想法是没问题，但第二题是没用数组存路径导致速度慢了，第四题则至今不明白哪里有问题。两个题都是模拟，我恨模拟！上周力扣周赛也是第二题模拟卡了我50分钟，直接后面就没时间思考了。感觉今年冬季PAT可以一战，高分应该没问题，满分就看运气了。2021-11-25 20:11:19 星期四昨晚做了套真题，才47分，排名985/2701，直接锐气都没了。今晚又花了一小时做了https://pintia.cn/problem-sets/1263308065769611264 PAT 520 钻石争霸赛真题（2020-05-20），结果得分55/120，排名1351/7951，直接自信给干崩溃了。。。其实要说我真不会吗，倒不是，问题就在于很难一次写出bug-free的代码，浪费时间太多了。也许以后做题要开始限时了，把熟练度提上来。我还是很缺练习，自己之前对自己的定位或许过高了。
不知道为什么这篇文章的图片全部显示不出来了……2022.4.20更新：换阿里云OSS以后全都没问题了。高分子化学也低分飘过，及格万岁！笔记懒得补了。1 绪论2 缩聚与逐步聚合![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-09 at 7.05.34 PM.jpg)![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-09 at 7.05.58 PM.jpg)3 自由基聚合![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-09 at 7.03.05 PM.jpg)4 自由基共聚合![](https://cutesnaketop.oss-cn-beijing.aliyuncs.com/image/gitee-img/Screen Shot 2021-11-09 at 7.04.55 PM.jpg)
part A2021-09-23 22:18:42 星期四#include <stdio.h> //printf() #include <time.h> //clock_t #include <stdlib.h> //atoi() #include <getopt.h> //getopt() #include "cachelab.h" typedef struct { unsigned tag; /* tag bits per line */ _Bool valid; /* 1 valid bit per line */ clock_t stamp; /* time stamp, to implement LRU algorithm */ }cache_line; cache_line** init_cache(int s, int E) { /* cache size = S(=2^s sets per cache) * E(lines per set) * B(=2^b bytes per block) * we use cache_line_size here instead of B */ int sets_cnt = 1<<s, cache_line_size = sizeof(cache_line); /* cache_line** cache is a two dimensional array, and cache[i] means * the ith set in the cache. */ cache_line** cache = (cache_line**) malloc(cache_line_size * sets_cnt); for(int i = 0; i < sets_cnt; ++i) { int set_size = cache_line_size * E; //initial the ith set cache[i] = (cache_line*) malloc(set_size); //the for loop can be replaced by //memset(cache[i], 0, set_size) //#include <string.h> for(int j = 0; j < E; ++j) { cache[i][j].tag = 0; cache[i][j].valid = 0; cache[i][j].stamp = 0; } } return cache; } void free_cache(cache_line** cache, int s) { int sets_cnt = 1<<s; for(int i = 0; i < sets_cnt; ++i) { free(cache[i]); } free(cache); } _Bool set_insert(cache_line* set, unsigned long tag, int E) { int old_stamp_index = 0; for(int i = 0; i < E; ++i) { if(set[i].stamp < set[old_stamp_index].stamp) old_stamp_index = i; if(!set[i].valid) { set[i].valid = 1; set[i].tag = tag; set[i].stamp = clock(); return 0; } } //all lines valid, evict the Least-Recent-Used set[old_stamp_index].tag = tag; set[old_stamp_index].stamp = clock(); return 1; } //hit=1, miss=0 _Bool set_inspect(cache_line* set, unsigned tag, int E) { for(int i = 0; i < E; ++i) { if(set[i].valid && set[i].tag == tag) { //hit, renew time stamp set[i].stamp = clock(); return 1; } } //miss return 0; } void cache_simulate(cache_line** cache, char type, unsigned address, int bytes, int s, int E, int b, int v, int* hits, int* misses, int* evictions) { //address = tag + set index + block offset //unsigned int has 32 bits unsigned tag = address>>s>>b, set_index = address<<(32-b-s)>>(32-s); cache_line* set = cache[set_index]; _Bool hit_or_not = set_inspect(set, tag, E), eviction_or_not = 0; if(!hit_or_not) { eviction_or_not = set_insert(set, tag, E); } //print detailed info if(v) { printf("%c %x,%d", type, address, bytes); if(hit_or_not) { printf(" hit"); } else { if(eviction_or_not) printf(" eviction"); printf(" miss"); } if(type == 'M') printf(" hit"); printf("\n"); } //summary if(type == 'M') ++*hits; if(hit_or_not) ++*hits; else ++*misses; if(eviction_or_not) ++*evictions; } void print_usage(){ printf( "Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n" "Options\n" " -h Print this help message.\n" " -v Optional verbose flag.\n" " -s <num>: Number of set index bits.\n" " -E <num>: Number of lines per set.\n" " -b <num>: Number of block offset bits.\n" " -t <file>: Trace file.\n" "\n" "Exampes:\n" " linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n" " linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n" ); } int main(int argc, char** argv) { //no arg if(argc == 1) { printf("./csim-ref: Missing required command line argument\n"); print_usage(); return 0; } /* access command line */ int s, E, b, v = 0; char ch; char* file_path; while((ch = getopt(argc, argv, "s:E:b:t:vh")) != -1) { switch(ch) { case 's': s = atoi(optarg); break; case 'E': E = atoi(optarg); break; case 'b': b = atoi(optarg); break; case 't': file_path = optarg; break; case 'v': v = 1; break; case 'h': print_usage(); return 0; default: break; } } //initialize cache cache_line** cache = init_cache(s, E); //open file FILE* fp = fopen(file_path, "r");//r: read only if(!fp) { printf("%s: No such file or directory\n", file_path); return 1; } //file format: S 7ff000398,8 /* read file */ char type; unsigned address; int bytes, hits = 0, misses = 0, evictions = 0; while(fscanf(fp, " %c %x,%d", &type, &address, &bytes) != EOF) { if(type == 'I') continue; //enter core function cache_simulate(cache, type, address, bytes, s, E, b, v, &hits, &misses, &evictions); } fclose(fp); printSummary(hits, misses, evictions); free_cache(cache, s); return 0; }运行结果：root@bb0b19885c0d:/cmu15-213/cachelab-handout# ./test-csim Your simulator Reference simulator Points (s,E,b) Hits Misses Evicts Hits Misses Evicts 3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace 3 (4,2,4) 6 5 2 6 5 2 traces/yi.trace 3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace 3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace 3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace 3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace 3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace 6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace 27 TEST_CSIM_RESULTS=27历时21.5h，做完Part A: Writing a Cache Simulator。我知道这速度真的超慢，更何况我基本都是抄的zero4drift。但是，不看答案我是真的没头绪，里面用到的巨多c库函数我都一无所知，Linux基础知识我也没有（比如说main()里面的argc和argv给了命令行参数处理的基本途径，你让我自己去想真的是无从下手）。我是先看书，想明白这个题目大概要我干什么之后，去别人代码里看架构，然后尽量自己写，写到不会的地方就参考。结果就是架构基本和别人一模一样，不过这也没办法，他真的写得太好了，好几个地方我自己想办法结果代码又臭又长，只好又采用回他的架构。最终我的代码和参考代码区别几乎就只在于我的变量名、变量引入的地方不一样、以及加了很多注释。没办法，他的代码真的写得太好了。本来如果只要求test-sim得满分的话，输入输出那里可以省很多步（参考周小伦），但zero4drift方方面面都照顾到了，真的和csim-ref一模一样的功能，我真的好佩服好佩服。这部分主要学习了c库函数等构件基本小工程的技巧。非常有收获。2021-09-28 21:24:00 星期二草，在看part B要求的时候才看到part A那里文档里说了推荐用getopt.h等头文件，再次吃了不看文档的亏。唉，都多少次了。part B2021-10-04 14:30:30 星期一为什么A和B对角线上元素会冲突？A[0][0]地址为0x0030b120,B[0][0]地址为0x0034b120。对于A[n][n]和B[n][n]而言，由于起始地址的后10位（二进制）一样，对应到cache里面就是set index和offset一样，只有tag不一。因此，对角线上的元素进行替换时，会在同一个set里面更新tag，即发生miss eviction。对非对角线上元素而言，在A中的offset与在B中的offset肯定是不一样的，就不会冲突。对第一个问题，32x32矩阵，采取8x8分块可使misses大幅下降，但由于对角线冲突问题还拿不到满分。此时每一个对角线分块有37个miss，非对角线上分块有16个miss（两个8行），计算应该有37x4+16x12=340次miss，实际的343次miss多出的3次大概源自循环变量。char trans_my[] = "my test funcion"; void trans_my_function(int M, int N, int A[N][M], int B[M][N]) { //set chunk for (int ii = 0; ii < N; ii += 8) { for (int jj = 0; jj < M; jj += 8) { //inside chunk for (int i = ii; i < ii + 8; ++i) { for (int j = jj; j < jj + 8; ++j) { A[i][j] = B[j][i]; } } } } }Function 4 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 4 (my test funcion): hits:1710, misses:343, evictions:311以下是为什么对角线分块上有37个miss：缓存中的内容 : +-----------------------+-------------------+ | opt | cache | +-----------------------+-------------------+ |before B[0][0]=tmp | A[0] |---+ +-----------------------+-------------------+ | |after B[0][0]=tmp | B[0] | | +-----------------------+-------------------+ | A 的第一行复制到 B 的第一列 . |after tmp=A[0][1] | A[0] | | 最终缓存中剩下 A[0], B[1]...B[7]. +-----------------------+-------------------+ +--> A[0]被两次加载进入内存 , |after B[1][0]=tmp | A[0] B[1] | | 总的 miss 次数是 10. +-----------------------+-------------------+ | |... | | | +-----------------------+-------------------+ | |after B[7][0]=tmp | A[0] B[1..7] |---+ +-----------------------+-------------------+ |after B[0][1]=tmp | A[1] B[0] B[2..7] |---+ +-----------------------+-------------------+ | A 的第二行复制到 B 的的二列 . |after B[1][1]=tmp | B[0..7] | | 其中发生的 miss 有 : +-----------------------+-------------------+ +--> A[0], B[0], A[1]与 B[1]的相互取代 . |after B[2][1]=tmp | A[1] B[0] B[2..7] | | 总的 miss 次数为 4. +-----------------------+-------------------+ | |... | | | +-----------------------+-------------------+ | |after B[7][1]=tmp | A[1] B[0] B[2..] |---+ +-----------------------+-------------------+ 之后的三至七行与第二行类似 , |... | |------> miss 的次数都是 4. +-----------------------+-------------------+ |after tmp=A[7][7] | A[7] B[0..6] |---+ 最后一行 A[7]被 A[8]取代后 , +-----------------------+-------------------+ +--> 不需要重新加载 . |after B[7][7]=tmp | B[0..7] |---+ 总的 miss 数为 3. +-----------------------+-------------------+ 所以对角块上的总的 miss 次数是 10+4*6+3=37.解决32x32矩阵对角线冲突问题，可以使用变量，一次存好一行，再一次读取一列。这样可以在对角线上的分块中miss次数降至23。char trans_32_32[] = "32-32 transpose"; void trans_32_32_function(int M, int N, int A[N][M], int B[M][N]) { int a[8]; //set chunk for (int ii = 0; ii < N; ii += 8) { for (int jj = 0; jj < M; jj += 8) { //inside chunk for (int j = jj; j < jj + 8; ++j) { for (int i = ii; i < ii + 8; ++i) { a[i-ii] = A[i][j]; } for (int i = ii; i < ii + 8; ++i) { B[j][i] = a[i-ii]; } } } } }Function 1 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 1 (32-32 transpose): hits:1766, misses:289, evictions:257这样part A miss次数低于300，得到了满分。为什么64x64矩阵进行8x8分块时比32x32矩阵多了那么多miss？由b=5，2的5次方为32，意味着cache set的data block里可以装32个Byte，即8个int（1个int需要4个Byte）。对于32x32矩阵，如果进行8行8列的分块，对单独一行的8列的int数据全部可以装进一个set中。一行共32列，装4个set，共32行，综合起来就是4x8=32个set，cache刚好能装下（s=5，2的五次方为32）。而对于64x64矩阵，共64列，一行装8个set。如果依然进行8x8分块，则前4行已经将cache填满，需要对后4行进行存取操作的时候，势必会将前面已经装好的某些数据弹出，造成非常多的miss。事实上，64x64的8x8分块和完全不进行分块的内存效率是一样的：char trans_my[] = "my test funcion"; void trans_my_function(int M, int N, int A[N][M], int B[M][N]) { //set chunk for (int ii = 0; ii < N; ii += 4) { for (int jj = 0; jj < M; jj += 4) { //inside chunk for (int i = ii; i < ii + 4; ++i) { for (int j = jj; j < jj + 4; ++j) { A[i][j] = B[j][i]; } } } } } char trans_desc[] = "Simple row-wise scan transpose"; void trans(int M, int N, int A[N][M], int B[M][N]) { int i, j, tmp; for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { tmp = A[i][j]; B[j][i] = tmp; } } }Function 4 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 4 (my test funcion): hits:3474, misses:4723, evictions:4691 Function 5 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 5 (Simple row-wise scan transpose): hits:3474, misses:4723, evictions:4691解决方法：将分块改为4x4。这样set是没装满的，非常浪费，但足以拿到不是0分的分数了，miss=1891（miss小于2000）char trans_my[] = "my test funcion"; void trans_my_function(int M, int N, int A[N][M], int B[M][N]) { //set chunk for (int ii = 0; ii < N; ii += 4) { for (int jj = 0; jj < M; jj += 4) { //inside chunk for (int i = ii; i < ii + 4; ++i) { for (int j = jj; j < jj + 4; ++j) { A[i][j] = B[j][i]; } } } } }Function 4 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 4 (my test funcion): hits:6306, misses:1891, evictions:1859如果用上32x32相同的策略来消除对角线冲突（即使用变量一次读好一行，再一次存好一列），可以进一步降低misses至1653char trans_64_64[] = "64-64 transpose"; void trans_64_64_function(int M, int N, int A[N][M], int B[M][N]) { int a[8]; //set chunk for (int ii = 0; ii < N; ii += 4) { for (int jj = 0; jj < M; jj += 4) { //inside chunk for (int j = jj; j < jj + 4; ++j) { for (int i = ii; i < ii + 4; ++i) { a[i-ii] = A[i][j]; } for (int i = ii; i < ii + 4; ++i) { B[j][i] = a[i-ii]; } } } } }Function 2 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 2 (64-64 transpose): hits:6546, misses:1653, evictions:16213最后61x64矩阵，跟32x32的思路一样的，多试试分块策略就完事了。char trans_61_67[] = "61-67 transpose"; void trans_61_67_function(int M, int N, int A[N][M], int B[M][N]) { for (int ii = 0; ii < N; ii += 24) { for (int jj = 0; jj < M; jj += 8) { for (int i = ii; i < ii + 24 && i < N; ++i) { for (int j = jj; j < jj + 8 && j < M; ++j) { B[j][i] = A[i][j]; } } } } }Function 3 (6 total) Step 1: Validating and generating memory traces Step 2: Evaluating performance (s=5, E=1, b=5) func 3 (61-67 transpose): hits:6282, misses:1897, evictions:1865成绩python2.7 ./driver.pyPart A: Testing cache simulator Running ./test-csim Your simulator Reference simulator Points (s,E,b) Hits Misses Evicts Hits Misses Evicts 3 (1,1,1) 9 8 6 9 8 6 traces/yi2.trace 3 (4,2,4) 6 5 2 6 5 2 traces/yi.trace 3 (2,1,4) 2 3 1 2 3 1 traces/dave.trace 3 (2,1,3) 167 71 67 167 71 67 traces/trans.trace 3 (2,2,3) 201 37 29 201 37 29 traces/trans.trace 3 (2,4,3) 212 26 10 212 26 10 traces/trans.trace 3 (5,1,5) 231 7 0 231 7 0 traces/trans.trace 6 (5,1,5) 265189 21775 21743 265189 21775 21743 traces/long.trace 27 Part B: Testing transpose function Running ./test-trans -M 32 -N 32 Running ./test-trans -M 64 -N 64 Running ./test-trans -M 61 -N 67 Cache Lab summary: Points Max pts Misses Csim correctness 27.0 27 Trans perf 32x32 8.0 8 289 Trans perf 64x64 4.0 8 1653 Trans perf 61x67 10.0 10 1897 Total points 49.0 53最后64x64矩阵转置部分还没能拿到满分，这里有个非常好的文章（因为它带图，而且步骤分解清晰，讲得比很多人都清楚）https://zhuanlan.zhihu.com/p/387662272 ，但对于我来说还是太难懂了。思路是大概明白了，可实在不想自己把代码实现一遍了。总结cachelab算上看书和做lab，一共花了38个小时。一路上的每一个问题，我自己独立做出来的意愿都是非常强的，但实在顶不住水平太次，徘徊半天才摸到门道，还是只能看别人的博客才能明白，明白以后还是写不出来代码，又变成抄抄乐。到最后，还留着看了博客也不能解决的地方……part B非常困难，我在其中意识到我对地址的某些概念还不清晰，常常绕着绕着就绕不出来了。由于中途对cache的构成有一丝不明晰：offset由多个bit组成，指向data block里面的确切地址的starting Byte，这一点没有搞明白，浪费了好几个小时。巩固了Linux和docker的操作，初步认识valgrind内存管理工具。
1 传质过程基础费克第一定律，传质微分方程（略），做题：求摩尔通量，摩尔平均速度，质量通量，扩散通量典型题其中，质量衡算方程相等两边分别是从左向右积分和从管壁向中心积分。2 气体吸收气膜阻力/总阻力=(1/KG)/(1/kG)2021-10-22 15:40:27 星期五2021-10-23 20:00:04 星期六