《编程珠玑》(Programming Peals)这本书买了很久了，买回来看了第一栏之后就一直没看过，这次决定每天看一个专栏（column），争取在这个月内看完。
今天从Column 1看起，这次专栏讲了一个很简单的问题：How do I sort a disk file?
问题经过一番分析后可以描述如下：
输入：一个包含有最多n个正整数的文件，每一个数都小于n，而n = 107，输入中任意整数都不会出现两次，同时每个数都没有其他的数据与之关联。
输出：一个升序排列的列表
限制条件：内存中最到只有1 Mb的存储容量可用，磁盘容量是足够的。运行时间必须最多不超过几分钟，10秒的运行时间即足够了。
一般来讲，可以想到两种方法：
1. Merge Sort（归并排序）
归并排序需要使用额外的Work Files，而且需要对它读写很多次，尽管只读过一次输入文件。（如下图所示）
2. 40-pass 算法
我们把每个数字表示成一个32位的整数，那么就可以在1Mb里面存放250,000个数字了。但是这样我们还是要读取输入文件40次（make 40 passes）。第一次，把0到249,999之间的数字读取到内存中，对其进行排序然后写到输出文件中。第二次，排序250,000到499,999的数字，就这样一直到最后第40次，从9,750,000到9,999,999进行排序。排序是用快速排序(quick sort)进行的。（如下图所示）
那么，为什么不把两者的优点结合起来呢，也就是说仅读取一次输入文件，而且不使用中间文件！
答案就是使用bitmap或者bit vector：
我们可以用一个20位的string来表示小于20的所有非负整数，例如，{1,2,3,5,8,13}可以表示成:
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
1所在的位置表示数字。
这个问题同样可以用这种思路，那么伪代码可以写成：
这样就可以很巧妙地解决了拥有如此巨大数目的问题。
文章后面介绍了几个解决问题的原则：
1. The Right Problem.解决正确的问题，问题分析清楚了就是成功的开端
2. The Bitmap Data Structure. 这个数据结构在每个元素最多出现一次而且没有其他关联数据时候非常管用。
3. Multiple-Pass Algorithms. 这些算法通常会对输入数据读取好多次
4. A Time-Space Tradeoff and One That Isn’t. 时间与空间的交换是算法中永恒的话题，不过有的时候并不是必然的，例如空间的减少也会导致时间的减少，因为需要更少地时间处理更少的数据，同时少量的数据可以放在内存中而不用读取磁盘！
5. A Simple Design. 简单的程序通常比复杂的更加可靠、安全、健壮、有效，而且易于建立与维护！
/***************************花絮******************************/
在专栏的课后习题中的最后一题，提到了已经被传遍了的在太空中使用铅笔和太空笔的故事，原来那仅仅是个传说，真实的情况是美国人最开始也是用的铅笔，后来太空笔发明之后卖给了NASA和俄国佬，可见传说并不可信，真相可猛击这里。
/***************************花絮******************************/
全文完。EOF
/* 原创文章，本文采用 BY-NC-SA 协议进行授权. 转载请注明转自: Swarm’s Blog*/
