《编程珠玑》

第一部分 基础

第1章 开篇

问题抽象描述：对10^7个正整数进行排序，只能使用1MB左右的内存空间

解决方案：使用位图，每个比特位代表一个整数，如果出现该整数则将该位置为1.

应用：该方法适合输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一的整数外，没有任何其他关联数据。位图的数据结构，描述了一个有限定义域内的稠密集合。

第2章 啊哈！算法

问题抽象描述：
A.找出一个不在40亿个随机排列的32位整数的顺序文件中的数，仅有几百字节的内存
B.将一个n元一维向量向左选装i个位置，仅有数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转
C.找出一个英语字典所有变位词集合。(pots,ptos, stop这种变位词)

解决方法：
A.二分搜索：采用已知包含至少一个缺失元素的一系列整数作为范围，并使用包含所有这些整数在内的文件表示这个范围。通过统计中间点之上和之下的元素来探测范围；或者上面或者下面的范围具有至多全部范围的一般元素。由于整个范围中有一个缺失元素，因此我们所需的那一半范围中必须也包含缺失的元素。
B.其中以前在很多地方都看到过这个方法，从ab开始，首先对a求逆得到c，然后对b求逆得到d，最后整体求逆，就得到ba了，然后各段的逆又可以在内部再次求逆，以此递归。
C.标识字典中的每一个词，使得在相同变位词类中的单词具有相同的标识。

第3章 数据决定程序结构

对数据结构所带来的方便进行了一些简述，这些在当今高级语言中都有所体现。

第4章 编写正确的程序

本章通过一些证明方法来证明了一个算法的正确性，由于我已经在《算法导论》里面饱受了数学的折磨了，这张直接跳过了，完全看不懂。

本章还介绍了一种用于检验程序正确性的方法，断言(assertion)或者叫不变式(invariant)。由于输入、程序变量和输出之间的关系勾勒出了程序的“状态”，断言使得程序猿可以准确阐述这些关系。

第5章 编程小事

本章写了一些测试的方法，不过都是手动进行测试。毋庸置疑，测试在编程中绝不是小事，特别是大型项目的开发，作者以小见大，说明了测试对于系统的稳定性和优化所带来的重大影响。

第二部分 性能

第6章 程序性能分析

从设计层面将程序性分为了几个方面：问题定义、系统结构、算法和数据结构、代码调优、系统软件、硬件。也有一个简单的分析方法就是看算法的复杂度，用O来表示那种。

第7章 粗略估算

本章使用生活中大量的例子来描述如何进行粗略估算，最近正好在看《蝎子网络》，发现我的数学功底越来越差，实际生活中有大量的使用估算的地方，比如，验证一些生活常识、验证一些新闻的正确性等。日常生活中的速算。

粗略估算的一些基本技巧：快速检验、经验法则(72法则)。还有一些估算定律：Little定律(队列中物体的平均数量为进入速率与平均停留时间的乘积。)

第8章 算法设计的技术

本章主要讲述了分治算法，这一算法我曾在算法导论上看过。

本章还介绍了几个重要的算法设计技术：保存状态，避免重复计算；将信息预处理至数据结构中；分治算法；扫描算法；累计；下界。

第9章 代码调优

本章介绍了优化代码的一些简单的思想和方法。例如将最常见类型的空闲记录缓存在一个链表中。然后，就可以通过对该链表的快速访问来处理常见的请求，而不必调用通用的内存分配程序。恰当使用函数、宏和内联代码。

”代码调优的最重要的原理就是尽量少用它.“

第十章 节省空间

Unix操作系统发明者(Dennis Ritchie和Ken Thompson)在论文中说道：“在系统及其软件方面，总是存在着相当严重的空间约束。如果同时对合理的效率和强大的能力提出要求，那么空间约束不仅具有经济上的意义，还会使设计更优雅一些。”

其实节省空间在所有地方都可以看到，比如在最初定义一个整数位数的时候，我一直使用的是int，但是如果要节约空间就使用其他的一些分配方法。

hash(散列表)特别适合某些稀疏场合。

如果一定要消耗时间来节省空间，在有些变量的计算上选择不存储，重新计算的方法更有效。在给变量分配内存时就使用动态分配。

第三部分 应用

第11章 排序

作者通过自己对快速排序的几种方法的改进超越了库函数。就像其他任何强大的工具一样，我们经常会在不该使用排序的时候使用排序，而在应该使用排序的时候却不使用排序。

第12章 取样问题

研究的一个问题就是输出随机数，虽然很多语言都提供了类似的随机函数，但是感觉目前大多数语言，特别是传统语言的随机几乎都无法做到真随机，必须自己在假随机上进行修改。

第13章：搜索

线性结构；二分搜索数。并提到了库的作用，C++标准模库提供了一个实现起来很容易，并且维护和扩展也比较简单的通用解决方案。当遇到涉及数据结构的问题时，我们的第一反应应该是寻求解决问题的通用工具。当然，有些时候针对特定的问题，使用专用的算法可能会大大提高运行速度。我们还要使用代码调优方法，比如将递归函数重写为迭代版本可以使链表的速度提升为原来的3倍，对大多数结构来说，引入哨兵可以获得清晰、简单的代码，并缩短运行时间。

第14章：堆

堆其实也是一种二叉树，但其有两个不同的性质：一是顺序性，任何结点的值都小于或等于其子结点的值。第二个性质就是形状，不是完整的三角形，右下角可以缺一点。

第15章：字符串

通过单词、短语和文本几个方面来处理字符串

《编程珠玑》(续)

第一部分 编程技术

第1章 性能监视工具

通过一些常用的代码性能监视工具，如行计数性能监视、过程时间性能监视等可以查看到一个程序里面各条语句的执行情况，以查找代码中执行最慢的地方，因为“一个程序中不到4%的语句通常占用了一半以上的运行时间”。我们最应该优化的就是这个地方。

第2章 关联数组

貌似本书很多章都是使用的Awk来讲解，但是Awk中的关联数组，我感觉就很像其他脚本语言中的字典，十分方便，但awk对字符串的处理可能更加方便，不过我是不喜欢其编码风格的。

第3章 程序猿的忏悔

再次提到调试脚手架的重要性，这一点上，Awk语言确实能起到很大的帮助，“Awk是一种构造算法原型的很好的语言，其内联数组使你模拟许多常用的数组结构，它的字段、隐式循环、模式-动作对等设计极大地简化了输入输出过程，隐式的变量声明和初始化也使得程序更加简洁。”。正如Fred Brooks认为“一个软件产品中应该有一半的代码都是脚手架”。

第4章 自描述数据

作者是使用的文档生成器来描述，其实本章所说的自描述数据在某种意义上类似于其他语言的一种模版，比如留下%s等占位符，让其他变量来填充。

第二部分 实用技巧

第5章 劈开戈尔迪之结

背景：在古希腊神话中，能解开戈尔迪之结者就可以当亚细亚之王，几百年后亚历山大大帝来了。他没有重蹈覆辙，而是拔出剑来，将结直接劈开，随即征服了亚洲。从那时起，“劈开戈尔迪之结”意味着为复杂问题找出聪明的解法。

我们在寻找解决问题的方法的需要考虑如下几个问题：什么是用户真正的需求(用户要求可预测性甚于要求速度)；考虑成本与收益的平衡；别把问题弄得太复杂也别太简单；用正确的方法使用正确的工具；对员工的奖赏。。。

简单的方法谁都想要，但并不是每个人都能找得到，我们还应该考虑时间成本，别花过多时间去思考简单的方法，没准一个你目前觉得复杂的方法可以很快完成项目。

第6章 计算机科学箴言集

居然把一些计算机的箴言单独列为一章，我也是醉了。

第7章 粗略估算

在原书已经有了几乎一样的内容...

第8章 人员备忘录

大神，这是你自己的日记吗？

第三部分 人性化I/O

第9章 小语言

作者以Pic为例子讲解了一种小的语言是如何运行起来的，相信看过编译原理的同学都能理解。

第10章 文档设计

原以为是要教我们关于PRD这样的文档的写法，不过只是教了我们一些写Word文档的基本的规则，不过我觉得一个有基本审美观的人无论怎么写也不会写得很差的。

第11章 图形化输出

合理使用图形工具。

第12章 对调查的研究

也是借调查这一事件来强调模版的好处。

第四部分 算法

第13章 绝妙的取样

好吧，就是随机数的一些个问题。

第14章 编写数值计算程序

牛顿迭代，这个我倒是完全理解。本章学到重要的一点就是“在特殊的上下文环境中针对特殊目的设计的代码比通用的程序更有效”。

第15章 选择

使用分治算法来进行选择，太聪明了。