用位圖排序無重復(fù)數(shù)據(jù)集實例代碼(C++版)
一、主要思想
位圖排序的思想就是在內(nèi)存中申請一塊連續(xù)的空間作為位圖,初始時將位圖的每一位都置為0,然后依次讀取待排序文件的整數(shù),將整數(shù)所在的位設(shè)置為1,最后掃描位圖,如果某一位為1,則說明這個數(shù)存在,輸出到已排序文件。比如待排序的數(shù)據(jù)S={3,0,4,1,7,2,5},max(S)=7,我們可以設(shè)置一個八位的位圖B,將位圖的每一位初始為0,即B=[0,0,0,0,0,0,0,0],對S中的每一個整數(shù)d,設(shè)置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}。
整個過程只需要遍歷一遍待排序文件和位圖,時間復(fù)雜度O(n),需要的輔助空間為(max(S)/8)B。雖然這個排序算法只能在無重復(fù)的整數(shù)集上運行,但對于有些需求,確實做到高效實現(xiàn),比如說給手機號碼排序,手機號碼11位,第一位始終為1,理論上可以有10^10個號碼,但一些號碼未發(fā)放,即有些號碼在系統(tǒng)中不存在,假設(shè)系統(tǒng)中有50%的合法號碼,每個號碼用long int表示,這么多號碼所需要的空間為50%*(10^10)*4B=20GB,不能放在內(nèi)存中進行快速排序。一個可選的方案是分多趟進行歸并排序,但需要較長的時間。我們申請一個10^10位的位圖,需要的內(nèi)存是10^10/8B=1.25GB,完全可以在當代的PC機上運行,在掃描位圖時,假設(shè)某一位i為1,輸出文件時,在前面添加一個1,例如i=3885201314,輸出為13885201314。
二、算法實現(xiàn)
用c語言實現(xiàn)的話,需要自己封裝位圖操作,這里需要用到三個操作:設(shè)置位圖的所有位為0(setAllZero);設(shè)定指定的位為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);//將位圖所有位設(shè)置為0
setBitmap(bitmap,"phoneNumber.txt");//掃描待排文件,將位圖對應(yīng)位設(shè)置為1
getSorted(bitmap,"bitmapSort.txt"); //掃描位圖,將位圖為1的位號輸出到文件
free(bitmap);//釋放位圖
return 0;
}
/***********設(shè)置待排序數(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位設(shè)置為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ù)結(jié)構(gòu)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所在位設(shè)置為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ù)集還真不容易,首先要保證不重復(fù),第二要丟掉40%的數(shù)(無效手機號碼),第三要盡可能的亂序,搗了很久,最終還是找到了實現(xiàn)辦法,生成了12GB的數(shù)據(jù)集,關(guān)于生成這個數(shù)據(jù)集的辦法,歡迎一起討論,我將會在下一篇中總結(jié)一下我的方法。
完整的代碼可以參考github。
相關(guān)文章
C++實現(xiàn)LeetCode(95.獨一無二的二叉搜索樹之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(95.獨一無二的二叉搜索樹之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07C++之CNoTrackObject類和new delete操作符的重載實例
這篇文章主要介紹了C++之CNoTrackObject類和new delete操作符的重載實例,是C++程序設(shè)計中比較重要的概念,需要的朋友可以參考下2014-10-10VC++文件監(jiān)控之FindFirstChangeNotification
因為ReadDirectoryChangesW 上次測試發(fā)現(xiàn)不能多級目錄監(jiān)控,所以嘗試用FindFirstChangeNotification來實施文件監(jiān)控,需要的朋友可以參考下2019-04-04C語言數(shù)據(jù)結(jié)構(gòu)中數(shù)制轉(zhuǎn)換實例代碼
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)中數(shù)制轉(zhuǎn)換實例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03簡要解讀C++的動態(tài)和靜態(tài)關(guān)聯(lián)以及虛析構(gòu)函數(shù)
這篇文章主要介紹了簡要解讀C++的動態(tài)和靜態(tài)關(guān)聯(lián)以及虛析構(gòu)函數(shù),析構(gòu)函數(shù)在C++編程中平時并不是太常用,需要的朋友可以參考下2015-09-09OpenCV中C++函數(shù)imread讀取圖片的問題及解決方法
利用C++函數(shù)imread讀取圖片的時候返回的結(jié)果總是空,而利用C函數(shù)cvLoadImage時卻能讀取到圖像。怎么回事?今天小編通過本教程給大家簡單說明原因2017-03-03詳解C語言編程中的函數(shù)指針以及函數(shù)回調(diào)
這篇文章主要介紹了C語言編程中的函數(shù)指針以及函數(shù)回調(diào),函數(shù)回調(diào)實際上就是讓函數(shù)指針作函數(shù)參數(shù)、調(diào)用時傳入函數(shù)地址,需要的朋友可以參考下2016-04-04