编程珠玑读后感

读后感

该书喜欢引用论文，理论性很强。由于出版时间的问题，本书介绍的算法在现在看来可能已经非常普遍了。中文版翻译的也有些生硬。

第一部分基础

第一章开篇

问题：对一个最多包含 $n$ 个正整数的文件进行排序。

输入：一个最多包含 $n$ 个正整数的文件，文件中每个数都小于 $n$，其中 $n = 10^7$，没有重复的数，没有其他任何关联数据。输出：按升序排列的列表。约束：最多使用有 1MB 的内存空间。

解决：使用一个 $10^7$ 个位的字符串表示这个文件。

第二章啊哈！算法

三个问题

1、给定一个最多包含40亿个32位整数的有序文件，找出一个不在文件中的32位整数（文件中至少缺失一个这样的数），仅使用常数个变量和几百字节的内存。

2、将一个具有 $n$ 个元素的一维数组向左旋转（循环移位）$i$ 个位置。

3、给定一个英语字典，找出其中所有的变位词集合。例如，”pots”, “stop”, “tops”互为变位词。

第三章数据决定程序结构

程序员在节省空间方面无计可施时，将自己从代码中解脱出来，退回起点并集中心力研究数据，常常能有奇效。（数据的）表示形式是程序设计的根本。

下面是退回起点进行思考的几条原则。

1、使用数据重新编写重复代码

2、封装复杂结构

3、尽可能使用高级工具

4、从数据得出程序的结构

第四章编写正确的程序

编写绝对正确的程序是困难的。

第五章编程小事

专业的调试人员永远也不会忘记，无论系统的行为乍看起来多么神秘莫测，其背后总有合乎逻辑的解释。

IBM 的 Yorktown Heights 研究中心发生的一件轶事可以说明这一点。一位程序员刚刚安装了一台新的工作站。当他坐着时一切正常，但是，一旦他站起来，就不能登录系统。这种情况事百分之百可重复的：坐着时，他总可以登录系统；站着时，他总是不能登录系统。最后发现问题出在键盘上：有两个键的键帽被交换了位置，当程序员坐着时，他采用盲打的方式进行登录，此时问题没有暴露出来。但是，当他站起来的时候，就不得不看着键盘输入，也就误入歧途了。

第二部分性能

第六章程序性能分析

代码调优：使用32位单精度浮点数替代64位双精度浮点数，可以使用运行时间减半；对程序的性能监视发现98%的运行时间都花在一个函数上，可以使用汇编语言重新编写该函数，可以将运行速度提升为原来的2.5倍。

硬件：在装有加速器的机器上运行代码，或可将运行时间再次减半。

第七章粗略估算

“粗略估算”在工程院校中是标准课程，对多数从业工程师来说则是谋生的必备技能。

72 法则：假设以年利率 r% 投资一笔钱 y 年，金融版本的 ”72 法则“指出，如果 r × y = 72，那么你的投资差不多会翻一倍。

安全系数：为了补偿我们的知识局限，在估算实时软件系统性能的时候，以2、4 或 6 的系数来降低对性能的估计。

Little定律：系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积。

第八章算法设计技术

本章就一个小问题研究了四种不同的算法。

问题：求一个包含正负数的数组中连续子数组和的最大值。

$n^3$ 做法：枚举 i，j，然后再枚举 i和j之间的所有元素求和。

$n^2$ 做法：1、朴素：先枚举 i，在枚举 j 的同时求i和j之间的所有元素和；2、前缀和：先求前缀和，然后再枚举 i，j。

$nlog(n)$ 做法：把区间l，r二分出m，从 m 向 l 和 r 求最大连续和相加，然后分别求 l，m 和 m，r 进行比较。

$n$ 做法：扫描，如果连续和小于 0 则值为 0。

第九章代码调优

高速缓存原理：最经常访问的数据，其访问开销应该是最小的。

集锦：

问题一：整数取模

C语言模运算%开销约比算术运算符 +-*/ 大10倍。

问题二：函数、宏和内联代码

使用函数开销会比直接使用代码要大，C语言的宏可能使函数的运行速度增快也有可能减慢，C++的内联函数却可以稳定地增快运行速度，可以做到近似直接使用代码的情况。

问题三：顺序搜索

函数 ssearch3 对比函数 ssearch1 有两处性能改进。

int ssearch1(t)
	for i = [0, n)
		if x[i] == t
			return i
	return -1

int ssearch3(t)
	x[n] = t
	for (i = 0; ; i += 8)
		if (x[i] == t) {break;}
		if (x[i + 1] == t) {i += 1; break;}
		if (x[i + 2] == t) {i += 2; break;}
		if (x[i + 3] == t) {i += 3; break;}
		if (x[i + 4] == t) {i += 4; break;}
		if (x[i + 5] == t) {i += 5; break;}
		if (x[i + 6] == t) {i += 6; break;}
		if (x[i + 7] == t) {i += 7; break;}
	if i == n
		return -1
	else return i;

问题四：计算球面距离

输入球面上 5000 个点组成的集合S，和一个 20000 个点的询问集合Q，对于 Q 中的每个点找出 S 中距离最近的点（每个点由经度和纬度表示）。

优化：使用三角函数求出每个点的 x, y, z 坐标进行计算。

第十章节省空间

数据空间技术：1、不存储，重新计算；2、稀疏数据结构；3、数据压缩；4、分配策略；5、垃圾回收。

代码空间技术：1、函数定义；2、解释程序；3、翻译成机器语言。

第三部分应用

第十一章排序

使用库函数排序。

第十二章取样问题

本章讲述了一个随机取样小程序的故事，要求从 $n$ 个字符串中随机选择 $m$ 个不同的字符串。

一种可行方案：随机打乱字符串的顺序，选择前 $m$ 个字符串即可。

第十三章搜索

本章介绍了几种数据结构。

线性结构：数组、简单链表、链表（消除递归）、链表（组分配）。

二分搜索树：二分搜索树、箱、位向量。

第十四章堆

本章介绍了堆的实现。

第十五章字符串

本章介绍了字符串hash、平衡树、后缀数组。

编程珠玑读后感