疯狂位图之——位图实现12GB无重复大整数集排序_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 疯狂位图之——位图实现12GB无重复大整数集排序

疯狂位图之——位图实现12GB无重复大整数集排序

 2013/7/10 4:37:08  huangfengsmile  程序员俱乐部  我要评论(0)
  • 摘要:疯狂位图之——位图实现12GB无重复大整数集排序《ProgrammingPearls》(编程珠玑)第一章讲述了如何用位图排序无重复的数据集,整个思想很简洁,今天实践了下。一、主要思想位图排序的思想就是在内存中申请一块连续的空间作为位图,初始时将位图的每一位都置为0,然后依次读取待排序文件的整数,将整数所在的位设置为1,最后扫描位图,如果某一位为1,则说明这个数存在,输出到已排序文件。比如待排序的数据S={3,0,4,1,7,2,5},max(S)=7,我们可以设置一个八位的位图B
  • 标签:实现
疯狂位图之——位图实现12GB无重复大整数集排序
  《Programming Pearls》(编程珠玑)第一章讲述了如何用位图排序无重复的数据集,整个思想很简洁,今天实践了下。

一、主要思想

  位图排序的思想就是在内存中申请一块连续的空间作为位图,初始时将位图的每一位都置为0,然后依次读取待排序文件的整数,将整数所在的位设置为1,最后扫描位图,如果某一位为1,则说明这个数存在,输出到已排序文件。比如待排序的数据S={3,0,4,1,7,2,5},max(S)=7,我们可以设置一个八位的位图B,将位图的每一位初始为0,即B=[0,0,0,0,0,0,0,0],对S中的每一个整数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。虽然这个排序算法只能在无重复的整数集上运行,但对于有些需求,确实做到高效实现,比如说给手机号码排序,手机号码11位,第一位始终为1,理论上可以有10^10个号码,但一些号码未发放,即有些号码在系统中不存在,假设系统中有50%的合法号码,每个号码用long int表示,这么多号码所需要的空间为50%*(10^10)*4B=20GB,不能放在内存中进行快速排序。一个可选的方案是分多趟进行归并排序,但需要较长的时间。我们申请一个10^10位的位图,需要的内存是10^10/8B=1.25GB,完全可以在当代的PC机上运行,在扫描位图时,假设某一位i为1,输出文件时,在前面添加一个1,例如i=3885201314,输出为13885201314。

二、算法实现

  用c语言实现的话,需要自己封装位图操作,这里需要用到三个操作:设置位图的所有位为0(setAllZero);设定指定的位为1(setOne);查看指定的位是否为1(find);代码如下:


1 #include <malloc.h>
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <time.h>
5 #include <math.h>
6
7 #define MAX_NUM 16777216//最大的数,也就是需要的位
8 #define BYTE_NUM (1+MAX_NUM/8)//字节数
9 #define MASK 0x07
10
11 void setAllZero(unsigned char *p,long size);
12 void setOne(unsigned char *p,long loc);
13 int find(unsigned char *p,long loc);
14 bool getSorted(unsigned char *bitmap,char *fileName);
15 bool setBitmap(unsigned char *bitmap,char *fileName);
16 int bitmapSort();
17 int main(){
18     return bitmapSort();
19 }
20 int bitmapSort(){
21     unsigned char *bitmap;    //位图指针
22     bitmap = (unsigned char *)malloc(BYTE_NUM*sizeof(unsigned char));
23     if(bitmap == NULL){
24         printf("Malloc failed\n");
25         return -1;
26     }   
27     setAllZero(bitmap,BYTE_NUM);//将位图所有位设置为0
28     setBitmap(bitmap,"phoneNumber.txt");//扫描待排文件,将位图对应位设置为1
29     getSorted(bitmap,"bitmapSort.txt");    //扫描位图,将位图为1的位号输出到文件
30     free(bitmap);//释放位图
31     return 0;
32 }
33 /***********设置待排序数据的位图**************/
34 bool setBitmap(unsigned char *bitmap,char *fileName){
35     FILE *readFp;
36     printf("Setting bitmap...\n");
37     readFp = fopen(fileName,"r");
38     if(readFp == NULL)
39         return false;   
40     long phoneNum=0;
41     while(fscanf(readFp,"%ld\n",&phoneNum) != EOF){
42         setOne(bitmap,phoneNum);//将    phoneNum位设置为1   
43     }
44     fclose(readFp);
45     return true;
46 }
47 /*****顺序遍历位图输出记录,从而实现排序****************/
48 bool getSorted(unsigned char *bitmap,char *fileName){
49     printf("Search bitmap...\n");
50     FILE *writeFp;
51     writeFp = fopen(fileName,"w");
52     if(writeFp == NULL)
53         return false;
54     long phoneNum=0;
55     for(phoneNum = 0; phoneNum < MAX_NUM; phoneNum += 1){
56         if(find(bitmap,phoneNum)){
57             fprintf(writeFp,"%ld\n",phoneNum);
58         }
59     }
60     fclose(writeFp);
61     return true;
62 }
63 /******先将位图清零********/
64 void setAllZero(unsigned char *bitmap,long size){
65     for(long i=0;i<size;i++)
66         *(bitmap+i) &= 0;
67 }
68 /*************************************************
69 将指定的位置为1
70 (loc>>3)相当于整除2^3=8,即定位到字节数,MASK=0x07,loc&MASK相当于loc%8
71 ***************************************************/
72 void setOne(unsigned char *bitmap,long loc){
73     *(bitmap+(loc>>3)) |= (1<<(loc&MASK));//
74 }
75
76 /******查找指定的位是否为1********/
77 int find(unsigned char *bitmap,long loc){
78     return ((*(bitmap+(loc>>3))) & (1<<(loc&MASK))) == (1<<(loc&MASK));   
79 }



  C++的STL中有一个数据结构bitset,操作位图很方便。  


1 #include <bitset>
2 #define MAX_NUM 4000000//最多的数,即需要的位数
3 using namespace std;
4
5 int main(){
6     FILE *readFp,*writeFp;
7     readFp = fopen("phoneNumber1.txt","r");       
8     writeFp = fopen("bitsetSorted.txt","w");   
9     bitset<MAX_NUM> bitmap;
10     for(long i=0;i<MAX_NUM;i++){//先将位图初试化为0
11         bitmap.set(i,0);
12     }
13     printf("Begin set bitmap...\n");
14     long number = 0;
15     while(fscanf(readFp,"%ld\n",&number) != EOF){
16         bitmap.set(number,1);//将number所在位设置为1       
17     }
18     printf("Begin search bitmap...\n");
19     for(long i=0;i<MAX_NUM;i++){
20         if(bitmap[i] == 1)//将位1的位输出到已排序文件
21             fprintf(writeFp,"%ld\n",number);
22     }
23     fclose(writeFp);
24     fclose(readFp);
25 }

  排序算法很快就写好了,就开始生成测试数据,想生成0—2^31的乱序数据集还真不容易,首先要保证不重复,第二要丢掉40%的数(无效手机号码),第三要尽可能的乱序,捣了很久,最终还是找到了实现办法,生成了12GB的数据集,关于生成这个数据集的办法,欢迎一起讨论,我将会在下一篇中总结一下我的方法。

  完整的代码可以参考github。

  感谢关注,欢迎评论。

  转载自http://www.cnblogs.com/fengfenggirl/
发表评论
用户名: 匿名