數據處理面試題(3)

數據處理面試題(3)

　　}

　　*p = *p|(0x01<<(posi%BYTESIZE));//將該Bit位賦值1

　　return;

　　}

　　void BitMapSortDemo()

　　{

　　//為了簡單起見，我們不考慮負數

　　int num[] = {3,5,2,10,6,12,8,14,9};

　　//BufferLen這個值是根據待排序的數據中最大值確定的

　　//待排序中的最大值是14，因此只需要2個Bytes(16個Bit)

　　//就可以了。

　　const int BufferLen = 2;

　　char *pBuffer = new char[BufferLen];

　　//要將所有的Bit位置為0，否則結果不可預知。

　　memset(pBuffer,0,BufferLen);

　　for(int i=0;i<9;i++)

　　{

　　//首先將相應Bit位上置為1

　　SetBit(pBuffer,num[i]);

　　}

　　//輸出排序結果

　　for(int i=0;i

　　{

　　for(int j=0;j

　　{

　　//判斷該位上是否是1，進行輸出，這里的判斷比較笨。

　　//首先得到該第j位的掩碼(0x01<< p="">

　　//位和此掩碼作與操作。最后判斷掩碼是否和處理后的

　　//結果相同

　　if((*pBuffer&(0x01<

　　{

　　printf("%d ",i*BYTESIZE + j);

　　}

　　}

　　pBuffer++;

　　}

　　}

　　int _tmain(int argc, _TCHAR* argv[])

　　{

　　BitMapSortDemo();

　　return 0;

　　}

　　可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

　　基本原理及要點

　　使用bit數組來表示某些元素是否存在，比如8位電話號碼

　　擴展

　　Bloom filter可以看做是對bit-map的擴展(關于Bloom filter，請參見：海量數據處理之Bloom filter詳解)。

　　問題實例

　　1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

　　8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。 (可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內存表示了所有的8位數的電話)

　　2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

　　將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上，在遍歷這些數的時候，如果對應位置的值是0，則將其置為1;如果是1，將其置為2;如果是2，則保持不變。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

【數據處理面試題(3)】相關文章：

IT數據處理員英文求職信06-08

Microsoft面試題09-04

iOS面試題07-10

公司面試題09-12

hibernate面試題10-18

英語面試題精選06-13

小升初面試題06-10

PHP面試題10-14

IT行業有關數據處理的英文求職信09-25

小升初面試題型08-24