搜索
当前位置: 秒秒彩平台 > 读整数内存 >

在一个文件中有10G个整数乱序排序要求找出中位数。

gecimao 发表于 2019-07-06 16:36 | 查看: | 回复:

  在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

  我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。

  如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围内出现的整数比较多,我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)。

  这是腾讯的一个笔试题,想知道“将64bit的整数空间平均分成256M个取值范围”是什么意思。。求教。。展开我来答

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  然后换个思维理解,比如有20个数,数的范围是(1-10),而内存只能装入两个数。用内存里的这两个数统计范围为(0,5),(6,10)的数出现的次数,比如内存里两个数的取值是4,16,显然中位数(姑且认为是求第10位)出现在(6,10)中的第6出现的数。

  这个时候,内存两个数统计范围变成(6,8),(9,10),统计这两个区间内范围出现的数的次数,如果是8,8,中位数是在(6,8)中第6次出现的数。

  第三次统计,内存两个数统计的范围是(6,7),(8),如果是7,1,那么所求的中位数还是(6,7)第6次出现的数。

  第四次统计,内存两个数为(6),(7),如果内存第一个数=6,则所求数为6,否则所求数为7。

  然后换个思维理解,比如有20个数,数的范围是(1-10),而内存只能装入两个数。用内存里的这两个数统计范围为(0,5),(6,10)的数出现的次数,比如内存里两个数的取值是4,16,显然中位数(姑且认为是求第10位)出现在(6,10)中的第6出现的数。

  这个时候,内存两个数统计范围变成(6,8),(9,10),统计这两个区间内范围出现的数的次数,如果是8,8,中位数是在(6,8)中第6次出现的数。

  第三次统计,内存两个数统计的范围是(6,7),(8),如果是7,1,那么所求的中位数还是(6,7)第6次出现的数。

  第四次统计,内存两个数为(6),(7),如果内存第一个数=6,则所求数为6,否则所求数为7。

  1. 读一遍10G个整数,把整数映射到256M个区段中,用一个64位无符号整数给每个相应区段记数。

  说明:整数范围是0 - 2^32 - 1,一共有4G种取值,映射到256M个区段,则每个区段有16(4G/256M = 16)种值,每16个值算一段, 0~15是第1段,16~31是第2段,……2^32-16 ~2^32-1是第256M段。一个64位无符号整数最大值是0~8G-1,这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。

  2. 从前到后对每一段的计数累加,当累加的和超过5G时停止,找出这个区段(即累加停止时达到的区段,也是中位数所在的区段)的数值范围,设为[a,a+15],同时记录累加到前一个区段的总数,设为m。然后,释放除这个区段占用的内存。

  3. 再读一遍10G个整数,把在[a,a+15]内的每个值计数,即有16个计数。

  4. 对新的计数依次累加,每次的和设为n,当m+n的值超过5G时停止,此时的这个计数所对应的数就是中位数。

  1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线. 考虑其他情况。

  若是有符号的整数,只需改变映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。

  花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。

  4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。

本文链接:http://latharnaog.com/duzhengshunacun/574.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部