海量數(shù)據(jù)處理系列之:用C++實(shí)現(xiàn)Bitmap算法
更新時(shí)間:2013年05月29日 09:37:25 作者:
本篇文章是對(duì)用C++實(shí)現(xiàn)Bitmap算法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
bitmap是一個(gè)十分有用的結(jié)構(gòu)。所謂的Bit-map就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value, 而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù),因此在存儲(chǔ)空間方面,可以大大節(jié)省。
適用范圍:可進(jìn)行數(shù)據(jù)的快速查找,判重,刪除,一般來(lái)說(shuō)數(shù)據(jù)范圍是int的10倍以下
基本原理及要點(diǎn):使用bit數(shù)組來(lái)表示某些元素是否存在,比如8位電話(huà)號(hào)碼
擴(kuò)展:bloom filter可以看做是對(duì)bit-map的擴(kuò)展
問(wèn)題實(shí)例:
1)已知某個(gè)文件內(nèi)包含一些電話(huà)號(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)存即可。
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次及以上?;蛘呶覀儾挥?bit來(lái)進(jìn)行表示,我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map。
下面是一個(gè)簡(jiǎn)單的Bitmap的實(shí)現(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位的個(gè)數(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的對(duì)應(yīng)位設(shè)為1
//index:要設(shè)的值
//返回值:0表示失敗,1表示成功
int bitmap_set(int index)
{
int quo = (index-g_base)/8 ; //確定所在的字節(jié)
int remainder = (index-g_base)%8; //字節(jié)內(nèi)的偏移
unsigned char x = (0x1<<remainder);
if( quo > g_size)
return 0;
g_bitmap[quo] |= x; //所在字節(jié)內(nèi)的特定位置為1
return 1;
}
//功能:取bitmap第i位的值
//i:待取位
//返回值:-1表示失敗,否則返回對(duì)應(yīng)位的值
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位對(duì)應(yīng)的值
int bitmap_data(int index)
{
return (index + g_base);
}
//釋放內(nèi)存
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;
}
【問(wèn)題實(shí)例】
1)已知某個(gè)文件內(nèi)包含一些電話(huà)號(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ù)的電話(huà))
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,都是一樣的道理。
適用范圍:可進(jìn)行數(shù)據(jù)的快速查找,判重,刪除,一般來(lái)說(shuō)數(shù)據(jù)范圍是int的10倍以下
基本原理及要點(diǎn):使用bit數(shù)組來(lái)表示某些元素是否存在,比如8位電話(huà)號(hào)碼
擴(kuò)展:bloom filter可以看做是對(duì)bit-map的擴(kuò)展
問(wèn)題實(shí)例:
1)已知某個(gè)文件內(nèi)包含一些電話(huà)號(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)存即可。
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次及以上?;蛘呶覀儾挥?bit來(lái)進(jìn)行表示,我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map。
下面是一個(gè)簡(jiǎn)單的Bitmap的實(shí)現(xiàn):
復(fù)制代碼 代碼如下:
#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位的個(gè)數(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的對(duì)應(yīng)位設(shè)為1
//index:要設(shè)的值
//返回值:0表示失敗,1表示成功
int bitmap_set(int index)
{
int quo = (index-g_base)/8 ; //確定所在的字節(jié)
int remainder = (index-g_base)%8; //字節(jié)內(nèi)的偏移
unsigned char x = (0x1<<remainder);
if( quo > g_size)
return 0;
g_bitmap[quo] |= x; //所在字節(jié)內(nèi)的特定位置為1
return 1;
}
//功能:取bitmap第i位的值
//i:待取位
//返回值:-1表示失敗,否則返回對(duì)應(yīng)位的值
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位對(duì)應(yīng)的值
int bitmap_data(int index)
{
return (index + g_base);
}
//釋放內(nèi)存
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;
}
【問(wèn)題實(shí)例】
1)已知某個(gè)文件內(nèi)包含一些電話(huà)號(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ù)的電話(huà))
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)文章
詳解Visual Studio 2019(VS2019) 基本操作
這篇文章主要介紹了詳解Visual Studio 2019(VS2019) 基本操作,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03VC實(shí)現(xiàn)五子棋游戲的一個(gè)算法示例
這篇文章主要介紹了VC實(shí)現(xiàn)五子棋游戲的一個(gè)算法示例,對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的朋友有一定的借鑒價(jià)值,需要的朋友可以參考下2014-08-08教你Visual?Studio?2022如何新建一個(gè)C語(yǔ)言工程(圖文詳解)
這篇文章主要介紹了Visual?Studio?2022如何新建一個(gè)C語(yǔ)言工程,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-09-09C++?LeetCode0538二叉搜索樹(shù)轉(zhuǎn)換累加樹(shù)示例
這篇文章主要為大家介紹了C++?LeetCode0538二叉搜索樹(shù)轉(zhuǎn)換累加樹(shù)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-12-12深入探討linux下進(jìn)程的最大線(xiàn)程數(shù)、進(jìn)程最大數(shù)、進(jìn)程打開(kāi)的文件數(shù)
本篇文章是對(duì)linux下進(jìn)程的最大線(xiàn)程數(shù)、進(jìn)程最大數(shù)、進(jìn)程打開(kāi)的文件數(shù)進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05