Posts

Lab用时：13小时 注：6.824 在2022年春季添加了一个新的jobcount test，但由于我看不懂这个测试代码。经我测试，本文的程序能通过2021年的所有test cases，但是2022年的测试会jobcount test FAIL 实验分析 用Go实现MapReduce的Coordinator(Master)和Worker程序。MapReduce程序模型见下图，paper和Lecture中讲的非常详细，不再过多介绍。 结构设计 RPC 首先是RPC参数的设计，定义一个Task结构体，Coordinator应该根据Task来维护整个MapReduce的状态和进度，Worker也应该能从Task中获取到足够的数据进行Map和Reduce type Task struct { TaskNum int // task编号 TaskType int // map: 1, reduce: 2, taskAllDone: 3 FName string // 待读取的文件名称 NMap int // map tasks数量 NReduce int // reduce tasks数量，MapReduce结束之后要生成NReduce个output files } Coordinator Coordinator要用一个mutex锁来原子化更改和读取它的字段，防止发生race，以此保证MapReduce进程的状态和进度正确。 type Coordinator struct { mu sync.Mutex state int // mapping: 1, reducing: 2, allDone: 3 nMap int // map tasks数量 mTasks []mapTask // map tasks状态数组 mapDoneCount int // 已完成的map tasks数量 nReduce int // reduce tasks数量 rTasks []reduceTask // reduce tasks状态数组 reduceDoneCount int // 已完成的reduce tasks数量 } type mapTask struct { fName string // Worker执行Map时读取的文件名 state int // map task状态 beginTime time....

疑问 今天在做剑指 Offer 34. 二叉树中和为某一值的路径这道题目时，我一开始写出了如下的代码： func pathSum(root *TreeNode, target int) (ans [][]int) { var dfs func(node *TreeNode, sum int, vals []int) dfs = func(node *TreeNode, sum int, vals []int) { // fmt.Printf("ptr:%p, val:%v\n", vals, vals) if node != nil { vals = append(vals, node.Val) sum += node.Val // if leaf node and sum is equal to target if node.Left == nil && node.Right == nil && sum == target { // fmt....

起因 我在读李笑来老师的《把时间当作朋友》时，了解到了前苏联科学家柳比歇夫和他的“时间记录法”，我还特意去读了写柳比歇夫的传记《奇特的一生》。虽然这本书的内容大多是传记作者对柳比歇夫的鼓吹，没有什么价值，我也没有读完，但是书中提到的柳比歇夫使用的“时间记录法”给我留下了很深刻的印象。在网上查阅了足够的资料后，我认为这个方法有非常高的实用价值，也刚好和我“想把生活中的很多方面数据化”的想法不谋而合，于是我就开始使用这个方法了。 执行 大体上来讲，“时间记录法”是把自己每天做的有价值的事情和做这些事消耗的时间给记录下来，每月、季、年可以分析一下自己做了哪些事情、自己近期学习状态如何等等。这给我们生活、学习的规划和分析在时间方面上提供了数据支持，让我们可以刨除自己不准确的“感觉”，用科学、严谨的方式来剖析自我，再而改善自己的学习、生活质量。 对于“所做的事情是否有价值”，人人都有自己的概念，对我来说，我把我认为有价值的时间简要分为两类： I 类时间：专注、认真地学习系统性、体系性、可繁殖性的知识 做某个课程的代码实验 写 LeetCode 算法题 读各种类型的有价值的书（网文不算） 写文章、做记录 II 类时间：也是在做有价值的事情，但是给个人带来的能力提升要低于 I 类时间 配置一下终端、代码编辑器、服务器环境 学学某个软件或工具的使用 看几篇篇幅短的、碎片式的好文章或博客 看一个有启发意义的好电影、纪录片、人物访谈等 我平日会耗费大量的 II 类时间，为了激励我多做 I 类时间对应的事情，我刻意弱化了 II 类时间的价值，所以在实际的执行中，我只认真记录了 I 类时间，几乎没有记录 II 类时间。案例如下： 分析 数据一：每日平均 I 类时间很低 先看一下从开始记录(2022-02-10)到今天(2022-05-09)为止的总体时间记录： 在这里，II 类时间的记录不具备参考价值，我们只看 I 类时间的记录，在这总计 89 天的时间内，我记录了 81 天，遗漏了 8 天(大概是这 8 天内没有做任何有价值的事情)。 不算不知道，一算吓一跳，在这 89 天的时间内，我平均每天的高效、高价值学习时间只有一个半小时…… 数据二：状态的好坏会持续连续几天时间 我把这 89 天的 I 类时间制成图表，结果是这个样子： 可以观察到，我的 I 类时间有多个在连续几天内都比较类似的情况，下图框选的看起来更明显： 这说明我学习的状态好坏会持续连续的好几天时间，既可能在连续的好几天内学习状态都不错，也有可能连续好几天摆烂……不过这其中有的是在某段时间内有些别的事情占用了我大量的时间，比如从 3 月 7 日(上图序号 26)到 3 月 18 日(上图序号 37)这两周学校安排了金工实习，一大早出发去老校区，下午四点多才回来，就没有多少时间学习了，所以记录的 I 类时间比较少。还有些低谷期是耗费了大量的 II 类时间，比如我有几天时间我重新配置了一遍我的 NeoVim ，有几天时间是我给我的旧台式机换了内存和硬盘，折腾着装了 Windows + Manjaro Linux 双系统，有几天时间是学校里 b 事太多了，还不如打游戏、追剧学到的东西多，却不得不为其耗费大量的时间……...

年初的时候我定下了今年刷够 300 道 LeetCode 算法题的目标，到 4 月 21 日，我已经刷够了100道题，按照每 4 个月 100 道题来算，今年的目标应该是能够达成的。 学而不思则罔，利用 4 月底的这几天时间，我对我的刷题心得做一个简单的总结。 算法题，其实也就这么回事 年初我刚开始写 LeetCode 的时候，真是连个简单题都没有思路，写不出来。我一度感觉十分沮丧，感觉自己智商受到打击了，但这其实是再正常不过的情况了，写代码本身就是需要很长时间学习思考、经历很久的练习之后才能做好的事情。 LeetCode 的评论区很有趣，大伙都喜欢在这里自黑： 大伙也很幽默： 所以说大家刚开始写算法题的时候都是差不多的情况。好在这个过程持续不了太久，大概做到二三十题的时候，基本上绝大多数的题型都遇到一遍了，这个时候再遇到见过的题型的时候就逐渐能自己解出来题了。 说到底，常见的算法题的解法大概只有以下这么几类： 哈希表 递归、回溯 滑动窗口 双指针 动态规划 二分查找 栈 少见的有如下几类： 自动机 数学 位运算 贪心 分治 涉及到的常见数据结构： 哈希表 栈 字符串 链表 树 所以说，算法的框架其实并不大，其中重要且常见的内容并不算多，但是需要长久的练习和总结。一种题目做得多了，再看到同类型的，下意识就能想到合适的做法了，比如说： 看到题目中要求 O(log n) 的时间复杂度，那这道题目大概率和 二分查找 有关系 题目要求判断一个括号数组或字符串能否正确闭合，那这道题目很有可能要用 栈 来做 根据题目中给出的参数的变化，如果内部要执行不同层级的循环，那这道题目很有可能要用 递归 或 回溯 来做 …… 这让我想起来了我打游戏的一些体会，职业选手们玩游戏的时候，总能一瞬间判断清楚局势、开始决策、再做出反应，在外人看来就有种**“操作看起来很流畅”或“掌控局势走向”的感觉，而自己打游戏的时候在同样的时间内只能注意到比较少的信息**，这些职业选手们能够发觉到任何一丁点的细节和机会，哪怕只有一个眼位，也能够影响到整个战局。算法能力也会给我们带来编程的这种**“敏感性”**，让我们在想要实现一个功能的时候，下意识能想到最简洁、优美的写法。 事实证明，刷算法题确实提高了我的代码水平。我原来写了一个 Python 程序，能够按照我的输入给我随机生成一个数组，方便我用作 LeetCode 题目的测试用例： 注意，这里有个 Repetition 选项，控制着生成的数组中能否出现重复的元素。这就涉及到列表元素去重的问题，起初我是将列表转化为集合，然后再转化成列表，然后再判断列表的长度是否等于输入的 amount 值，大致是这个样子：...

转眼又是一年过去了，虽然也感觉忙忙碌碌，但是仔细盘算一下其实也没学到多少真东西。不过这一年里也算是有点感想，让我能发现自己的一些问题，长话短说，这一年里我最值得说的地方有两点： 把原来的Windows笔记本卖了换了MacBook 认识到自己学的知识大多只在应用层，偏离了根本 MacBook 在以前我用的笔记本电脑是机械革命 Code01 16+512G，2020年7月花费4999元在京东买的，说实话这台电脑我还是比较满意的，91Wh电池续航很长，键盘按键够大，手感也不错，虽说是个轻薄本但是也能满足我偶尔打打独立游戏的需求。然后在2021年7月份我有机会把旧电脑卖掉换了MacBook Air M1 8+256G 澳门版，6099元购于闲鱼，价格属实便宜。 换了MacBook之后，发现这玩意真的爽，续航长的离谱，49.9Wh的电池在图书馆（得开高亮度）能用8个小时左右，触控板也顺滑的不得了，屏幕、音响都非常顶级，偶尔打打空洞骑士这种小型独立游戏也没问题……当然，最令我惊奇的还是苹果的操作系统macOS，这个有点难说明，只有用过这玩意才知道有多爽。尤其是类Unix系统的Shell(命令行)直接导致了我改变了专业技术的学习方向和兴趣，让我下定决心要学习一些更硬核、更根本的技术（相较于正常的应用层的比如说编程语言或者框架的学习）。 macOS上也有很多能提高使用效率的软件，还有许多比Windows更先进的设计。完全可以说我现在已经回不去Windows了以后可能再用到Windows系统也就是打打游戏了，就像用过Google就再也无法忍受百度一样。不过我虽然不打算在此长篇大论说macOS到底比Windows优越在那里，我还是强烈推荐所有计算机专业的学生尽早自己动手接触类Unix系统，即使不用MacBook，也能给自己电脑装个Linux+Windows双系统，尝试一下学习怎么用命令行，绝对能打开学习计算机专业知识的新天地。 学习的感悟 我大一一整年几乎是纯兴趣驱动学了一些感兴趣的知识，直到我大一暑假，我一共会以下的技术： Python 一点爬虫 C语言 一点点Flutter JavaScript、HTML、CSS 不过大多数人早期对一个领域的了解大概率是片面的嘛，我也不例外，后来我接触到树莓派和macOS，了解了一些更硬核的玩法，我发现了我的学习思路存在以下的问题： 应用层的东西并不能真正提升整体的技术水平，反而会因为没有底层知识的支撑而在入门某个技术之后难以再度提高 应用层的技术隔几年就会更新换代一次，这种情况下如果没有底层硬核知识的支撑，在职业发展道路中后期可能会遇上瓶颈 目前国内IT行业虽然严重偏向互联网，但是我认为在目前的国际环境下，如果国内想要再更硬核的科技方面挑战西方国家，一定需要更多有能力从事底层开发的资深工程师 所以我就下决心要花费更多心力学习底层知识，暂且不说别的方面（如操作系统等），在大二上学期学完数据结构之后，虽然我觉得我学的并不好，仍需要进一步学习，不过目前我掌握的知识绝对够我着手刷算法题了。按照我背英语单词的经验，我觉得1天1题太难了，但是每周6题应该可以坚持，以周为单位计算的话如果哪天有事情漏掉也可以再找时间补上，所以在新的一年里我计划完成300道LeetCode算法题。目前是打算从1-300题按照顺序刷，C语言写题的话代码太长了，所以打算用Python写。 所以，从本周开始我每周末会在GitHub或者我的博客上每周更新一下刷题的动态。我也打算建一个交流群，供同学们互相监督学习和分享优质的学习资料，希望大家都能进步，感兴趣的同学可以等待我的消息。 最后，祝愿大家在新的一年里能够实现自己更多的目标，能够取得进步，变得更强！