日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

分享

數(shù)據(jù)結(jié)構(gòu):位圖法

 精髓_感知力 2015-08-03

一、定義

       位圖法就是bitmap的縮寫。所謂bitmap,就是用每一位來(lái)存放某種狀態(tài),適用于大規(guī)模數(shù)據(jù),但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來(lá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 位來(lái)表示一個(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ù),沒排過(guò)序的,然后再給一個(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)過(guò),如果沒出現(xiàn)放入,否則即為重復(fù)的元素。

       3、使用位圖法進(jìn)行整形數(shù)組排序

      首先遍歷數(shù)組,得到數(shù)組的最大最小值,然后根據(jù)這個(gè)最大最小值來(lái)縮小bitmap的范圍。這里需要注意對(duì)于int的負(fù)數(shù),都要轉(zhuǎn)化為unsigned int來(lái)處理,而且取位的時(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無(wú)意義)。其實(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; 

}

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,所有內(nèi)容均由用戶發(fā)布,不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花(0

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多