案例：一个最多包含n个正整数的磁盘文件，每个数都小于n，其中n=10^7，文件中不包含重复的数。要求输出按升序排列的输入整数的列表。 Note：最多有（大约）1MB的内存可用，有充足的磁盘空间可用。
思路与解决方案：
第一：
首先，显而易见的方法是以一般的基于磁盘的归并排序（不了解的可以请教度娘）为起点，当然可能由于一些特殊情况，对大体的程序做一个微调，但是这也丝毫不会影响这个程序可能还要运行几天的事实。
第二：
考虑到该问题的特殊性，每个数都小于10^7，且不能重复。很显然能用一个包含10 000 000个位的向量来表示所有小于10^7的正整数，出现过的数即把相应的位置1，没出现过的数即置0，这样就大大降低了程序运行时间。这种方法简而言之就是：用位图或位向量表示集合。
继续探讨，1MB最多能表示1024*1024*8约为8 000 000个位，但是这里最多包含10 000 000个元素（即使用10 000 000个位），怎无奈表示不下。这里，为了说明位向量怎么使用以及程序怎么编写，我们假设有2MB内存，在后面我们再去研究表示不下的情况。
接下来，我们来实现该程序。假设已经声明表示文件中整数集合的位向量，可以分三个步骤来编写程序。第一阶段将所有的位置0，从而将集合初始化为空；第二阶段通过读入文件中的每个整数来建立集合，将每个对应的位都置为1；第三阶段检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件。
伪代码如下：
/* 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
编写的C代码如下：
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N / BITSPERWORD]; //位向量
void set(int i) { //设置出现过的数，置1
a[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i) { //清除，将每一位置0
a[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i) { //检验某一位是否为1
return a[i >> SHIFT] & (i << (i & MASK));
}
int main(void) {
int i;
for (i = 0; i < N; i++) {
clr(i);
}
while (scanf("%d", &i) != EOF) {
set(i);
}
for (i = 0; i < N; i++) {
if (test(i)) {
printf("%d\n", i);
}
}
return 0;
}
如果你对位运算不怎么感冒（个人建议认真学习，文末我会稍微提及一下位运算），花多点时间也要吃透该code，因为实在是太精辟了，寥寥几行解决了几十年前令程序员棘手的问题。
然后，探讨用1MB内存表示不了10 000 000个位的情况。我没有给出该题的背景，如果考虑到背景的话，实际上可以将10 000 000个位降低为8 000 000个位，那么1MB可以说刚刚好；其次，我们可以采用两趟算法，首先使用5 000 000/8=625 000个字节的存储空间来排序0~4 999 999之间的整数，然后第二趟排序5 000 000~9 999 999的整数。k趟算法可以在kn的时间开销和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。
Summary：
位图数据结构。该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有任何数据结构与该元素相关联。即使这些条件没有完全满足（例如，存在重复元素或额外的数据），也可以用有限定义域内的键作为一个表项或者更复杂的表格的索引。正确理解该数据结构以及学会如何使用、在什么场合使用，如此方能得心应手。
ps：
1.将一个整数n除以2，我以前会写成 n = n / 2，但现在我会用 n = n >> 1;位运算其实是速度很快的一种运算方式，如果写成第一种方式（没有一点毛病，甚至不能太对），但是编译器会将它优化成第二种形式，所以，不用多讲，你应该能明白道理了。
2.判断一个数n是不是偶数？相信你以后不会再用 if n%2 == 0,而是会采用 if n&1 == 0。
网友评论