bitmap实现大数据排序和去重

要点：

假如有10亿元素，全部数据读进内存，占用 1000000000 * 4 / 1024 / 1024 /1024 ≈ 3.725 G，爆炸！

解决方法：

bitmap算法，每一位都能表示一位数字，10000000000 / 8 / 1024 / 1024 / 1024 ≈ 0.116 G，节约了31倍的空间！

代码：

#define SIZEBIT 1000000000  #define SIZE SIZEBIT/32 + 1 

void cleanAll(unsigned int* bitmap)
{
	for (int i = 0; i 		bitmap[i] = 0;
}

void set(unsigned int* bitmap, unsigned int index)
{
	bitmap[index / 32] |= 1 <}

void clean(unsigned int* bitmap, unsigned int index)
{
	bitmap[index / 32] &= ~(1 <}

int get(unsigned int* bitmap, unsigned int index)
{
	return bitmap[index / 32] & (1 <}

void sort(vector &a)       // 将元素存入bitmap数组中，元素其实自动排序，只要bit == 1，即说明有此元素。
{
	unsigned int bitmap[SIZE];
	cleanAll(bitmap);

	for (int i = 0; i 	{
		set(bitmap, a[i]);
	}

	for (int i = 0; i 	{
		if (get(bitmap, i))
		    cout <	}
}
int main()
{
	vector a = { 1, 3, 2, 5, 2 };
	sort(a);    // 输出 1 2 3 5 
        system("pause");
	return 0;
}