本文關(guān)鍵詞：數(shù)據(jù)處理，由筆耕文化傳播整理發(fā)布。

十七道海量數(shù)據(jù)處理面試題與Bit-map詳解

作者：小橋流水，redfox66，July。

    本博客內(nèi)曾經(jīng)整理過有關(guān)海量數(shù)據(jù)處理的10道面試題（十道海量數(shù)據(jù)處理面試題與十個(gè)方法大總結(jié)），此次除了重復(fù)了之前的10道面試題之后，重新多整理了7道。僅作各位參考，不作它用。

    同時(shí)，程序員編程藝術(shù)系列將重新開始創(chuàng)作，第十一章以后的部分題目來(lái)源將取自下文中的17道海量數(shù)據(jù)處理的面試題。因?yàn)�，我們覺得，下文的每一道面試題都值得重新思考，重新深究與學(xué)習(xí)。再者，編程藝術(shù)系列的前十章也是這么來(lái)的。若您有任何問題或建議，歡迎不吝指正。謝謝。

1. 給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？

    方案1：可以估計(jì)每個(gè)文件安的大小為50G×64=320G，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理�？紤]采取分而治之的方法。

    方案2：如果允許有一定的錯(cuò)誤率，可以使用Bloom filter，4G內(nèi)存大概可以表示340億bit。將其中一個(gè)文件中的url使用Bloom filter映射為這340億bit，然后挨個(gè)讀取另外一個(gè)文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url（注意會(huì)有一定的錯(cuò)誤率）。

    讀者反饋@crowgns：

方案2：

    一般query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對(duì)于所有的query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用trie樹/hash_map等直接來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了

    （讀者反饋@店小二：原文第二個(gè)例子中：“找一臺(tái)內(nèi)存在2G左右的機(jī)器，依次對(duì)用hash_map(query, query_count)來(lái)統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)�！庇捎趒uery會(huì)重復(fù)，作為key的話，應(yīng)該使用hash_multimap 。hash_map 不允許key重復(fù)。@hywangw:店小二所述的肯定是錯(cuò)的，hash_map(query,query_count)是用來(lái)統(tǒng)計(jì)每個(gè)query的出現(xiàn)次數(shù) 又不是存儲(chǔ)他們的值 出現(xiàn)一次 把count+1 就行了 用multimap干什么？多謝hywangw）。

方案3：

    與方案1類似，但在做完hash，分成多個(gè)文件后，可以交給多個(gè)文件來(lái)處理，采用分布式的架構(gòu)來(lái)處理（比如MapReduce），最后再進(jìn)行合并。

3. 有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。

    方案1：順序讀文件中，對(duì)于每個(gè)詞x，取

然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。下面的代碼給出了一個(gè)BitMap的用法：排序。

//定義每個(gè)Byte中有8個(gè)Bit位 #include ＜memory.h＞ #define BYTESIZE 8 void SetBit(char *p, int posi) { for(int i=0; i ＜ (posi/BYTESIZE); i++) { p++; } *p = *p|(0x01＜＜(posi%BYTESIZE));//將該Bit位賦值1 return; } void BitMapSortDemo() { //為了簡(jiǎn)單起見，我們不考慮負(fù)數(shù) int num[] = {3,5,2,10,6,12,8,14,9}; //BufferLen這個(gè)值是根據(jù)待排序的數(shù)據(jù)中最大值確定的 //待排序中的最大值是14，因此只需要2個(gè)Bytes(16個(gè)Bit) //就可以了。 const int BufferLen = 2; char *pBuffer = new char[BufferLen]; //要將所有的Bit位置為0，否則結(jié)果不可預(yù)知。 memset(pBuffer,0,BufferLen); for(int i=0;i＜9;i++) { //首先將相應(yīng)Bit位上置為1 SetBit(pBuffer,num[i]); } //輸出排序結(jié)果 for(int i=0;i＜BufferLen;i++)//每次處理一個(gè)字節(jié)(Byte) { for(int j=0;j＜BYTESIZE;j++)//處理該字節(jié)中的每個(gè)Bit位 { //判斷該位上是否是1，進(jìn)行輸出，這里的判斷比較笨。 //首先得到該第j位的掩碼（0x01＜＜j），將內(nèi)存區(qū)中的 //位和此掩碼作與操作。最后判斷掩碼是否和處理后的 //結(jié)果相同 if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j)) { printf("%d ",i*BYTESIZE + j); } } pBuffer++; } } int _tmain(int argc, _TCHAR* argv[]) { BitMapSortDemo(); return 0; }

可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來(lái)說數(shù)據(jù)范圍是int的10倍以下

使用bit數(shù)組來(lái)表示某些元素是否存在，比如8位電話號(hào)碼

Bloom filter可以看做是對(duì)bit-map的擴(kuò)展（關(guān)于Bloom filter，請(qǐng)參見：海量數(shù)據(jù)處理之Bloom filter詳解）。

1)已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。

    8位最多99 999 999，大概需要99m個(gè)bit，大概10幾m字節(jié)的內(nèi)存即可。 （可以理解為從0-99 999 999的數(shù)字，每個(gè)數(shù)字對(duì)應(yīng)一個(gè)Bit位，所以只需要99M個(gè)Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內(nèi)存表示了所有的8位數(shù)的電話）

2)2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。

    將bit-map擴(kuò)展一下，用2bit表示一個(gè)數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時(shí)候，如果對(duì)應(yīng)位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變�；蛘呶覀儾挥�2bit來(lái)進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map，都是一樣的道理。

參考：

完。

  本文關(guān)鍵詞：數(shù)據(jù)處理，由筆耕文化傳播整理發(fā)布。