《编程珠玑》----一、开篇
by Blanche
at 2010-11-08 17:33:00
original http://www.cnblogs.com/Blanche/archive/2010/11/08/1871950.html
这一章通过一次对话引出来，对话的请教者向作者请教了一个有关于美国电话排序的问题，每个美国电话由3位“区号”，（当时只有800这一个免费的区号），后再跟7位数字，问题的具体描述是：
输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10*10*...10(共7个10相乘)，（注：很抱歉，博客里面不支持mathType里面的数据格式）
如果在输入文件中有任何整数重复出现就是致命错误，没有其他数据与该整数相关联。
输出：按升序排序的输入整数的列表
约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。
解决方法：
1. 一般的方法，
以一般的基于磁盘的归并排序程序为起点，对其调整，可将原来的程序减少为几十行，同时使程序运行得更快，但完成运行可能仍然需要几天时间。
2. 利用该问题的特殊性。
若每个号码使用7个字节存储，可在1M存储空间里大约存143 000个号码，
若每个号码使用32位（4个字节）整数来表示，可在1M存储空间存250 000个号码，需遍历文件40趟。
第一趟：0~249 999之间任何号码， 先读入内存，排完序后写到输出文件中。
第二趟：250 000~499 999之间的整数。。。。。。。。
。。。。。。。
内存排序，仅需20行代码，该程序的特性是不必考虑中间磁盘文件，但是代价是读取输入文件40次。
3. 神奇的算法
使用位图或位向量的集合。可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，
如：可用字符串来表示集合{1,2,3,5,8,13}：01110100100001000000 代表集合中数值的位置1，其他位置0
实际问题，每个7位十进制正数表示一个小于1 000万的整数，使用一个具有1 000万个位的字符串来表示这个文件，其中，当且仅当整数 i 在文件中存在时，第 i
位为1,。这种表示利用了该问题的三个在排序问题中不常见的属性：输入数据限制在相对较小的范围内；数据没有重复；而且对于每条记录而言，除了单一整数 外，没有任何其他关联数据。
若给定表示文件中整数集合的位图数据结构，则可以分三个自然阶段来编写。第一阶段，将所有位都置0，从而将集合初始化为空；第二阶段，通过读入文件 中的每个整数来建立集合，将每个对应的位都置为1；第三阶段，如果该位为1，就输出对应的整数，由此产生有序的输出文件。令n为位向量中的位数（本例为 10 000 000），程序伪代码表述如下：
//phase 1: initialize set to empty
for i=[0,n)
bit[i]=0;
//phase 2: insert parent elements into the set
for each i in the put file
bit[i]=1;
//phase 3:write sorted output
for i=[0,n]
if bit[i] == 1
write i on the output file
结论：对细小问题的仔细分析有时可以得到明显的实际益处
（1）正确的问题，明确问题。
（2）位图的数据结构
（3）多趟算法
（4）时间与空间的折中与双赢
（5）简单的设计
这一章的这个问题，作者根据实际问题进行细致的分析，最后得到使用位操作来进行处理，相当的巧妙，该方法不但简化了程序，提高了运行速度，也容易实现。
高人，呵呵，以后也要学会使用位来解决某些问题。
作者: Blanche 发表于 2010-11-08 17:33 原文链接
最新新闻：
· 微软将与6大硬件厂商联合提供云计算参考架构(2010-11-09 09:21)
· 羊城晚报：网络红人炒作流程揭秘(2010-11-09 09:12)
· 《华盛顿邮报》发布iPad应用 定价2美元(2010-11-09 09:09)
· 微软大力推广Windows Phone 7手机(2010-11-09 09:07)
· 传AOL邀请美国银行协助并购雅虎(2010-11-09 09:06)
编辑推荐：我们的测试驱动开发经验