海量數(shù)據(jù)處理系列之:用C++實現(xiàn)Bitmap算法

更新時間：2013年05月29日 09:37:25 作者：

本篇文章是對用C++實現(xiàn)Bitmap算法進行了詳細的分析介紹，需要的朋友參考下

bitmap是一個十分有用的結構。所謂的Bit-map就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。
適用范圍：可進行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下
基本原理及要點：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼
擴展：bloom filter可以看做是對bit-map的擴展
問題實例：
1)已知某個文件內包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。
8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內存即可。
2)2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內存空間不足以容納這2.5億個整數(shù)。
將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上?；蛘呶覀儾挥?bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map。
下面是一個簡單的Bitmap的實現(xiàn)：

復制代碼代碼如下:

#include "stdafx.h"
#include <iostream>
using namespace std;
char *g_bitmap = NULL;  
int g_size = 0;  
int g_base = 0; 
//功能：初始化bitmap 
//參數(shù)： size：bitmap的大小，即bit位的個數(shù) 
//      start：起始值 
//返回值：0表示失敗，1表示成功 
int bitmap_init(int size, int start)  
{  
 g_size = size/8+1;
 g_base = start;
 g_bitmap = new char[g_size];  
 if(g_bitmap == NULL)
 {
  return 0;  
 }
 memset(g_bitmap, 0x0, g_size);  
 return 1;  
}  
//功能：將值index的對應位設為1 
//index:要設的值 
//返回值：0表示失敗，1表示成功 
int bitmap_set(int index)  
{  
     int quo = (index-g_base)/8 ;  //確定所在的字節(jié)
     int remainder = (index-g_base)%8;  //字節(jié)內的偏移  
     unsigned char x = (0x1<<remainder);    
     if( quo > g_size)  
          return 0;
     g_bitmap[quo] |= x;   //所在字節(jié)內的特定位置為1  
     return 1;   
}  

//功能：取bitmap第i位的值 
//i：待取位 
//返回值：-1表示失敗，否則返回對應位的值 
int bitmap_get(int i)  
{  
 int quo = (i)/8 ;  
 int remainder = (i)%8;  
 unsigned char x = (0x1<<remainder);  
 unsigned char res;  
 if( quo > g_size)  
  return -1;  
 res = g_bitmap[quo] & x;  
 return res > 0 ? 1 : 0;   
}  

 //功能：返回index位對應的值   
int bitmap_data(int index)  
{  
 return (index + g_base);  
}  
//釋放內存 
int bitmap_free()  
{  
 delete [] g_bitmap;
 return 0;
}    

int _tmain(int argc, _TCHAR* argv[]) 
{  
 int a[] = {5,8,7,6,3,1,10,78,56,34,23,12,43,54,65,76,87,98,89,100};  
    int i;  
 bitmap_init(100, 0);  
 for(i=0; i<20; i++)
 {
  bitmap_set(a[i]);  
 }
 for(i=0; i<=100; i++)  
 {  
  if(bitmap_get(i) > 0 )  
   cout << bitmap_data(i)<< " ";
 }  
 cout << endl;  
 bitmap_free(); 
    return 0;  
}  

【問題實例】
1)已知某個文件內包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。
8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內存即可。（可以理解為從0-99 999 999的數(shù)字，每個數(shù)字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內存表示了所有的8位數(shù)的電話）
2)2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)，內存空間不足以容納這2.5億個整數(shù)。
將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時候，如果對應位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個 2bit-map，都是一樣的道理。

您可能感興趣的文章: