推荐订阅源

《编程珠玑》第一章

问题一：一个文件包含了10,000,000个记录，每个记录的内容是7位的整数。记录不会重复。需要一个程序来读取文件内容，需要将这些记录排序后输出文件，内存限制1M左右。

解答：由于记录不会重复，因此每个记录用一个bit标示，就可以很简单的完成记录的标记和排序。这样需要大约1.25M的内存，时间和空间都不大。

/* Phase 1: initialize set to empty */
for i = [0, n)
    bit[i] = 0
/* Phase 2: insert present elements into the set */
for each i in the input file
    bit[i] = 1
/* Phase 3: write sorted output */
for i = [0, n)
    if bit[i] = 1
        write i on the output file

问题二：问题一中，如果严格限定不能超过1M的内存呢？

解答：多通道进行，以时间换空间。扫描两遍源文件，第一次只检查0x7FFFFFFF以下的数值，标记并输出；第二次读取源文件，此时只记录和检查0x80000000以上的数值，标记并输出。这样需要大约0.63M的内存。

问题三：问题一中，如果每个整数不是最多出现一次，而是最多出现十次呢？

解答：那就需要通过4个bit来记录每个记录，而不是之前的1个bit。这样，内存占用需要扩大四倍。如果仍然保持不变的内存限制，那就只好继续划分多个通道分别处理了。

问题四：问题一中，如果能减少初始化整段bit数组的时间？

解答：两个方法。

方法一：将bit数组定义为没有手动初始化的全局变量，将其编译到bss段中。这样，程序被栽入内存的时候，操作系统自动会将bss段的内容置0。也就是说，可以将系统运行时占用的时间，提前到系统被加载时。

方法二：（书上的解法 ）设整段数组的元素个数为n，数组为data。另定义两个包含n个元素的数组from和to，初始化全局变量t=0。

当需要设置data[i]的数值前，执行以下代码: 

from[i]  = t;
to[t]    = i;
data[i]  = 0;
t++;

这样可以只设置需要设置的元素项，并通过from、to和全局变量t来共同保证数据可靠性，替代通常的把整段数组memset的做法。

偶对书上提供的方法二有疑问：在i和t可能较大的情况下，from和to数组的元素类型就不得不设置为unsigned long，这样耗用的内存未免过大，相比而言真正需要操作的data数组的每个元素仅占1个bit。这样是不是有点得不偿失？