002 bitmap海量數據的快速查找和去重

002 bitmap海量數據的快速查找和去重

題目描述

如果你只有10MB的內存呢？

對於40億個整數，如果直接用int數組來表示的大約要用40*10^8*4B=16GB,超出了內存要求，這裡

我們可以用bitmap來解決，bitmap基本思想是一位表示一個整數，比如我們有6個數據：

7 3 1 5 6 4

假設bitmap容量為8，當插入7時 bit[7]=1,一次類推

bit[3]=1

bit[1]=1

bit[5]=1

......

bit[4]=1

這樣我們查詢5，只需要查看bit[5]==1側存在，否則不存在。

這樣一個位代表一個數據，那40一個數據大概要40*10^8*bit = 0.5GB,滿足內存要求。

首先我們用int來表示：int bmap[1+N/32]; //N是總數，N=40億，一個int32bit

然後我們插入一個整數val，要先計算val位於數組bmap中的索引:index = val/32;

比如整數33，index=33/32=1,第33位於數組中的index=1

比如整數67，index=67/32=2,位於數組中index=2

然後在計算在這個index中的位置，因為數組中的每個元素有32位

33，index=1，在1中的位置為33%32=1

67，index=2，在2中的位置為67%32=3

然後就是標識這個位置為1：

bmap[val/32] |= (1<<(val%32));

33: bmap[1] != (1<<1);//xxxxxx1x,紅絲位置被置為1

67: bmap[2] != (1<<3);//xxxx1xxx

代碼：

void setVal(int val)
{
	bmap[val/32] |= (1<<(val%32));
	//bmap[val>>5] != (val&0x1F);//這個更快？
}

比如我們檢測33，同樣我們需要計算index，以及在index元素中的位置

33: index = 1, 在bmap[1]中的位置為 1，只需要檢測這個位置是否為1

bmp[1] &(1<<1),這樣是1返回true，否側返回false

67:bmp[2]&(1<<3)

127:bmp[3]&(1<<31)

代碼：

bool testVal(int val)
{
	return bmap[val/32] & (1<<(val%32));
	//return bmap[val>>5] & (val&0x1F);
}

const int N      = MaxN;
const int BitLen = 32;
int bmap[1+N/BitLen];

void setVal(int val)
{
	bmap[val/BitLen] |= (1<<(val%BitLen));
}

bool testVal(int val)
{
	return bmap[val/BitLen] & (1<<(val%BitLen));
}

void funTest()
{
	int a[] = {1, 2, 3, 4, 6, 7};

	for (int i=0; i<6; ++i)
	{
		setVal(a[i]);
	}

	std::cout << testVal(5) << std::endl;
	return 0;
}

這當然不能用bitmap來直接計算。因為從40億數據找出一個不存在的數據，我們可以將這麼多的數據分成許

多塊， 比如每一個塊的大小是1000，那麼第一塊保存的就是0到999的數，第2塊保存的就是1000 到1999的數……

實際上我們並不保存這些數，而是給每一個塊設置一個計數器。 這樣每讀入一個數，我們就在它所在的塊對應的計數器加1。

處理結束之後， 我們找到一個塊，它的計數器值小於塊大小(1000)， 說明了這一段裡面一定有數字是文件中所不包含的。然後我們單獨處理
這個塊即可。接下來我們就可以用Bit Map算法了。我們再遍歷一遍數據， 把落在這個塊的數對應的位置1(我們要先把這個數
歸約到0到blocksize之間)。 最後我們找到這個塊中第一個為0的位，其對應的數就是一個沒有出現在該文件中的數。)

代碼如下（一個測試的代碼）：

const int N           = 1000;
const int BITLEN      = 32;
const int BLOCK_SIZE  = 100;

int Bucket[1+N/BLOCK_SIZE]={0};
int BitMap[1+BLOCK_SIZE/BITLEN] = {0};

void test()
{
	//生成測試數據
	freopen("test.txt", "w", stdout);
	for (int i=0; i<1000; ++i)
	{
		if (i == 127) 
		{
			printf("0\n");
			continue;
		}
		printf("%d\n", i);
	}
	fclose(stdout);

	//讀入測試數據
	freopen("test.txt", "r", stdin);
	int Value;
	while (scanf("%d", &Value) != EOF)
	{
		++Bucket[Value/BLOCK_SIZE]; //測試數據分段累計
	}
	fclose(stdin);

    //找出累計計數小於BLOCK_SIZE的
	int Start=-1, i;
	for (i=0; i<1+N/BLOCK_SIZE; ++i)
	{
		if (Bucket[i] < BLOCK_SIZE)
		{
			Start = i*BLOCK_SIZE;
			break;
		}
	}
	if (i == 1+N/BLOCK_SIZE || Bucket[N/BLOCK_SIZE]==0 && i==N/BLOCK_SIZE) return;
    int End = Start + BLOCK_SIZE-1;

	//在不滿足的那段用bitmap來檢測
	freopen("test.txt", "r", stdin);
	while (scanf("%d", &Value) != EOF)
	{
		if (Value >= Start && Value <= End)//Value必須滿足在那段
		{
			int Temp = Value - Start;
			BitMap[Temp/BITLEN] |= (1<<(Temp%BITLEN));
		}
	}
	fclose(stdin);

	//找出不存在的數
	freopen("re.txt", "w", stdout);
	bool Found = false;
	for (int i=0; i<1+BLOCK_SIZE/BITLEN; ++i)
	{
		for (int k=0; k < BITLEN; ++k)
		{
			if ((BitMap[i] & (1<







參考：http://hawstein.com/posts/12.3.html



關於數據的去重這裡有一遍很好的文章是用bitmap來實現：
http://blog.csdn.net/hguisu/article/details/7880288