第一章 : 开篇

有限资源下进行大批量不重复数字排序

解释

一个有限定义域内的稠密集合 , 其中每个元素最多出现一次 , 且没有其它任何数据有该元素相关联, 则可以使用 BitMap 对其进行排序。

用法

问题

一个文件中包含 n 个不重复的正整数 , 对其进行排序 , 并且严格限定内存大小 。

解法

1. 基于磁盘的归并排序 , 生成若干个中间文件, 把原本放在内存中的数据都持续化存储在磁盘上。归并时候直接拿文件进行 append 。
2. 多趟读取文件: 例如 一共10000个数字 , 第一趟遍历整个文件取得 0 ~ 250 之间的数字读进内存并排序, 第二趟 250 ~ 500 之间, 以此类推 , 一共有40趟 , 以时间换取了空间。
3. 位图实现 : 使用 n 位二进制数 , 当且仅当整数 i 存在文件中时, 第 i 位二进制为 1 。第一遍遍历文件生成位图 , 第二遍遍历位图得到排序结果。位图所占的内存大小仅为 n/8 字节 (int bitmap[] , 每个 int 4 字节, 32 bit , 能代表32个数字的存在与否情况 )。

位图数据结构实现

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int bitmap[1 + N/BITSPERWORD];

void set(int i){
    bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
void clr(int i){
    bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
}

int test(int i){
    return bitmap[i >> SHIFT] & (1 << (i & MASK));
}