编程珠玑第三部分随笔——十一至十五章

第三部分是《编程珠玑》的精华，对于这块内容我建议是边读边结合实际。最好是在项目中用到了作者给出的方法，这样的理解会更加深入。我在这一部分统一做一个简单的总结，恰好很多内容曾经遇到过，不论是在项目中还是编程竞赛中。作者给出了很多经典的解决方案看起来似曾相识，这也说明了好的方法渊远流长，可能以前有人拜读过此书，并且把解决方案早早应用在了自己的项目之中。

解决现有的问题是程序员任务的一部分，另一个也许更重要的部分是做好解决未来问题的准备。有时，这种准备包括听课或者读书；不过更常见的情况是，程序员通过询问自己如何用不同的方法解决问题来得到提高。

第十一章排序

这一章节的主题就是我们最为常用的排序算法了，可以说但凡是初学计算机入门的程序员，冒泡排序往往是第一个正式的算法。本章的主人公是快速排序，我们其实在前面几章的习题中已经用过快排的思想了，如果没记错就是讲解二分算法的一章。二分算法作为可以说同样为最常用的算法之一，其前提条件就是作用对象相对有序。有序化有时会给我们带来很大的帮助。随机的快排，应该可以为你的项目提速不少。

第十二章取样问题

我觉得这是很重要的一章，特别是在大数据时代，面临的数据处理与日俱增，当我们面对在一个很大样本空间中取样时，书中的方法就很好用了。

select = m
remaining = n
for i = [0, n)
	if (bigrand() % remaining) < select
		print i
		select--
	remaining--

上面这段取样程序很巧妙，Knuth证明了其正确性，而另一种由Knuth提出的方法即是：

for i = [0, n)
	swap(i, randint(i, n - 1))

然后把前m个元素取出，想想看是不是很棒的思路？

第十三章搜索

这个就不用说了，太广泛的算法。哪里都会用到搜索，比如我们设计游戏，其中用到的寻路算法A*，最近听说有更好的解决方案了。虽然这个方法常用，但是在遇到剪枝等复杂的优化情况时，仍然要多多积累。

第十四章堆

还记得曾经写过的Dijkstra的单源最短路径算法吗？算法复杂度是多少？如果用优先队列优化后又会是多少？我们操作系统的内存管理的数据结构就用到了堆栈，而且因为堆本身良好的性质：二叉堆是完全二叉树，其实现非常漂亮简洁。此外，理论上很牛掰的裴波那契堆可以被实现很简洁的配对堆在实用中替代。值得深入研究的一个领域。

第十五章字符串

作者把这一章留作结束，也给了我一些回忆。记得小学时最后一个算法就是字符串处理，当时还写着BASIC代码。直到高中时代学会的KMP、AC自动机、Tire等之后就告一段落了。首先，字符串非常重要，可以说我们大部分工作都是围绕着文本进行了，而且字符串中模式匹配占据着一定的比例。本章作者提到了后缀数组，我觉得有必要连带后缀树一同学习一下。而生成文本部分则给了我一个惊喜。试想用一个「具有固定转换概率的有限状态马尔可夫链」去生成一个随机英文文本，且其中大部分都是真正的英文单词是多么有趣的一件事。

总结

这是一本干货充足的好书，很难得遇到这样的作品。通读过后，感觉这辈子值了~