bit-map再顯身手：test.txt中有42億個無符號整數， 求不存在于test.txt中的最小無符號整數。限制： 可用內存為600MB....

? ? ? ? 先看看這個題目：test.txt中有42億個無符號整數， 求不存在于test.txt中的最小無符號整數. 限制： 可用內存為600MB. ?

? ? ? ?又是大數據。 看到42億， 有靈感沒？ 要知道， 2的32次方就是42億多一點點啊。42億個無符號整數存在于文件里。 我們能夠考慮在內存中用bit-map與之建立二值狀態映射。 2的32次方個無符號整數。 須要內存空間為512M, 這個是非常easy計算的。

? ? ? ?這么大的空間。 要用棧數組肯定不行。 可考慮用堆。

還是我們之前介紹過的bit-map, ?用不著多說（別說我不描寫敘述思路啊， 代碼就體現了思路）， 直接給出代碼：

#include <iostream>
#include <fstream>
using namespace std;#define BIT_INT 32   // 1個unsigned int能夠標志32個坑
#define SHIFT 5
#define MASK 0x1f
#define N 4294967296 // 2的32次方unsigned int *a = NULL;// 必須用堆
void createArr()
{a = new unsigned int[1 + N / BIT_INT];
}void deleteArr()
{delete []a;a = NULL;
}// 將全部位都初始化為0狀態
void setAllZero()
{memset(a, 0, (1 + N / BIT_INT) * sizeof(unsigned int));
}// 設置第i位為1
void setOne(unsigned int i)
{a[i >> SHIFT] |= (1 << (i & MASK));
}// 設置第i位為1
void setZero(unsigned int i)
{a[i >> SHIFT] &= ~(1 << (i & MASK));
}// 檢查第i位的值
int getState(unsigned int i)
{return (a[i >> SHIFT] & (1 << (i & MASK))) && 1;
}void setStateFromFile()
{ifstream cin("test.txt");  // 我測試的時候， 文件里的數據為：7 8 9 2 5 2 6 0 1 4 unsigned int n;while(cin >> n)  {  setOne(n);}  
}void printResult()
{unsigned int i = 0;for(i = 0; i < N; i++){if(0 == getState(i)){cout << i << endl; // 3break;}}	
}int main() 
{createArr();setAllZero();setStateFromFile();printResult();deleteArr();return 0;
}

? ? ? ?結果與預期相符。 ?我們在測試的時候， 用的數據較小。 有興趣的朋友能夠把數據量加大， 進行測試。

? ? ? ?OK, 無非又是利用bit-map來節省空間而已， 事實上非常easy。

本文先介紹到這里了。