[打卡]CS61B/61C

今天上午磕磕绊绊做完了 CS 61B 的 Discussion 3. 在链表 reverse 的问题试了很久，明明思考的没问题，debug 也找不出问题，最后发现是自己单元测试写错了，后面到 Array 部分就很简单了。状态有起伏，每天能学到新东西就好。

下午开始听 CS 61C 的第四讲「C 的内存管理」，我先在 mancunian 介绍的 2015 年 Youtube 视频上听完全程，最后再对比 2019 年的 ppt，发现 2019 年新增了大概 30% 的内容，且是 2015 年的超集，例如第四讲会提到对于 C 传统 malloc 有哪些改进，而别的语言又是如何避免这个问题。又比如 C 里面结构的 memory layout 是什么样的，这些内容是 2015 年没有覆盖到的。建议听一遍 2015 的课有点感觉再过一遍 2019 的课件。

2015 年的课使用 MIPS 指令集，2019 年的课用的是 UCB 自家的 RISC-V，个人对 RISC-V 更感兴趣一些，老师从第四节末就开始像大家安利 RISC-V 了，对 CPU 指令、汇编了解不多，也是上这门课让我兴奋的点。

今天上午做完了 CS 61B 的 Discussion 4。这一节主要是 Java 的继承带来的各种代码上的表现。我拿自己熟悉的领域（TypeScript + JavaScript）来对比，其实 Java 编译器的类型检查就像 TypeScript 的 Type Checker，整个可以独立程序运行，在编译阶段进行类型推断；而实际运行的时候（就像 JavaScript 在 V8 里面运行），一开始初始化是什么类型，接下来不管怎么 cast 转换，该调用方法的时候依然优先往原来初始化时候的类去找方法，除非找不到再回到基类。

下午听完了 CS 61B 的第十一讲 Subtype Polymorphism. 函数操作于一般的类，具体的行为由类的实现者去完成。这样就引申到了把一个方法包装成 interface 契约，类只要实现了这个契约就可以和其它依赖这个契约的类联动。这个 interface 非常像 TypeScript 里的 interface，也类似于 Rust 里面的 Trait：https://doc.rust-lang.org/book/ch10-02-traits.html。

晚上做完了 eslint-plugin-ava 里面增加 no-inline-assertions 规则的设计部分：https://github.com/avajs/eslint-plugin-ava/pull/262 其实自己也做了一个大约可以工作的版本，只是觉得需求没澄清，自己动手走得太远没有必要，终于赶在图书馆关门之前回到家里了。

今天上午开始看 CS 61C 的第五节——终于开始讲 RISC-V 正题了，看了头几页幻灯片就开始觉得新东西有些多。跑到 Youtube 听了 MIT CS 6.004 的课 终于找到些感觉了。CS 6.004 的第二节也是 RISC-V 的介绍，但是浅显许多，但学生提的问题挺好的，例如为什么 RISC-V 的 operand 就要占掉 10bit ，但第二节因为才五十分钟，涵盖的没有 CS 61C 第五节多。听完了再回来看 CS 61C 第五节，理解清楚 Register-Register Operand / Register-Memory operand 之后事情就好多了，也意识到其实用 RISC-V 或者 MIPS 甚至 x86，本质还是要处理 CPU 的计算，CPU - 内存界面的数据交互的事情，那么用一个看起来优雅一些的架构，对于学习这门课本身来说，也还挺不错。这可能也是为什么 CS 61A 要使用 Python 的原因。

当看到这些平常稀松的 C 代码转成 RISC-V 之后，突然更理解为什么之前看到一些 ACMer 的代码这么喜欢循环的迭代器自减，敢情脑子里就是奔着汇编语言去的，只是把汇编语言翻译成 C 意思一下。

看到自己居然可以翻译出来一些 RISC-V 指令一度非常激动，我半个月前刚刚开始刷课的时候一定想不到半个月后的自己。

晚上提交了 eslint-plugin-ava 的 feature request，明天晚上该把时间给 babel 了。

今天，2019年6月13日，Raptors 夺冠了，人群欢呼。昨天东八区的人还在上演平行世界。

而我，眼里只有 RISC-V 和许许多多等着我的 Compiler Techniques。

昨天做完了 CS 61C 的 Discussion 02。在做 Proj1 的时候发现仓库拖下来的单元测试失败，最后检查是 CUnit 版本问题，仓库的单元测试在新版 CUnit 下面因为界面不正确会 segmentfault，详见 https://stackoverflow.com/a/56615393/1490357

解决了这个问题之后，单元测试就可以正常写了。

另外 CS 61C 今天更新了网站，目前正在准备 summer 19 的课程，下架了所有的课件和作业。目前可以通过 Archive.org 访问旧版的网站继续学 Spring 19 的课程：http://web.archive.org/web/20190528205037/https://cs61c.org/

今天的时间都贡献给了 babel。尝试换一种方法来解决 scope 的问题，详见 https://github.com/babel/babel/pull/10055#issuecomment-502519402

今天挺顺利过完了 CS 61B 的 12 讲到 16 讲，因为中间有两讲是数学课，Josh 一再说这可能会 daunting，嗯，好吧。

讲到 BST 的时候，突然豁然开朗，从 List 到 BST 原来是（为了优化搜索，指向中间点以节省一半的搜索步数）这么一个 idea 然后根据 ordered 特性进行递归之后的结果。和原来对二叉树的「树」的纠结比起来，一下子打通了很多事情。后面自己在暂停 Josh 剧透二叉搜索树的删除算法之后，自己重新发现了 Hibbard Deletion 这个过程还是蛮开心的。

今天做完了 sp18 的 Lab 9：实现 TreeMap 和 HashMap。这两个数据结构在实现的时候都有卡壳的情况，TreeMap 难点在于 remove 的实现，需要同时更新链接与删除节点的置换，还要处理当左右分支都存在时，使用 Hibbard Deletion 的交换节点过程。

HashMap 因为已经有了 ArrayMap 的实现而变得相对简单一些，需要注意 resize 的时候需要 rehash 所有的元素，（所以叫做 amortized constant time access）。

前天做完了 CS 61B 的 Lab 5，主要的难点在于决定六边形的起始与终点。计算的时候我知道它们都和六边形的 size 成线性关系，所以都是拿两个特例去拟合这个线性函数。

昨天开始做 CS 61B 的 Project 2 Phase 1，设计了一个天真的地图生成算法，今天计划再想想有什么可以改进的，然后再动手实现。

昨天去参加一个 meetup ，停了一天。

前天听完了 CS 61B 的 Lecture-17 B-tree，B 树的 split node 想法真是石破天惊，在维基百科上也有介绍哪些文件系统使用 B-tree：https://en.wikipedia.org/wiki/B-tree#In_filesystems 最后我把 extra 部分的 B-tree deletion 也看完了，希望可以自己动手实现一下，然后可以比对下现有的 ext4 filesystem 里面的 B-tree 实现。

今天打算换一种学习方式，先读阅读再来听 Lecture 18.

另外强烈推荐开始跟 61C 的 Summer term：主要卖点是 Autograder 对所有人开放，只要照着 deadline 走就可以了：https://cs61c.org/#by-week

补充内容 (2019-6-26 22:45):
Linux 里面的 B+Tree 实现：https://github.com/torvalds/linux/blob/master/lib/btree.c

RBTree 实现：https://github.com/torvalds/linux/blob/master/lib/rbtree.c

今天做完了 Project 2 的 Phase 1，使用了随机生成房间再来连接各个房间的方法，最后生成的地图因为连通性很强变得难度很低，考虑一下可以如何改进。

今天听完了 Lecture 20 Priority Queue and Heap. Josh 感冒还在录课程真是令人敬佩。自己想出来了最小堆的插入和删除方法还挺开心的，回顾这一个月可以明显看到算法理解上的进步。感谢可以随时暂停的公开课，可以让我一步一步学习算法。

昨天参加了 Toronto 的一个 Rust Meetup，看到了 Mozilla 几位大神的分享，非常有意思，有志于成为像他们一样有趣有深度专注自己热爱的事情的人。Meetup 的视频链接在 https://www.youtube.com/watch?v=F1AquroPfcI