秋梦无痕

from: 逸仙时空

发信人: kyhpudding (只要衫除实得~), 信区: CS
标 题: IT 民工男的 CS 课程记忆
发信站: 逸仙时空 Yat-Sen Channel (Sun Mar 7 16:42:31 2010), 转信

先介绍下自己，03CS 本科。
在某更懂中文的地方混了两年多，做社区产品，后来做基础平台，带项目带新人前端到后端应用到底层跟各部门死磕无处不折腾，每年都为可以公费回广东回来校招，据说是杀手，不过我不觉得。
最近在一以企鹅为吉祥物的公司继续折腾。
此文仅代表个人观点，也只包含个人经验。

聊聊 CS 本科各种课程对实际工程工作，更准确点，对典型互联网行业的工程工作的影响。
试图回答: 这些课程有啥用？以及，为啥面试会问这种 BT 问题？
不过如果你不希望走技术方向，或者希望折腾一下技术就"转管理"请忽略这篇文章。

首先是数学，我本科四年最后悔的事就是没把数学学好。掩面，这个问题先不谈。

程序设计，首先是语言问题。可能大家会抱怨出来工作基本都是 java C# 了，为毛大学还在教 C++，落后！好吧，我最熟悉的语言其实是 C 语言……

我们看程序设计担负的任务。一方面，你必须掌握一门跟计算机沟通的语言，否则后面的课根本没法学。另一方面，通过学习程序设计——而不是某一门特定语言，掌握一些基础的设计方法和一些思路，为进行真正的工程开发做准备。

从掌握计算机原理，以有效利用计算机的角度考虑，应该选一门相对低级的高级语言，这自然是 C，它对于一些底层问题: 硬件，数据结构，底层操作系统机制等提供了合适程度的抽象，把我们对计算机的认识从底至上衔接起来: 写汇编时，你得知道指令对底层硬件的意义; 同样的，你需要能把 C 的循环，数组寻址，指针在汇编上到底是什么解释清楚，你需要知道函数调用压栈的到底是什么数据，memcpy 到底怎么拷的数据 (经典问题)。到学 OS 时，如果用 linux (或任何 UNIX-like) 做教材样本，你得有很扎实的 C 语言功底，才做得来操作系统实验，或者至少理解系统调用用怎么完成。C 是系统底层的标准语言，扎实的 C 语言基础是了解系统底层原理的敲门砖，至于为什么要对这些计算机系统底层如此了解的原因，我们下面再谈。

另一方面的任务，涉及到许多人每天的工作——程序设计。两个分支: 数据结构和算法，软件设计范式，抽象，建模现实世界问题，提供计算机解决。这要求有一个能让底层细节不会阻碍思考，而且相对实用的语言。越来越多的大学使用 Java，当然也有不少人讨厌这个，MIT 使用 scheme 和 python。从达到教学要求角度看，我觉得都没什么问题。前提就是: 你依然得有很好的 C 语言和其他底层知识基础。数据结构和算法下面我们还会说到。设计范式，抽象，建模等问题，相当地困难 (数据结构也是一种抽象方法)。我那时的程序设计书好像就是讲了一堆 C 的知识，然后后面附加讲了点 "面向对象设计"，其实是在讲 C++ 的语言特性，非常生硬难懂。我觉得首先得解决的是一个关于 "如何抽象问题，建立模型" 的问题，而"面向对象" 仅仅是其中一种可选方法！而如何使用语言特性去实现这些抽象方法，那更是细枝末节。在这方面，我还是觉得 MIT 原6.001 课程 SICP 做得最好，逐步引导越来越高层的抽象，一步步教导经典设计思路，而不是一次过塞给你一坨似是而非的理论以及非常恐怖的语言特性。至于 design pattern——专指 GoF，我认为是应该在有相当的开发经验后自行修炼的，不适宜在课堂上讲授。

说回来，我认为程序设计课应该分成两部分: 为了解计算机系统底层原理准备的 C 课程，以及为学习计算机的高层理论知识提供趁手的高级语言工具。MIT 以前用 scheme，现在用 python，两个课程链接:
6.001 SICP
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/CourseHome/index.htm
6.189，这门课的教材就叫 How to Think Like a Computer Scientist
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-189January--IAP--2008/CourseHome/index.htm

程序设计是一个 准备 课程，好戏在后头。在实际开发中，底层我们用 C/C++ 应用层我们用 Java PHP Python 等等等等，还有各种脚本，甚至自己设计语言。从语言角度，我不认为深入掌握 C 和 Scheme 的人学习任何还算正常的语言会有多难。至于应用框架/系统，那是另一个问题，有兴趣的自行学习，许多大公司对此自有一套，大学不是什么培训机构，要在课堂上讲这些，会让人笑掉大牙。

数据结构与算法，这咚咚每天都要跟它打交道。基础数据结构，是这行的通用语言。面试时要考察 candidate 是否对此熟练掌握，其重要考虑就是: 不掌握无以沟通。没人有功夫跟你解释 B+ 树是怎么回事，如果我说这个模块维护了个 B+ 树你看着我一面惘然，那大家都会很痛苦。当然，有的数据结构，比如倒排表，你没听说过我觉得很正常，但我可以三言两语就让你明白这是怎么回事，你可以马上运用它来解决问题，那就行了。

算法——参加 ACM 对此有帮助，但专门钻研算法的奇怪技巧却没太大帮助。同理，一些基础算法，例如排序，是行业通用语言，不掌握无以沟通。而每个专业分支都会有其专门的一些算法，这些也不是本科计算机课程可以和需要教授的，本来就应该在工作之后再学习。

但另一方面，我们往往需要设计算法——往往是某些算法的变体和结合，我们更往往要分析算法复杂度——这是个要命问题。这是可以在课堂上学习到一些基本方法的，虽然会令这门课看起来更难，而且需要更好的数学知识 (知道我为啥后悔了吧，顺便说一下，某大牛的观点，CS 数学是应该学数学分析的，深以为然)。但我认为，有基础的人就算不知道某算法，也会一听就明白，并能利用。但算法分析，这个不抓紧时间在课堂上学好，以后就难了。

算法方面还是建议看 Introduction to Algorithms 吧，MIT 课程
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm

微机原理/计组/体系结构。对我来说，这些课程的作用就是让我知道，我折腾的那个铁盒子到底是怎么一回事。考虑一些系统性能问题，做设计权衡时，我必须考虑实际的计算机体系，各部分的性能状况——有了基础，还要时刻紧跟随摩尔定律发展的潮流。我们必须时常考虑，硬盘的读写特性是怎样的？Cache 能多有效，怎么利用多核 等等。

操作系统原理，这是一门核心课程。在我的工作中，它有两方面用途。一方面，为了实现高效的低层应用，我需要清楚操作系统的行为，需要了解我的 API——系统调用的实现原理，效率情况。我这行在服务端通常使用 linux 系统，而 OS 教学在传统上以 UNIX 为范本，有的甚至直接采用分析 linux 内核的方法，这就很好地结合起来了。基本上，扎实的 OS 知识，再加上 APUE，linux 系统编程就问题不大了。

OS 也提供了一些常用的概念和抽象方法: 例如锁，线程和进程。你会在各种地方碰到他们你需要利用它，你有时候需要自己实现它，你有时候还会发现一个自旋锁耗掉多少 CPU 指令是影响你的程序性能的关键……

另一方面，可能是大家容易忽视的，是 OS 乃一门非常重要的工程入门课——我认为这才是 OS 最大的意义: 开始学习设计实际系统。
- 学习一个真正的大型系统。真实的操作系统都非常复杂，你可以看到现实世界的模块划分和抽象方法，你可以看到闪光的设计思想——以及一些丑陋的既成事实，这比任何一本所谓 "设计方法" 的书都来得精彩。ps: 看看 APUE 吧。
- 分析瓶颈，考虑权衡: 当你面对的是一个系统而不是一个单一问题点的时候，分析瓶颈成了一种重要能力。没有最优算法的说法，调度方案等等有得必有失，方案取舍必须在充分的分析基础上进行。linux 的调度算法，cache 设计是怎么样并不重要。重要的是: 它为什么要这么设计？解决什么问题？这个方案基于什么假设？对什么有利而什么不利？是否与应用模式相吻合？我们用什么方法来精确测量，验证这些问题？

这些都是非常重要的工程能力。我遇到过一位同学，解决一个模块的性能问题，上来看了一通代码，然后跟我说: 那个函数复杂度是 O(N^2) 可以优化成 O(NLogN) 的，但实际上那个函数的数据规模只是几十，更重要的是，此时模块的瓶颈在 IO。OS 的课程教会我们这些重要的分析方法，还有一些非常精妙的设计思路——这会在应用其他地方用得着。

网络，这门课同样有两方面意义。一方面是掌握常识: 我们总得知道什么叫 "四层设备"，总得能分清楚交换机和路由。当然，一些网络编程知识也包含其中。另一方面，我认为对协议设计的理解，尤其是 TCP 设计的理解，提供了设计分布式系统的基本思路和基本知识，TCP 的许多设计方法，在高层次通讯协议的设计中照样适用。我在文后会给两个例子。

数据库，我觉得这门课非常难教。讲理论吧，讲成数学了。讲实现吧，不现实，讲 SQL？这不搞笑么？实际上我们每样都得学点。数据库跟 OS 课程很相似的一点是: 它是许多学科重点知识和问题的集中体现，要看看那些稀奇古怪的知识是怎么用到现实中的？看看 OS 和数据库吧。

数据库一方面得讲经典的关系理论——基本上只要还是在设计存储系统，就很难撇得开它，这还得有很好的数学基础。同时也掌握了基本的范式，基本的设计方法。在思考一个实际问题的存储方案时，这是你的思考起点。业界这两年流行讲反范式，或者干脆讲 NoSQL，No-RDBMS，不过相信我，经典的关系理论往往还是你思考的起点。

数据库总会有个地方讲并发，讲 ACID，讲事务。嘿嘿，欢迎来到业界第一大坑，OS 的锁知识学好没？准备了点分布式系统常识没？准备好了就跳吧。业界流行对 ACID 进行取舍，以达到可扩展性等目的，我们不是要盲目去接受这些 "流行" 的东西，我们有时间在课堂上好好搞清楚 ACID 各为的是什么？怎么实现？会有什么问题？怎么个死锁法？

最好再来点实现内容，数据库的 index 是个什么原理？存储具体该怎么实现？一个查询语句，结合 index，你可以怎么做？

当然我们还是得知道的 SQL 的，这东西实在太好懂，表达工具而已，抠细节则不必。我想课堂上自然也不会详细讲 MySQL 怎么配置啊，Oracle 有什么 BT 特性啊之类的东西。

编译原理，这门课放在本科承载的内容有点杂了。首先得讲一下基础中的基础，自动机。又得讲经典的词法分析语法分析内容。还得讲怎么编译到机器语言。从实用角度来讲。一方面自动机的知识词法语法分析的知识给我们提供解决相关问题的基本思路——这些都是 CS 最基础的问题。另一方面就如一开头所说，我们有时候不得不设计语言，在设计语法，设计解析器的时候，了解基本的编译原理知识，并熟练运用 lex&yacc 成了必须。

至于代码生成的部分，我不敢说重要性有多高，但至少我用到过相关的知识。

软件工程，恕我直言，这不是应该在 CS 上讲的课程，至少不应该看得很重。这有很多是管理问题，又有不断更新的新概念，新理论。更重要的，我认为它更多的是 Art，而不是 Science，更应该在实际工作中学习积累，做成选修课不好？反正放心吧，无论讲不讲，你铁定不会一出来就是项目经理的。

我还要推荐 joelonsoftware 的一篇著名文章
Advice for Computer Science College Students
http://joelonsoftware.com/articles/CollegeAdvice.html

最后，这里提供几个问题，帮助大家检查一下，自己的本科学习是否牢固，以支撑工程需要。这全部是基本问题，算法问题就不列了。
这不是面试经验，每个公司的面试都有不同风格，但解决以下这些问题的能力在我的工作中是必要的。

1. 请实现 memcpy。

2. 用 PV 信号量或 mutex，实现一个读写锁。

3. 说说 fread 从一开始到读到磁盘的整个调用过程？

4. malloc 是操作系统内核实现的吗？实现一对 malloc/free

5. 说说 TCP 三次握手？为什么是三次？为什么关闭连接要来四次？SYN Flodd 怎么弄，怎么预防？

6. 说说 TCP 的滑动窗口机制，自己实现一下。

7. 设计一个内存垃圾回收方法，说说它的优势和局限。

8. 假设我已经有一个 B+ 树的存储实现。请利用它实现一个基本的数据库系统: 针对某类查询，如何建 index，如何执行查询，如何完成一条更新操作？

补一门 MIT 的工程课，建议所有希望投入到工程的同学学习
Computer System Engineering
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-033Spring-2009/CourseHome/index.htm

本科的时间，不花在学习课程上，去学习某样流行的技术，也许能令你找到一份令人羡慕的工作，但是别怪我乌鸦嘴，你很快会是那个抱怨知识更新太快，跟不上，年纪大了失去竞争力的人。

--
Just for fun

※ 来源:．逸仙时空 Yat-Sen Channel argo.sysu.edu.cn．[FROM: 112.94.249.26]
※ 修改:．kyhpudding 于 Mar 7 18:40:18 修改本文．[FROM: 112.94.249.26]