上一篇讲述了用位图实现无重复数据的排序，排序算法一下就写好了，想弄个大点数据测试一下，因为小数据在内存中快排已经很快。
一、生成的数据集要求
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。
《编程珠玑》第一章习题的第4题与这里的要求类似，书上给的解是这样的：
//生成k个0-n之间的随机整数
for i = [,n)
x[i] = i
for i = [,k)
swap(x[i],x[randint(i,n-)])//randint(a,b)生成的是[a,b]之间的随机数，swap(a,b)表示交换a,b的值
save(x[i])
上面的解法是建立在n比较小，大小为n的数组能放在内存的条件下的，按之前的分析，如果建立一个n=2^31-1的数组，需要的内存是8GB，因此内存放不下，swap(x[i],x[random])这样的操作无法进行。也许我们可以先生成满足1-3的条件的数据：
for(long num=;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 = ;//计数器
while(count <= 0.6*LONG_MAX){
random = getLongRand();
offset = ;
while(B[random+offset]==){
offset = getNextIndex();//获取下一个探测偏移量
}
saveData(random+offset);
count++;
B[random+offset]==//该数已经被使用
}
}
}
按照算法思想，每次产生一个随机数，如果这个随机数未被使用过，就保存，否则就找一个离这个随机数最近且未被使用的数保存。这里有两个关键的地方，一个是getLongRand()，这个产生0-LONG_MAX随机数的随机性直接影响了整个数据集的随机性，如果getLongRand()满足随机，那生产的数据也会是随机的。另外一个就是getNextIndex()，如果随机数已经被使用，需要在其周围探测，这个探测序列的设计的优劣将影响算法的实现效率，如果总是探测失败，就会在探测上花费太多时间，特别是在后期，很多数都已经被使用了，需要的探测的次数变得很多。如果用这个算法生成100%的数而不是60%，将会非常耗时，试想最后几个数总是要遍历整个数空间，但我们只生成60%的数据，位图中的0还不至于非常稀疏，不需要进行耗时的查询。
实现代码如下：
/*********生成一个左右摆动的序列:1，-1,2，-2...**************/
long getNextIndex(long size,long index){
static short tag = -;
static long left = ;
static long right = ;
if (index == -){//对不同的index,需要将static变量重置
tag = -;
left = ;
right = ;
}
if(index + (left - ) < && index +(right + ) >= size)
return ;//已经遍历完，不需要再找了
if (index + (left - ) < )
return ++right;//左边已经越出界限了，试探右边
if (index+(right + )>=size)
return --left;//右边已经越出界限了，试探左边
if (tag == -){//左右都没有出界，左右依次试探
tag *= -;
return ++right;
}else{
tag *= -;
return --left;
}
} void makePhoneNum(unsigned char *bitmap,long maxNum,short bitSize){
FILE * phoneNumFile = fopen("phoneNumber.txt","w");
long count = ;
long percent = 0.6*maxNum;
while(true){
long index = randLong(bitSize);
long offset = ;
while(find(bitmap,index+offset) == ){//这个数已经用过或者不存在
offset = getNextIndex(maxNum,index);
if(offset == ){//查找的偏移量为0说明数都用过了
fclose(phoneNumFile);
return;
}
}
getNextIndex(maxNum,-);//将static变量重置
long loc = index+offset;
setOne(bitmap,loc);
fprintf(phoneNumFile,"%ld\n",loc);
if(++count > percent)//保存了80%终止
break;
if(count%==)
printf("count:\t%ld\n",count);
}
fclose(phoneNumFile);
}
生成随机数randLong()在下一篇单独介绍，下一篇会总结下随机数,也可以在Github上查看。
数据生成完后，发现其实可以生成一个降序的文件，再按升序排序也能验证排序算法。最后发现生成12G的数据将近要2天，需要探测的次数变多后变得很慢，这次属于瞎折腾了，不过结果不重要，通过这次折腾还是熟悉了位图的基本操作，并对随机数有了新的认识，而且我认为这个位图+冲突处理的方法还是很有启发的。
