|
一、定義
位圖法就是bitmap的縮寫。所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的。在STL中有一個(gè)bitset容器，引用bitset介紹：
A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, ...).The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.
二、數(shù)據(jù)結(jié)構(gòu)
unsigned int bit[N];
在這個(gè)數(shù)組里面，可以存儲(chǔ) N * sizeof(int)個(gè)數(shù)據(jù)，但是最大的數(shù)只能是N * sizeof(int) - 1。假如，我們要存儲(chǔ)的數(shù)據(jù)范圍為0-15，則我們只需要使得N=1，這樣就可以把數(shù)據(jù)存進(jìn)去。如下圖：
數(shù)據(jù)為【5，1，7，15，0，4，6，10】，則存入這個(gè)結(jié)構(gòu)中的情況為
三、相關(guān)操作
1，寫入數(shù)據(jù)
定義一個(gè)數(shù)組： unsigned char bit[8 * 1024];這樣做，能存 8K*8=64K 個(gè) unsigned short 數(shù)據(jù)。bit
存放的字節(jié)位置和位位置（字節(jié) 0~8191 ，位 0~7 ）
比如寫 1234 ，字節(jié)序： 1234/8 = 154; 位序： 1234 &0b111 = 2 ，那么 1234 放在 bit 的下標(biāo) 154 字節(jié)處，把該字節(jié)的 2 號(hào)位（ 0~7）置為 1
字節(jié)位置： int nBytePos =1234/8 = 154;
位位置： int nBitPos = 1234 & 7 = 2;
[cpp]
// 把數(shù)組的 154 字節(jié)的 2 位置為 1
unsigned short val = 1<<nBitPos;
bit[nBytePos] = bit[nBytePos] |val; // 寫入 1234 得到arrBit[154]=0b00000100
// 把數(shù)組的 154 字節(jié)的 2 位置為 1
unsigned short val = 1<<nBitPos;
bit[nBytePos] = bit[nBytePos] |val; // 寫入 1234 得到arrBit[154]=0b00000100
再比如寫入 1236 ，
字節(jié)位置： int nBytePos =1236/8 = 154;
位位置： int nBitPos = 1236 & 7 = 4
[cpp]
// / 把數(shù)組的 154 字節(jié)的 4 位置為 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100
// / 把數(shù)組的 154 字節(jié)的 4 位置為 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100函數(shù)實(shí)現(xiàn)：
[cpp]
#define SHIFT 5
#define MAXLINE 32
#define MASK 0x1F
void setbit(int *bitmap, int i){
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
#define SHIFT 5
#define MAXLINE 32
#define MASK 0x1F
void setbit(int *bitmap, int i){
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}2，讀指定位
[cpp]
bool getbit(int *bitmap1, int i){
return bitmap1[i >> SHIFT] & (1 << (i & MASK));
}
bool getbit(int *bitmap1, int i){
return bitmap1[i >> SHIFT] & (1 << (i & MASK));
} 四、位圖法的缺點(diǎn)
可讀性差
位圖存儲(chǔ)的元素個(gè)數(shù)雖然比一般做法多，但是存儲(chǔ)的元素大小受限于存儲(chǔ)空間的大小。位圖存儲(chǔ)性質(zhì)：存儲(chǔ)的元素個(gè)數(shù)等于元素的最大值。比如， 1K 字節(jié)內(nèi)存，能存儲(chǔ) 8K 個(gè)值大小上限為 8K 的元素。（元素值上限為 8K ，這個(gè)局限性很大?。┍热?，要存儲(chǔ)值為 65535 的數(shù)，就必須要 65535/8=8K 字節(jié)的內(nèi)存。要就導(dǎo)致了位圖法根本不適合存 unsigned int 類型的數(shù)（大約需要 2^32/8=5 億字節(jié)的內(nèi)存）。
位圖對(duì)有符號(hào)類型數(shù)據(jù)的存儲(chǔ)，需要 2 位來表示一個(gè)有符號(hào)元素。這會(huì)讓位圖能存儲(chǔ)的元素個(gè)數(shù)，元素值大小上限減半。 比如 8K 字節(jié)內(nèi)存空間存儲(chǔ) short 類型數(shù)據(jù)只能存 8K*4=32K 個(gè)，元素值大小范圍為 -32K~32K 。
五、位圖法的應(yīng)用
1、給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中
首先，將這40億個(gè)數(shù)字存儲(chǔ)到bitmap中，然后對(duì)于給出的數(shù)，判斷是否在bitmap中即可。
2、使用位圖法判斷整形數(shù)組是否存在重復(fù)
遍歷數(shù)組，一個(gè)一個(gè)放入bitmap，并且檢查其是否在bitmap中出現(xiàn)過，如果沒出現(xiàn)放入，否則即為重復(fù)的元素。
3、使用位圖法進(jìn)行整形數(shù)組排序
首先遍歷數(shù)組，得到數(shù)組的最大最小值，然后根據(jù)這個(gè)最大最小值來縮小bitmap的范圍。這里需要注意對(duì)于int的負(fù)數(shù)，都要轉(zhuǎn)化為unsigned int來處理，而且取位的時(shí)候，數(shù)字要減去最小值。
4、在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個(gè)整數(shù)
參 考的一個(gè)方法是：采用2-Bitmap（每個(gè)數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）。其實(shí)，這里可以使用兩個(gè)普 通的Bitmap，即第一個(gè)Bitmap存儲(chǔ)的是整數(shù)是否出現(xiàn)，如果再次出現(xiàn)，則在第二個(gè)Bitmap中設(shè)置即可。這樣的話，就可以使用簡(jiǎn)單的1- Bitmap了。
[cpp]
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#define SHIFT 5
#define MAXLINE 32
#define MASK 0x1F
using namespace std;
// w397090770
// wyphao.2007@163.com
// 2012.11.29
void setbit(int *bitmap, int i){
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
bool getbit(int *bitmap1, int i){
return bitmap1[i >> SHIFT] & (1 << (i & MASK));
}
size_t getFileSize(ifstream &in, size_t &size){
in.seekg(0, ios::end);
size = in.tellg();
in.seekg(0, ios::beg);
return size;
}
char * fillBuf(const char *filename){
size_t size = 0;
ifstream in(filename);
if(in.fail()){
cerr<< "open " << filename << " failed!" << endl;
exit(1);
}
getFileSize(in, size);
char *buf = (char *)malloc(sizeof(char) * size + 1);
if(buf == NULL){
cerr << "malloc buf error!" << endl;
exit(1);
}
in.read(buf, size);
in.close();
buf[size] = '\0';
return buf;
}
void setBitMask(const char *filename, int *bit){
char *buf, *temp;
temp = buf = fillBuf(filename);
char *p = new char[11];
int len = 0;
while(*temp){
if(*temp == '\n'){
p[len] = '\0';
len = 0;
//cout<<p<<endl;
setbit(bit, atoi(p));
}else{
p[len++] = *temp;
}
temp++;
}
delete buf;
}
void compareBit(const char *filename, int *bit, vector<int> &result){
char *buf, *temp;
temp = buf = fillBuf(filename);
char *p = new char[11];
int len = 0;
while(*temp){
if(*temp == '\n'){
p[len] = '\0';
len = 0;
if(getbit(bit, atoi(p))){
result.push_back(atoi(p));
}
}else{
p[len++] = *temp;
}
temp++;
}
delete buf;
}
int main(){
vector<int> result;
unsigned int MAX = (unsigned int)(1 << 31);
unsigned int size = MAX >> 5;
int *bit1;
bit1 = (int *)malloc(sizeof(int) * (size + 1));
if(bit1 == NULL){
cerr<<"Malloc bit1 error!"<<endl;
exit(1);
}
memset(bit1, 0, size + 1);
setBitMask("file1", bit1);
compareBit("file2", bit1, result);
delete bit1;
cout<<result.size();
sort(result.begin(), result.end());
vector< int >::iterator it = unique(result.begin(), result.end());
ofstream of("result");
ostream_iterator<int> output(of, "\n");
copy(result.begin(), it, output);
return 0;
}
|
