疯狂位图之——位图生成12GB无重复随机乱序大整数集

    上一篇讲述了用位图实现无重复数据的排序，排序算法一下就写好了，想弄个大点数据测试一下，因为小数据在内存中快排已经很快。

一、生成的数据集要求

　　1、数据为0--2147483647(2^31-1)范围内的整数；

　　2、数据集包含60%的0--2^31-1的整数，即踢去40%的数；

　　3、数据集中无重复数据，即任意两个数不相等；

　　4、生成的数据尽可能乱序。

二、方案分析

　　开始只是想弄个大点数据玩一下而已，觉得测试数据应该要满足上面的要求，动手写的时候发现，满足前3个要求都很容易，实现尽可能的乱序不好处理，计算一下这样的数据大概有多大，每个整数按10个字符计算，60%2^31*10B=12GB，存在磁盘中需要12GB空间，如果能放入内存，整数按4字节整数计算60%*2^31*4B=4.8GB。

　　可以先生成满足1-3的条件的数据：

for(long num=0;num<=LONG_MAX;num++){
    if (rand() <= 0.6*RAND_MAX)//利用随机数实现抽样60%
        saveData(num);
}

　　接下来再进行乱序处理，和排序算法一下，一个可选的方案是进行分段归并乱序处理。不过我在想既然可以用位图排序，为什么不能用位图生成。受到散列表的启发，设计了一个用位图生成的方法。步骤如下：

　　1、在内存中申请一个2147483647位大小的位图B，需要内存为2^31/8B=256MB的内存；

　　2、将位图的所有位设置为0(B[i]=0)，表示0-2147483647的所有数均未使用过；

　　3、生成一个0-2147483647之间的随机数random，在位图中检查B[random]是否等于0，如果为0，表示这个数没有用过，把random写入文件，并置B[random]为1；如果为1，表示这个数已经被使用过了，此时去检查random+1是否等于0，等于0就保存(random+1)，并置(random+1)为1，如果不为0，则再探测random-1，random+2，random-2...，直到遇到一个为0的位，这和散列表的冲突处理类似，我这里用摆动线性探测。

　　伪代码如下：

void generatorData(){
    B = new bitset(LONG_MAX);
    B.reset();//将位图置0
    count = 0;//计数器
    while(count <= 0.6*LONG_MAX){
        random = getLongRand();    
        offset = 0;
        while(B[random+offset]==1){
            offset = getNextIndex();//获取下一个探测偏移量
        }
        saveData(random+offset);
        count++;
        B[random+offset]==1//该数已经被使用
        }        
    }
}

　　按照算法思想，每次产生一个随机数，如果这个随机数未被使用过，就保存，否则就找一个离这个随机数最近且未被使用的数保存。这里有两个关键的地方，一个是getLongRand()，这个产生0-LONG_MAX随机数的随机性直接影响了整个数据集的随机性，如果getLongRand()满足随机，那生产的数据也会是随机的。另外一个就是getNextIndex()，如果随机数已经被使用，需要在其周围探测，这个探测序列的设计的优劣将影响算法的实现效率，如果总是探测失败，就会在探测上花费太多时间，特别是在后期，很多数都已经被使用了，需要的探测的次数变得很多。如果用这个算法生成100%的数而不是60%，将会非常耗时，试想最后几个数总是要遍历整个数空间，但我们只生成60%的数据，位图中的0还不至于非常稀疏，不需要进行耗时的查询。

　　实现代码如下：

 1 /*********生成一个左右摆动的序列:1，-1,2，-2...**************/
 2 long getNextIndex(long size,long index){
 3     static short tag = -1;
 4     static long left = 0;
 5     static long right = 0;
 6     if (index == -1){//对不同的index,需要将static变量重置
 7         tag = -1;
 8         left = 0;
 9         right = 0;
10     }
11     if(index + (left - 1) < 0 && index +(right + 1) >= size)  
12         return 0;//已经遍历完，不需要再找了
13     if (index + (left - 1) < 0)
14         return ++right;//左边已经越出界限了，试探右边
15     if (index+(right + 1)>=size) 
16         return --left;//右边已经越出界限了，试探左边
17     if (tag == -1){//左右都没有出界，左右依次试探    
18         tag *= -1;
19         return ++right;
20     }else{
21         tag *= -1;
22         return --left;
23     }
24 }
25 
26 void makePhoneNum(unsigned char *bitmap,long maxNum,short bitSize){
27     FILE * phoneNumFile = fopen("phoneNumber.txt","w");
28     long count = 0;
29     long percent = 0.6*maxNum;
30     while(true){
31         long index = randLong(bitSize);
32         long offset = 0;
33         while(find(bitmap,index+offset) == 1){//这个数已经用过或者不存在
34             offset = getNextIndex(maxNum,index);
35             if(offset == 0){//查找的偏移量为0说明数都用过了
36                 fclose(phoneNumFile);
37                 return;
38             }
39         }
40         getNextIndex(maxNum,-1);//将static变量重置
41         long loc = index+offset;
42         setOne(bitmap,loc);
43         fprintf(phoneNumFile,"%ld\n",loc);
44         if(++count > percent)//保存了80%终止
45             break;
46         if(count%1000000==0)
47             printf("count:\t%ld\n",count);
48     }
49     fclose(phoneNumFile);
50 }

　　　　数据生成完后，发现其实可以生成一个降序的文件，再按升序排序也能验证排序算法。最后发现生成12G的数据将近要2天，需要探测的次数变多后变得很慢，这次属于瞎折腾了，不过结果不重要，通过这次折腾还是熟悉了位图的基本操作，并对随机数有了新的认识，而且我自认为这个位图+冲突处理的方法还是很有启发的。

评论

1 楼 nubix 2013-07-03  

不知道该说什么了