资源描述：
《海量数据排序总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、问题:假设一个文件中有9亿条不重复的9位整数，现在要求对这个文件进行排序。一般解题思路:1、将数据导入到内存中2、将数据进行排序 （比如插入排序、快速排序）3、将排序好的数据存入文件难题:一个整数为4个字节即使使用数组也需要900,000,000*4byte=3.4G内存对于32位系统，访问2G以上的内存非常困难，而且一般设备也没有这么多的物理内存将数据完全导入到内存中的做法不现实其他解决办法:1、导入数据库运算2、分段排序运算3、使用bit位运算解决方案一:数据库排序将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件优点：操作简单缺点：运算速度慢，而且需要
2、数据库设备。解决方案二:分段排序操作方式：规定一个内存大小，比如200M，200M可以记录(200*1024*1024/4)=52428800条记录，我们可以每次提取5000万条记录到文件进行排序，要装满9位整数需要20次，所以一共要进行20次排序，需要对文件进行20次读操作缺点：编码复杂，速度也慢(至少20次搜索)关键步骤：先将整个9位整数进行分段，亿条数据进行分成20段，每段5000万条在文件中依次搜索0~5000万，50000001~1亿……将排序的结果存入文件解决方案三:bit位操作思考下面的问题:一个最大的9位整数为999999999这9亿条数据是不重复的可不可
3、以把这些数据组成一个队列或数组，让它有0~999999999(10亿个)元素数组下标表示数值，节点中用0表示这个数没有，1表示有这个数判断0或1只用一个bit存储就够了声明一个可以包含9位整数的bit数组(10亿)，一共需要10亿/8=120M内存把内存中的数据全部初始化为0,读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909这个数据，那就先在内存中找到341245909这个bit，并将bit值置为1遍历整个bit数组，将bit为1的数组下标存入文件关键代码检查是某一个char里面(first)的第second位中存储的数据是否为1boolCompa
4、reBit(unsignedcharfirst,intsecond){conststaticintmark_buf[]={0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80};if(second>.8)returnfalse;return(first&mark_buf[second])==mark_buf[second];}将某一个char(Desc)中的第source位置为1boolWriteToBit(unsignedchar*Desc,intsource){conststaticintmark_buf[]={0x1,0x2,0x4,0x8,0x1
5、0,0x20,0x40,0x80};if(source>.8)returnfalse;Desc[0]
6、=mark_buf[source];returntrue;}案例在某个项目中，我们需要对2亿条手机号码删除重复记录(过滤号码黑名单同样有效)工作难点就在于如何处理这2亿条电话号码,直接用哈希表存放手机号码不大现实,即使经过优化,用一个unsignedint存放一条记录,那也得需要2亿*4=8亿byte,远超过32位系统的寻址能力解决方案:将电话号码由12位单个数字组成的字符串转换为一个unsignedint型数据(这个完全可能,手机号码由前三位数字和后面八位数字组成,后面
7、八位需要占到1~1000万的空间,而前面用0~100的数字存储已经足够)为简单起见,默认为0~4G的数字都有可能分布号码,为此我们分配4G/32=512M的内存将这2亿个号码整理成unsignedint类型后按上述办法存放在这块内存中(比如13512345678我们整理后为112345678,我们找到内存中112345678bit的下标,并将此bit值设为1)遍历整个bit数组,记录下所有的号码,这些号码即是不重复的手机号码总结建立一个足够大的bit数组当作hash表以bit数组的下标来表示一个整数以bit位中的0或1来表示这个整数是否在这个数组中存在适用于无重复原始数据
8、的搜索原来每个整数需要4byte空间变为1bit，空间压缩率为32倍扩展后可实现其他类型（包括重复数据）的搜索主题：3000w数据的表，取某项字段前50项数据，内存2G偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的，3000w的数据划分为1000段，也就是1-3w为一段，30001-6w项为第二段，依次类推，从每3w的数据中提取出前50条数据（这个根据sql排序就能取出来，2个g的内存够了），最后1000个50就会产生5w个数据，最后提取出来的5w的数据放置到ArrayList中去，最后5w的数据统一排序，取出前50
