上一篇讲述了用位图实现无重复数据的排序,排序算法一下就写好了,想弄个大点数据测试一下,因为小数据在内存中快排已经很快。
一、生成的数据集要求
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天,需要探测的次数变多后变得很慢,这次属于瞎折腾了,不过结果不重要,通过这次折腾还是熟悉了位图的基本操作,并对随机数有了新的认识,而且我自认为这个位图+冲突处理的方法还是很有启发的。
相关推荐
透明位图 背景透明 VC代码 ; 注释清晰,代码简洁一目了然,附带透明位图原理说明文档。
RGB数据生成BMP位图(其中包括RGB数组随机生成),关于更RGB数据处理和图像处理,请联系作者
简单的 G代码生成软件,处理简单的平面雕刻,软件有三个按钮...打开:打开位图文件,如打开的位图已经画好了边缘则不用扫描边缘直接生成G代码 如果是钻孔的话,图片里钻孔的位置放一个像素的黑点 需要些图片处理的功底
3.1.2 组描述符和位图 105 3.1.3 磁盘索引节点表 105 3.2 VFS接口数据结构 110 3.2.1 Ext2 超级块对象 110 3.2.2 Ext2 的索引节点对象 121 3.2.3 创建Ext2文件系统 124 3.2.4 Ext2的方法总结 126 3.3 Ext2索引节点...
windows下的位图生成工具,可以生成简单的位图。 使用方法很简单,点击“工具”添加字符即可获得需要的位图字体。
位图字体生成工具 ugui 、 ngui 自定义字体,美术字、、、
平台:DEV-C++ 5.8.3 语言:C++ 功能: 1)1、4、8(灰度、色彩)、16(565、555)、24、...2)可用C++在源码级别生成位图,画个小画;读入位图数据,转换位图格式。 3)将图片转化为单片机开发能用到的液晶坐标文件。
flash动画优化——位图淘汰机制 Bitmap对象是flash中渲染速度最快的,同时它还有一个特点是多个Bitmap实例可以共用同一个BitmapData对象,在这种情况下,多个Bitmap实例和单个Bitmap实例所占用的内存相差无几。 ...
24位彩图转为8位灰度图的C++代码,通过修改位图文件信息头来实现位图转换。
纯C++代码写文件的形式生成Bitmap。对于理解Bitmap的格式有着非常好的效果。
Java文字生成位图demo,通过后台接口,传入文字等一系列参数,生成位图 图片
使用C# 生成单色位图,并且为图片添加信息头
android 多位图转化为单色位图。32位深图转1位深图。24位深转1位
生成24位位图 c 代码
一个非常实用的位图生成样例,并可生成相应的BMP文件。
一个生成8位位图文件的c源码
VC++源代码,根据位图实际大小,自动调整窗口大小,显示位图
VC下彩色位图转单色位图,可实现截图,生成位图数据文件。
LCD 位图 生成工具 用于嵌入式位图的生产。希望有用。