用位圖排序無重復數(shù)據(jù)集實例代碼（C++版）

更新時間：2013年11月20日 11:01:16 作者：

本文講解如何用位圖排序無重復的數(shù)據(jù)集，我們使用C++實現(xiàn)一下這個方法

《Programming Pearls》(編程珠璣下載)第一章講述了如何用位圖排序無重復的數(shù)據(jù)集，整個思想很簡潔，今天實踐了下。

一、主要思想

位圖排序的思想就是在內(nèi)存中申請一塊連續(xù)的空間作為位圖，初始時將位圖的每一位都置為0，然后依次讀取待排序文件的整數(shù)，將整數(shù)所在的位設置為1，最后掃描位圖，如果某一位為1，則說明這個數(shù)存在，輸出到已排序文件。比如待排序的數(shù)據(jù)S={3,0,4,1,7,2,5}，max(S)=7，我們可以設置一個八位的位圖B，將位圖的每一位初始為0，即B=[0,0,0,0,0,0,0,0]，對S中的每一個整數(shù)d，設置B[d]=1，即B=[1,1,1,1,1,1,0,1]，最后掃描位圖，對位圖的每一位i,如果B[i]==1，則輸出i到已排序文件，排序后的S={0,1,2,3,4,5,7}。
整個過程只需要遍歷一遍待排序文件和位圖，時間復雜度O(n)，需要的輔助空間為(max(S)/8)B。雖然這個排序算法只能在無重復的整數(shù)集上運行，但對于有些需求，確實做到高效實現(xiàn)，比如說給手機號碼排序，手機號碼11位，第一位始終為1，理論上可以有10^10個號碼，但一些號碼未發(fā)放，即有些號碼在系統(tǒng)中不存在，假設系統(tǒng)中有50%的合法號碼，每個號碼用long int表示，這么多號碼所需要的空間為50%*(10^10)*4B=20GB，不能放在內(nèi)存中進行快速排序。一個可選的方案是分多趟進行歸并排序，但需要較長的時間。我們申請一個10^10位的位圖，需要的內(nèi)存是10^10/8B=1.25GB，完全可以在當代的PC機上運行，在掃描位圖時，假設某一位i為1，輸出文件時，在前面添加一個1，例如i=3885201314，輸出為13885201314。

二、算法實現(xiàn)

用c語言實現(xiàn)的話，需要自己封裝位圖操作，這里需要用到三個操作：設置位圖的所有位為0(setAllZero)；設定指定的位為1(setOne)；查看指定的位是否為1(find)；代碼如下：

復制代碼代碼如下:

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define MAX_NUM 16777216//最大的數(shù),也就是需要的位
#define BYTE_NUM (1+MAX_NUM/8)//字節(jié)數(shù)
#define MASK 0x07

void setAllZero(unsigned char *p,long size);
void setOne(unsigned char *p,long loc);
int find(unsigned char *p,long loc);
bool getSorted(unsigned char *bitmap,char *fileName);
bool setBitmap(unsigned char *bitmap,char *fileName);
int bitmapSort();
int main(){
    return bitmapSort();
}
int bitmapSort(){
    unsigned char *bitmap;    //位圖指針
    bitmap = (unsigned char *)malloc(BYTE_NUM*sizeof(unsigned char));
    if(bitmap == NULL){
        printf("Malloc failed\n");
        return -1;
    }
    setAllZero(bitmap,BYTE_NUM);//將位圖所有位設置為0
    setBitmap(bitmap,"phoneNumber.txt");//掃描待排文件，將位圖對應位設置為1
    getSorted(bitmap,"bitmapSort.txt");    //掃描位圖，將位圖為1的位號輸出到文件
    free(bitmap);//釋放位圖
    return 0;
}
/***********設置待排序數(shù)據(jù)的位圖**************/
bool setBitmap(unsigned char *bitmap,char *fileName){
    FILE *readFp;
    printf("Setting bitmap...\n");
    readFp = fopen(fileName,"r");
    if(readFp == NULL)
        return false;
    long phoneNum=0;
    while(fscanf(readFp,"%ld\n",&phoneNum) != EOF){
        setOne(bitmap,phoneNum);//將    phoneNum位設置為1
    }
    fclose(readFp);
    return true;
}
/*****順序遍歷位圖輸出記錄，從而實現(xiàn)排序****************/
bool getSorted(unsigned char *bitmap,char *fileName){
    printf("Search bitmap...\n");
    FILE *writeFp;
    writeFp = fopen(fileName,"w");
    if(writeFp == NULL)
        return false;
    long phoneNum=0;
    for(phoneNum = 0; phoneNum < MAX_NUM; phoneNum += 1){
        if(find(bitmap,phoneNum)){
            fprintf(writeFp,"%ld\n",phoneNum);
        }
    }
    fclose(writeFp);
    return true;
}
/******先將位圖清零********/
void setAllZero(unsigned char *bitmap,long size){
    for(long i=0;i<size;i++)
        *(bitmap+i) &= 0;
}
/*************************************************
將指定的位置為1
(loc>>3)相當于整除2^3=8，即定位到字節(jié)數(shù)，MASK=0x07,loc&MASK相當于loc%8
***************************************************/
void setOne(unsigned char *bitmap,long loc){
    *(bitmap+(loc>>3)) |= (1<<(loc&MASK));//
}

/******查找指定的位是否為1********/
int find(unsigned char *bitmap,long loc){
return ((*(bitmap+(loc>>3))) & (1<<(loc&MASK))) == (1<<(loc&MASK));
}

C++的STL中有一個數(shù)據(jù)結構bitset，操作位圖很方便。

復制代碼代碼如下:

#include <bitset>
#define MAX_NUM 4000000//最多的數(shù)，即需要的位數(shù)
using namespace std;

int main(){
    FILE *readFp,*writeFp;
    readFp = fopen("phoneNumber1.txt","r");
    writeFp = fopen("bitsetSorted.txt","w");
    bitset<MAX_NUM> bitmap;
    for(long i=0;i<MAX_NUM;i++){//先將位圖初試化為0
        bitmap.set(i,0);
    }
    printf("Begin set bitmap...\n");
    long number = 0;
    while(fscanf(readFp,"%ld\n",&number) != EOF){
        bitmap.set(number,1);//將number所在位設置為1
    }
    printf("Begin search bitmap...\n");
    for(long i=0;i<MAX_NUM;i++){
        if(bitmap[i] == 1)//將位1的位輸出到已排序文件
            fprintf(writeFp,"%ld\n",number);
    }
    fclose(writeFp);
    fclose(readFp);
}

排序算法很快就寫好了，就開始生成測試數(shù)據(jù)，想生成0—2^31的亂序數(shù)據(jù)集還真不容易，首先要保證不重復，第二要丟掉40%的數(shù)（無效手機號碼），第三要盡可能的亂序，搗了很久，最終還是找到了實現(xiàn)辦法，生成了12GB的數(shù)據(jù)集，關于生成這個數(shù)據(jù)集的辦法，歡迎一起討論，我將會在下一篇中總結一下我的方法。
完整的代碼可以參考github。

您可能感興趣的文章: