编程珠玑（Programming Pearls）读后感(一)

很早就买了编程珠玑（英文版第二版），但是一直没有时间来学习。最近意识到每天上下班班车上的两个多小时其实很珍贵，下决心利用这个时间来看些书。历时2个月，终于把这本小册子囫囵吞枣般的通读了一遍。

以前看完书，总是很有成就感的把书一扔，过不了几天就把当时的领悟忘记了。也很少再去读第二遍。最近突然意识到，读书就是跟原作者的思想交流，这跟 我们平常面对面的交流有很多相似之处，但更加系统化。往往第一遍阅读能抓住作者思想的30%就不错了，反复阅读温故知新是必须的，读书笔记更是必须的。因 此通过这篇文章记下自己从书中所得，以便下次阅读时能快速恢复自己领悟的部分。

思想很重要

思想是灵魂，这是最近在工作和读书过程中的体会。具体到IT行业，有思想的写代码就是大师，没有思想的写代码就是码农。 从之前看过的《代码大全》和《C++沉思录》，到《编程珠玑》，处处体现着思想的光芒。突然想起刚学习写代码时读过的《VC技术内幕》，几乎没有什么思想而已，通篇只是工具介绍。真应该早几年能读到这种大师级的作品。

言归正传，看看这本书里体现的思想：

• 真正的程序员怎样写出正确的程序：problem definition, algorithm design, and data structure selection.这告诉我们，当我们遇到问题的时候，首先要弄清楚到底问题是什么？然后再考虑合适的算法设计和数据结构。这里问题的定义很重要，它是 指对用户需求高度抽象以后，从程序员的角度所看到的“问题”。问题定义得精确与否，直接影响到后面的算法设计和数据结构的难易度和效率。

• Scaffolding(脚手架). 顾名思义，脚手架是我们在盖房子之前搭建的临时的框架，保证房子能按照设计来建造。scaffolding帮助我们能确保程序的正确性，就像我们盖房子一样。这个过程往往出现在coding过程中，特别是实现一个算法的时候。

  • 首先，伪码帮助我们理清思路

  • 在真正编码的过程中，利用scaffolding(通常是assert或者log)来确保程序执行到某一行时，某个变量预期的值应该是多少。这样在代码编写过程中保证我们的实现是正确的，避免之后通过debug来查找错误，提高编码效率。

• 本书的第二部分的主题是Performance。包括时间效率和空间效率，往往这两个直接是有一定联系的。关于空间复杂度和时间复杂度的问 题，《算法导论》有详细解释，我目前还处于初学阶段。本书通篇都在根据同一问题的不同solution来探讨如何把时间复杂度从n^2减少到 nlog(n),甚至线性的n，这些内容需要在下次阅读时仔细琢磨。说老实话，这个部分我最多理解了30%。作者还在书中提到研究performance 的三个原因，有必要记录一下：

  • 它在所有application的内在重要性（intrinsic importance）
  • Performance是学习编程的很好的素材，它几乎要考虑方方面面的问题。这里提到两个名词：估算（back of the envelope calculations), performance tuning.
  • 第三个原因，也是最重要的原因：速度是必须的。作者引用了《壮志凌云》的原话引出 - immortal words of the 1986 film Top Gun:"I feel the need... the need for speed!"

• 本书的第三部分虽然叫做Product，但只是用前两个部分中的方法来解决一些有意思的小问题。往往一个问题有很多种方法来实现，然后根据 当前方法的不足，来进一步提高并实现更好的解法。详细介绍了排序搜索（quick sort），Binary Search Trees， Heaps(binary tree的一种典型应用）。总结了部分经验：

  • 对于大量数据n, Quick Sort可以做到O(nlogn)的run time排序;但对少量数据的排序，Insertion Sort表现更好，特别是那种基本上排序好了而只有少数几个没有按照顺序的数据。
  • heap的两个属性：order 和 shape。 order是指父亲总是小于或者等于孩子的值。shape是指树中没有空节点，叶子节点总是在最底下的两层中，而且如果一个节点只有一个孩子的话，这个孩子一定是在左节点，右节点为空。
• Hash的重要性。在介绍查找的时候(13.4)，利用hash思想的bins搜索方法最快，超过了binary tree，让我对Hash有了深层认识。15.1中也提到了同样的比较。但对其中具体如何实现hash，我还存着疑问，只有等下次阅读来解决这个问题了。

最后，用作者在第一版的结束语中，对design process的总结来结束这篇读后感：

• Work on the right problem
• Explore the design space of solutions
• Look at data
• Use the back of the envelope
• Exploit symmetry
• Design with components
• Build prototypes
• Make tradeoffs when you have to
• Keep it simple
• Strive for elegance

keep it simple和Strive for elegance是我目前能理解和追求的两个方面，产生共鸣的感觉真好...  (全文完)