开篇
具体化你的解决的问题。下面是A和B的对话。
A：我该如何对磁盘文件进行排序？B：需要排序的内容是什么？文件中有多少条记录？每个记录的格式是什么？A：该文件包含至多10,,个记录，每条记录都是一个7位整数。B：如果文件那么小，为什么要使用磁盘排序呢？为什么不在主存中对它排序？A：该功能是某大型系统中的一部分，大概只能提供1MB主存给它。B：你能将记录方面的内容说得更详细一些吗？A：每个记录是一个7位正整数，没有其它的关联数据，每个整数至多只能出现一次。......
经过一系统的问题，我们可以将一个定义模糊不清的问题变得具体而清晰：
输入：所输入的是一个文件，至多包含n个正整数，每个正整数都要小于n，这里n=10^7。如果输入时某一个整数出现了两次，就会产生一个致命的错误。这些整数与其它任何数据都不关联。输出：以增序形式输出经过排序的整数列表。约束：大概有1MB的可用主存，但可用磁盘空间充足。运行时间至多允许几分钟，10秒钟是最适宜的运行时间。
如果主存容量不是严苛地限制在1MB，比如说可以是1MB多，或是1~MB之间，那么我们就可以一次性将所有数据都加载到主存中，用Bitmap来做。10,,个数就需要10,,位，也就是10,,b=1.5MB。
程序可分为三个部分：第一，初始化所有的位为0；第二，读取文件中每个整数，如果该整数对应的位已经为1，说明前面已经出现过这个整数，抛出异常，退出程序(输入要求每个整数都只能出现一次)。否则，将相应的位置1；第三，检查每个位，如果某个位是1，就写出相应的整数，从而创建已排序的输出文件。
如果主存容量严苛地限制在1MB，而使用Bitmap需要1.5MB，因此无法一次载入完成排序。那么，我们可以将该文件分割成两个文件，再分别用Bitmap处理。分割策略可以简单地把前一半的数据放到一个文件，后一半的数据放到另一个文件，分别排序后再做归并。也可以把文件中小于某个数(比如5,,)的整数放到一个文件，叫lss.txt，把其余的整数放到另一个文件，叫gatr.txt。分别排序后，把gatr.txt的排序结果追加到lss.txt的排序结果即可。
啊哈！算法
第章围绕3个问题展开。
给定一个包含3位整数的顺序文件，它至多只能包含40亿个这样的整数，并且整数的次序是随机的。请查找一个此文件中不存在的3位整数。在有足够主存的情况下，你会如何解决这个问题？如果你可以使用若干外部临时文件，但可用主存却只有上百字节，你会如何解决这个问题？
这是CTCI中的一道题目，详细解答请戳以下链接：请猛戳我
请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，那么向量abcdfgh旋转之后得到向量dfghabc。
这个问题很常见了，做3次翻转即可，无需额外空间：
vrs(0,i-1);//cbadfghvrs(i,n-1);//cbahgfdvrs(0,n-1);//dfghabc
给定一本英语单词词典，请找出所有的变位词集。例如，因为“pots”，“stop”，“tops”相互之间都是由另一个词的各个字母改变序列而构成的，因此这些词相互之间就是变位词。
这个问题可以分3步来解决。第一步将每个单词按字典序排序，做为原单词的签名，这样一来，变位词就会具有相同的签名。第二步对所有的单词按照其签名进行排序，这样一来，变位词就会聚集到一起。第三步将变位词分组，形成变位词集。示意图如下：
数据决定程序结构
恰当的数据视图实际上决定了程序的结构。我们常常可以通过重新组织内部数据来使程序变得小而美。
发明家悖论：更一般性的问题也许更容易解决。(有时候吧)
程序员在节省空间方面无计可施时，将自己从代码中解脱出来，退回起点并集中心力研究数据，常常能有奇效。数据的表示形式是程序设计的根本。
下面是退回起点进行思考时的几条原则：
使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构——数组来更好地表述。封装复杂结构。当需要非常复杂的数据结构时，使用抽象术语进行定义，并将操作表示为类。尽可能使用高级工具。超文本，名字-值对，电子表格，数据库，编程语言等都是特定问题领域中的强大的工具。从数据得出程序的结构。在动手编写代码之前，优秀的程序员会彻底理解输入，输出和中间数据结构，并围绕这些结构创建程序。
提到的书籍：Polya的《HowtoSolvit》，中文书《怎样解题》；Krnighan和Plaugr的《ElmntsofProgrammingStyl》；FdBrooks的《人月神话》StvMcConnll的《代码大全》；《RapidDvlopmnt》；《SoftwaProjctSurvivalGuid》
编写正确的程序
本章以二分搜索为例子，讲述了如何对程序进行验证及正确性分析。
深入阅读：DavidGris的《ScincofProgramming》是程序验证领域里极佳的一本入门书籍。
编程中的次要问题
到目前为止，你已经做了一切该做的事：通过深入挖掘定义了正确的问题，通过仔细选择算法和数据结构平衡了真正的需求，通过程序验证技术写出了优雅的代码，并且对其正确性相当有把握。万事俱备，只欠编程。
使用断言assrt自动化测试程序
进阶阅读：《PracticofProgramming》第5章(调试)，第6章(测试)《CodComplt》第5章(单元测试)，第6章(调试)
程序性能分析
下图展示了一个程序的性能提升过程，该程序的作用是对三维空间中n个物体的运动进行仿真。从图中可以看出，一个程序可以从多方面进行性能提升，而其中算法和数据结构的选择又显得尤为重要。
从设计层面提升程序性能：
问题定义。良好的问题定义可以有效减少程序运行时间和程序长度。系统结构。将大型系统分解成模块，也许是决定其性能的最重要的单个因素。算法和数据结构。这个不用说了。代码调优。针对代码本身的改进。系统软件。有时候改变系统所基于的软件比改变系统本身更容易。硬件。更快的硬件可以提高系统的性能。
深入阅读：ButlrLampson的“HintsforComputrSystmDsign”，该论文特别适合于集成硬件和软件的计算机系统设计。
粗略估算
这一章讲述了估算技术，我认为是相当有用的一章。
文中先抛出一个问题：密西西比河一天流出多少水？如果让你来回答，你会怎么答，注意不能去Googl哦。
作者是这么回答这个问题：假设河的出口大约有1英里宽和0英尺深(1/50英里)，而河水的流速是每小时5英里，也就是每天10英里。则可以计算出一天的流量：
1英里*1/50英里*10英里/天约等于1/英里^3/天
上述算式非常简单，可是在看到这些文字之前，如果有人真的问你，密西西比河一天流出多少水？你真的能答上来吗？还是愣了一下后，摆摆手，说：这我哪知道！
对于上面的问题，我们至少可以注意到以下两点：
你需要把问题转换成一个可计算的具体模型。这一点往往不需要太担心，因为我们做的是估算，所以可以忽视很多无关紧要的因素，可以去简化你的模型，记住我们要的只是一个粗略计算的结果。比如对于上面的问题，计算密西西比河一天流出多少水其实就是计算其一天的流量，利用中学所学知识，流量=截面积x流速，那我们就只需计算密西西比河的出水口的截面积和流速即可。我们可以将出水口简化成一个矩形，因此就只需要知道出水口的宽和深即可。你需要知道常识性的东西。上面我们已经把问题转换成了一个可计算的具体模型：流量=出水口宽x出水口深x流速。接下来呢？你需要代入具体的数值去求得答案。而这就需要你具备一些常识性的知识了。比如作者就估计了密西西比河的出口有1英里宽，0英尺深(如果你估计只有几十米宽，那就相差得太离谱了)。这些常识性的知识比第1点更值得