《编程珠玑》读书笔记

一直知道《编程珠玑》是一本很经典的编程书籍,其实很早已经入手了,但每次都是翻开前几章,就断开阅读了。虽然这次也是磨磨蹭蹭很久才把书过一遍,所以觉得应该书中的一些总结记录下来,毕竟简单的过一遍,就觉得满篇精华了。

书本一共分了3部分,分别为:

  • 基础
  • 性能
  • 应用

所以我的读书笔记也跟着这个思路去写好了。

这仅仅是读书笔记,所以很多都是来自书上的内容了。

第一部分(基础)

第一部分,我觉得是从一个程序整体上看,如果编写一个好的程序。从第一章描述如何准确确定和描述需求(问题),到第二章算法在程序的重要性,第三章的程序代码的结构化,第四章的如何保证代码的正确,第五章的测试,都是从一个整体的角度观察程序。就像名字“基础”一样,这是第二部分的基础,如果无法保证代码的良好结构、正确性和测试,第二部分的性能优化根本是无法下手的。

分析问题的步骤

  1. 正确的问题。要准确的问题描述,可以用下面三部分对问题进行概况:

    • 输入。问题提供的“参数”条件
    • 输出。问题想要得到的结果。
    • 约束。有哪些限制。
  2. 决定算法的采用,不要一开始就是用最“暴力”的解法。

  3. 最后才是代码的实现。

代码的结构的优化

正确使用数据结构来是的代码更规范,以下是书中的几条原则:

  • 使用数组重新编写重复的代码。书中的例子就是将许多同类型的相似对象,使用数组来保存,从而减少冗长且相似的代码(具体见第3章的内容)。
  • 封装复杂的结构。当遇到复杂的数据结构时,尝试将其抽象定义成类,封装其操作。
  • 尽可能使用高级工具。etc: 数据库,表格,k-v存储等。
  • 从数据得出程序的结构。通过恰当的数据结构代替复杂的代码。所以在动手编写代码之前,应该彻底理解输入、输出和中间数据结构,然后围绕这些结构进行开发。

编写正确的函数

书中第4章,主要讲了怎么了写一个“正确”的程序,其要点是要通过一个前置条件(precondition)(调用函数之前的成立的状态)和后置条件(postcondition)(函数终止时的状态)来保证函数的正确型。就是在前置条件(precondition)满足的情况下调用函数,那么后置条件(postcondition)就已经确立了。就和我们开发时写的单元测试一样,编写各种情况下的参数,来确保函数最终结果的正确。

第二部分(性能)

第二部分,主要讲3个问题:

  1. 为什么性能会有问题应该优化什么方面
  2. 如何对性能进行一个评估
  3. 性能优化的3个着手点(算法,代码,空间)

性能分析

影响性能的几个方面:

  • 系统结构。将大型系统分解模块时,是决定性能的重要的单个因素。设计者需要完成简单的“粗略估算”。
  • 算法和数据结构。算法和数据结构是获得快速模块或者函数的关键。
  • 代码调优。对代码进行改进,有可能会有不错的加速。
  • 系统软件。操作系统,编程语言等影响。
  • 硬件

优化代码的着手点:

  • 如果仅需要较小的加速,就对效果最佳的层面做改进。选择“性价比”最高的那个:投入最小的精力就可以获得最大加速系数的设计层面。
  • 如果需要较大的加速,就对多个层面做改进

性能的估算技巧

  • 两个答案比一个答案好。从多个角度和方式进行估算,并比较结果。
  • 快速检查。通过一些简单的方法,粗略计算一个值。
  • 经验

算法设计的几个要点(着手点)

具体例子参考第8章。

  • 保存状态,避免重复计算。可以通过使用一些空间来保存中间计算结果,避免重复计算的时间。
  • 将信息预处理至数据结构中
  • 分治算法
  • 扫描算法
  • 累加数组
  • 下界。确定自己算法的下界。

第三部分(应用)

第三部分这比较直接,描述了程序开发上常见问题的思路和一些优化和较好的方法。

巧妙的例子

使用位图对不重复的非负整数进行排序

第1章的,举的例子是对大量已知上限的不重复的非负整数进行排序,使用了位图表示,使得时间复杂度仅仅是O(n)

二分搜索

第2章中,二分搜索是可以用来判断给定值是否在已排序的数组中。

初始条件是已知一个对象存在于一个给定范围内,而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的未知。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象,则将当前范围减半,然后继续下一次探测。当找到所需的对象或范围为空时停止。

数组的最大连续和

第8中的一个例子。

问题:

给定一个数组,输出其任何连续项的最大和。

1
2
3
4
5
[31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
^ ^
| |
2 6
其最大和是x[2...6]的总和,即187。

其中共有3中解法:

  1. 直接对满足0 <= i <= j <= n(i,j)进行迭代。但整体的时间复杂度还是O(n^2)
  2. 分治算法。(见书P86)
  3. 扫描算法。

扫描算法

从数组最左端(x[0])开始扫描,一直到最右端(x[n-1])为止,并记下所遇到的总和最大的子向量。 最大总和的初始值设为0。假设我们已解决了x[0...i-1]的问题,那么如何将其扩展为包含x[i]的问题呢?我们使用类似于分治算法的原理:前i个元素中,最大总和子数组要么在前i-1个元素中(我们将其存储在maxsofar中),要么其结束位置为i(我们将其存储在maxendinghere中)。

1
2
3
4
5
6
maxsofar = 0
maxendinghere = 0
for i = [0, n)
/* invariant: maxendinghere and maxsofar are accurate for x[0...i-1]/
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)

理解这个程序的关键在于变量maxendinghere。在循环中的第一个赋值语句之前,maxendinghere是结束位置为i- 1的最大子向量的和;赋值语句将其修改为结束位置为 i 的最大子向量的和。若加上x[i]之后结果依然为正值,该赋值语句就将maxendinghere增大x[i];若加上x[i]之后结果为负值,该赋值语句就将maxendinghere重新设为0(因为结束位置为i的最大子向量现在为空向量)。

稀疏矩阵取代二维数组

第10章中的例子,使用稀疏矩阵取代了二维数组,以节省内存的使用。