案例: 一个最多包含 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.
来源: http://www.jianshu.com/p/35cc07eeb7d6