编程珠玑,字字珠玑


Programming Pearls跌跌撞撞,连滚带爬地但还算仔细地读完了这本书,感觉身心愉悦、神清气爽,决定还要再度几遍。

首先,这本书的书名好,中文译名更好——《编程珠玑》,正如本书的风格,篇幅精悍短小,行文流畅优美,十五章的正文如十五颗熠熠生辉的珍珠,阐释着编程之道,没有一句话多余,也不必再增,果然字字珠玑。译者显然比我功力深许多,要是我,恐怕就直接译成珍珠了——过于直白,顿失优雅。

概览全书,共分15章,短的仅四五页,长的不过数十页,一本书薄薄200来页,似有K&R《C程序设计语言》一书风格。前十章介绍程序设计的基本原则和基本技能技术,后五章给出运用这些原则、技术的实际应用,“效率”是贯穿全书的主题。每一章开始提出有关本章主题的若干个问题,接下来详细分析,给出解决方案,章末还有总结和拓展习题。语言风格绝非教科书式的“周吴郑王”,更像是在讲故事,如作者在第一版跋中自问自答所述,“本书的章节侧重的是故事情节而不是定理和表格”。源码大多以接近C/C++伪代码写成,也有部分C/C++代码,这样将主要的注意力集中在算法和数据结构上,而不是规范的声明、接口,有些甚至略去了错误检查机制。边栏和深入阅读大大拓宽了读者的视野。

我觉得有必要按章来总结一下这本书。

第一章
开篇提出“怎样给一个磁盘的文件排序”的问题,阐述了正确定义和理解问题的重要性,这是程序设计的第一步。这一章回答了为什么要自己设计数据结构自己设计程序,而不用系统提供的功能。事实上,系统为我们提供了许多有用的程序功能,但是有时候因为一些原因,我们不能使用,更多的时候是因为效率问题,我们需要自己设计。

第二章
通过三个问题揭示算法给程序员带来的好处,一个精妙的算法在时空效率上给程序带来的好处。1.在海量数据中寻找缺失的某个数字;2.字符串的循环左移; 3.寻找“变位词”集合。在本书中第一次正式讲到了二分搜索和排序。

第三章
数据视图决定了我们在程序中应该采用什么样的数据结构,好的数据结构可以简化代码。

第四章
这是非常重要的一章,本章仔仔细细地讨论了二分搜索,从最初用伪代码表示二分搜索的思想,一点一点扩充完善代码,最终形成非常接近C代码的伪代码。后半部分使用程序验证技术讨论了上述代码的正确性,逻辑缜密。

第五章
将第四章的二分搜索的伪代码用C语言实现,使用断言对所实现的程序进行了测试,并介绍了一些测试和程序计时的方法。 第五章的第一条习题讨论了本书的编程风格。

第六章
讨论了程序性能分析,以一个实例讲述了在计算机系统的若干个设计层面上提高程序执行效率的方法,然后给出了系统化观点的总结。

第七章
这一章是有趣的估算。开篇讲述了一些估算的基本技巧,然后介绍了程序性能的估计等问题。

第八章
这一章可以看作是第二章的进一步讲解,突出了算法设计在程序设计中的重要地位。本章的问题是“求和最大的连续子序列”,这是今年淘宝实习生招聘研发类的一道笔试题。对这个问题,本章给出了4种不同的算法,从一个显而易见的算法开始,逐步优化,降低时间复杂度,最终得出最优算法,过程非常详细。

第九章
这一章讲的是代码调优。前半部分讲了四个问题的代码调优。1.整数取模;2.函数、宏和内联代码;3.顺序搜索;4.计算球面距离。后半部分对二分搜索进行了细致的代码调优,书中称之为“大手术”。

第十章
讨论了如何节省空间。前半部分以实例介绍了稀疏疏结构,后半部分给出了数据空间技术和代码空间技术,使用这些技术以节省存储空间和代码空间。

第十一章
这一章详细介绍了插入排序和快速排序,同样从最初简陋的代码逐步优化算法,并使用部分第九章介绍的代码调优技术对代码进行优化。

第十二章
讨论一个有趣的问题——生成随机数。本章给出了三种不同的解决方案。

第十三章
本章介绍了5种表示集合的重要数据结构——数组、链表、二叉搜索树、箱和位向量。对每一种数据结构的实现都做了详细的讲解,并对其性能进行了分析,同时提出了一些优化的方法。

第十四章
介绍了两个重要的数据结构——堆和优先级队列。后半部分介绍了堆排序。

第十五章
这一章围绕字符串进行了一些讨论,统计一本书中每个单词出现的次数,查找字符串中最长的重复子字符串以及随机生成文本,主要涉及的数据结构是散列表和“后缀数组”(字符指针数组)。章末再次讨论了关于使用库组件还是定制组件的问题,一些库组件通用性强,但效率不如定制的专用组件高;有些库组件是非常高效的。

最后说说我觉得这本书不足的地方。本书把习题提示和习题答案分开了,我觉得没有必要,这反而给读者带来了阅读困难,实际上某些习题提示已经非常接近最终答案了,而某些习题答案只是给出了提示性的语言,所以两部分合并起来为好,也方便阅读。本书一些章节的标题起的不好,这似乎和一个我非常赞赏的书名很矛盾,比如第十三章,章标题是“搜索”,而主要内容将的却是几种数据结构,虽然这章开始交代了本章内容有一个搜索问题引发,可我怎么也看不出那是一个搜索问题。前面有些章节的标题也不够好,看不出本章的内容到底是什么。个人见解,仅供参考。

  1. #1 by INNOCENT on 2011 年 08 月 17 日 - 10:52

    该书适合作为床头书吗? 自从看完 黑客与画家 之后, 打算养成睡前看点书的习惯= =…

    • #2 by mazhechao on 2011 年 08 月 17 日 - 11:11

      适合在书桌前认认真真读。睡前还是读点轻松的吧。

(will not be published)

Are you a human?