|
一、定義
位圖法就是bitmap的縮寫。所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數據，但數據狀態(tài)又不是很多的情況。通常是用來判斷某個數據存不存在的。在STL中有一個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.
二、數據結構
unsigned int bit[N];
在這個數組里面，可以存儲 N * sizeof(int)個數據，但是最大的數只能是N * sizeof(int) - 1。假如，我們要存儲的數據范圍為0-15，則我們只需要使得N=1，這樣就可以把數據存進去。如下圖：
數據為【5，1，7，15，0，4，6，10】，則存入這個結構中的情況為
三、相關操作
1，寫入數據
定義一個數組： unsigned char bit[8 * 1024];這樣做，能存 8K*8=64K 個 unsigned short 數據。bit
存放的字節(jié)位置和位位置（字節(jié) 0~8191 ，位 0~7 ）
比如寫 1234 ，字節(jié)序： 1234/8 = 154; 位序： 1234 &0b111 = 2 ，那么 1234 放在 bit 的下標 154 字節(jié)處，把該字節(jié)的 2 號位（ 0~7）置為 1
字節(jié)位置： int nBytePos =1234/8 = 154;
位位置： int nBitPos = 1234 & 7 = 2;
[cpp]
// 把數組的 154 字節(jié)的 2 位置為 1
unsigned short val = 1<<nBitPos;
bit[nBytePos] = bit[nBytePos] |val; // 寫入 1234 得到arrBit[154]=0b00000100
// 把數組的 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]
// / 把數組的 154 字節(jié)的 4 位置為 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100
// / 把數組的 154 字節(jié)的 4 位置為 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100函數實現：
[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));
} 四、位圖法的缺點
可讀性差
位圖存儲的元素個數雖然比一般做法多，但是存儲的元素大小受限于存儲空間的大小。位圖存儲性質：存儲的元素個數等于元素的最大值。比如， 1K 字節(jié)內存，能存儲 8K 個值大小上限為 8K 的元素。（元素值上限為 8K ，這個局限性很大?。┍热?，要存儲值為 65535 的數，就必須要 65535/8=8K 字節(jié)的內存。要就導致了位圖法根本不適合存 unsigned int 類型的數（大約需要 2^32/8=5 億字節(jié)的內存）。
位圖對有符號類型數據的存儲，需要 2 位來表示一個有符號元素。這會讓位圖能存儲的元素個數，元素值大小上限減半。 比如 8K 字節(jié)內存空間存儲 short 類型數據只能存 8K*4=32K 個，元素值大小范圍為 -32K~32K 。
五、位圖法的應用
1、給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中
首先，將這40億個數字存儲到bitmap中，然后對于給出的數，判斷是否在bitmap中即可。
2、使用位圖法判斷整形數組是否存在重復
遍歷數組，一個一個放入bitmap，并且檢查其是否在bitmap中出現過，如果沒出現放入，否則即為重復的元素。
3、使用位圖法進行整形數組排序
首先遍歷數組，得到數組的最大最小值，然后根據這個最大最小值來縮小bitmap的范圍。這里需要注意對于int的負數，都要轉化為unsigned int來處理，而且取位的時候，數字要減去最小值。
4、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數
參 考的一個方法是：采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）。其實，這里可以使用兩個普 通的Bitmap，即第一個Bitmap存儲的是整數是否出現，如果再次出現，則在第二個Bitmap中設置即可。這樣的話，就可以使用簡單的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;
}
|
