程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 海量數據處理系列之:用C++實現Bitmap算法

海量數據處理系列之:用C++實現Bitmap算法

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

#include "stdafx.h"
#include <iostream>
using namespace std;
char *g_bitmap = NULL; 
int g_size = 0; 
int g_base = 0;
//功能:初始化bitmap
//參數: size:bitmap的大小,即bit位的個數
//      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 ;  //確定所在的字節
     int remainder = (index-g_base)%8;  //字節內的偏移 
     unsigned char x = (0x1<<remainder);   
     if( quo > g_size) 
          return 0;
     g_bitmap[quo] |= x;   //所在字節內的特定位置為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位數字,統計不同號碼的個數。
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,都是一樣的道理。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved