什么是计算思维？
最近读完了吴军博士著的一本畅销书《计算之魂》，对计算机的认识更进了一步（虽然仍然肤浅），在此对自己目前的理解水平做一个快照。
读这本书的动机
一直以来我都对那些“高屋建瓴”式的书籍很有好感。可能是因为这些观点有点儿像万金油，从哪个角度都能理解，总给人一种有所收获的满足感。在读《计算之魂》之前我在豆瓣上刷到有关它的书评，一时间被所谓的“计算思维”、“工程思维”这些大词给唬住了。
另一方面，我对畅销书都不是很感冒，认为它们多半都是披上外衣的鸡汤，并无多少实质。
在这样矛盾的心理下，我决定自己读一读这本书，既是对“大词”的祛魅，也是对畅销书的平反(笑
读后的整体感受
这本书不太厚，只有十一个章节三百来页。吴军博士在每个章节会以一些经典的例题讲解他认为重要的一个计算思维，同时也会对这些例题和思维能力做一个评判。比如某道题曾在XX公司作为面试题刷掉了多少人、XX思维是高级工程师必备的素质等等。有趣的是，吴军还效仿朗道为物理学家评级那般为计算机工程师列了一个等级，每一道题后面他都会附上做出这道题相当于几级工程师，让读者清楚自己的实力（备受打击）。
总的来讲，这本书传递的很多思维十分受用。我将这些思维大致分为以下几类：
- 如何编程解决一个给定的问题？递归思想（第二章）、分治思想（第六章）
- 如何将现实问题转化为可计算的问题？编码（第三章）、分类与组合（第四章）、图论（第五章）、等价性与因果关系（第九章）
- 如何把理论可解的问题变为工程可解？分治（第六章）、存储（第七章）、并行（第八章）、随机（第十章）
坦率地讲，每个章节只是举了几个例子以及一些思考题，这些训练只能是让读者感受一下这种思维的作用以及简单了解一下在工业界的应用（主要是Google）。但这样的内容编排我仍然觉得受益匪浅，吴军博士从自己对计算机思维的理解出发给读者展示了一个清晰的框架————什么样的思维在计算机中是本质性的，遇到问题应该从哪些方面去考虑？之后再通过对框架中内容的不断细化学习，将这些思维内化于心，熟练运用是完全可行的。
印象深刻的内容
什么是计算机？
作为一个软件工程专业的学生，我每天都在使用计算机也一直在学习计算机的底层原理。但在读这本书之前，我其实不能解构计算机这个概念。
在本书中，作者通过几个例子指出计算机其实就是一个具有运算能力、存储能力并且受指令控制的机器。我们现在习惯了集成电路驱动的计算机，认为这就是计算机的本来面目，其实如何驱动并不是关键，像中国古代的算盘甚至是《三体》中巨大的人型计算阵列都是计算机。
对这一概念的解构让我也理解了计算的本质其实就是机械运动。
分治的两个作用
学过算法的同学都知道主定理，它决定了一个问题采用分治策略会不会带来时间效率上的进步。在这本书中，我了解到了分治思想的难点和另一层作用。
分治的另一层作用在于可以将工程上难以在单机运行的任务分发给集群共同完成，同时也利用并行提高了效率。
分治难在如何分解问题。比如书中提到的求100TB数据的中位数问题。分隔算法既保证了低复杂度，也使多台机器共同计算成为可能。其次，同一个问题可能有不同的分解策略，不同的分解策略对应的Merge操作复杂度不同，来看下面这一例：
有25名短跑选手竞争前3名，赛场上有5条赛道，因此以此可以有5名选手同时比赛，比赛并不计时只看相应名次。假设选手的发挥是稳定的，他们相互比赛的序是保持不变的。问最少需要几次比赛才能决出前三名？
因为一次只能排出5个数据的序，像传统分治将问题划分为两个子问题就不好merge了。受这一点直觉的启发，我们将问题划分为5个子问题，即5个人一组分别比赛。第6次比赛安排每组的第一名进行比赛决出整体的第一名，第7次比赛枚举“仍然可能”是2、3名的选手，会发现恰好只剩5个，因此7次比赛即可决出前三名。（严格的证明略去）
智力题还是思维题？
书中有很多看似测试智力的题目，即从题面完全看不出对特定知识的考察，全然要靠读者的灵机一动。但实际上在吴军博士的解构下，这些题目很多都可以用书中讲授的计算机思维延伸出来。比如书中的两个玻璃球问题：
给你两个一模一样的玻璃球，如果这两个球从一定高度掉到地上一定会摔碎，而如果在这个高度以下扔则不会碎。现已知这个恰巧摔碎的高度在1~100层，问最少需要试验多少次才能测试出摔碎的高度。
乍一看，此题确像智力题，但如果从对信息编码的角度出发则很容易求解：0~99在十进制下有两位，正好对应两个玻璃球。可以先 用第一个玻璃球测试十进制位是什么，再用另一个球测试个位，因此最少需要19次。（事实上还能更少一点，但那种做法就不是出 于考察计算思维而是数学能力了）
类似这样的题目在书中不胜枚举，实在是一场丰富的体验。
统计海量文本中出现频率最高的100万的二元组
这道题贯穿了这本书与工程思维有关的每个章节，最后的解决方案也引出了MapReduce这一技术的核心思想。
首先可以采用工程上近似的解决方案，即先通过抽样大致确定频率最高的1000万个元组，假定包含所有待求元组，然后在扫描全部数据时只记录这1000万个元组就能在单机上完成了。
如果要采用精确的做法，肯定要先分治，因为海量数据的Partial Result在单机中存不下。将数据分解到单机可解的范围后，单机内用哈希表完成统计，然后根据$<x,y>$二元组进行排序，之后将不同单机的统计结果进行merge。排序一方面可以加快merge时的效率，另一方面也保证对数据的读取是顺序而非随机的，降低IO瓶颈。
事实上，上述办法需要merge多次才能合并二元组频率表，因为计算机同时打开的文件数是有限的。书中还提出了减少merge次数的算法：不必将频率表合并到一张，可以约定$N$台机器中的第$i$台存储频率表的$[\frac{i-1}{N},\frac{i}{N})$（根据二元组排序，这样做是为了去重）, 之后在这$N$台机器中应用并行版本的分隔算法即可。这也是MapReduce的核心思想。
阅读时还有很多印象深刻的内容，此处就不一一列举了。
总结
这本书作为畅销书确实有夸大宣传的意味，比如封面上的“计算科学品位和认知进阶”；但瑕不掩瑜，书的内容还是挺令人眼前一亮的。读完这本书，除了完善自己的计算机学科思维框架外，还有一个重要的收获：
之前我总是希望能找到一个自己喜欢的方向认真钻研，为此学习了很多“专门”的知识，比如程序分析、数据库开发等等。读完这本书，我有一个感觉是计算机工程中很多问题都是相通的，看似专门的解决方案背后都是计算思维的应用。比如数据库中的SQL优化，其中主要的算法就是动态规划；Deadlock的诊断及破除也不过是简单的图论应用。因此，过早地将自己投身于某些专门的领域或许能比别人多一些相关领域的经验，但如果基础不牢，这些专门领域的经验就是只见树木不见森林，难以迁移应用。换句话说，仅仅是“了解”而非真正的“理解”。
那什么是基础知识、通用知识而非专门知识呢？我觉得《计算之魂》这本书为此搭起了一个相对完善的框架，整本书传递的这些思维在计算机领域相当通用，值得在之后的学习中进一步落实。
