题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为
2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。
分析:
既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法
(请见《桶排序
》):
思想:将整形的每1byte作为一个关键字,也就是说一个整形可以拆成4个keys,而且最高位的keys越大,整数越大。如果高位keys相同,则比较次高位的keys。整个比较过程类似于字符串的字典序。
第一步:把10G整数每2G读入一次内存,然后一次遍历这536,870,912个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶,那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中,同时在内存中统计每个桶内数据的数量,自然这个数量只需要255个整形空间即可。
代价:(1) 10G数据依次读入内存的IO代价(这个是无法避免的,CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据,这是一个O(n)的线性时间复杂度。(3)把255个桶写会到255个磁盘文件空间中,这个代价是额外的,也就是多付出一倍的10G数据转移的时间。
第二步:根据内存中255个桶内的数量,计算中位数在第几个桶中。很显然,2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加,发现少于1,342,177,280,把第128个桶数据量加上,大于1,342,177,280。说明,中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(平均而言,每个文件的大小估计在10G/128=80M左右,当然也不一定,但是超过2G的可能性很小)。
代价:(1)循环计算255个桶中的数据量累加,需要O(M)的代价,其中m<255。(2)读入一个大概80M左右文件大小的IO代价。
注意,变态的情况下,这个需要读入的第128号文件仍然大于2G,那么整个读入仍然可以按照第一步分批来进行读取。
第三步:继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同,也是255个桶。
第四步:一直下去,直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。
整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上,即10G数据分255个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。关于快排的效率,可以看看我博客中的数据《基于比较的内部排序总结
》。
分享到:
相关推荐
腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持腾讯x5 tbs 多文件支持
使用腾讯TBS来预览pdf,word,excel,ppt等多种类型的文件,去 腾讯浏览服务官网下载SDK,按照官方文档文档集成SDK。 2.使用TbsReaderView来加载文件 动态创建TbsReaderView,然后添加到布局中。 // 回调 ...
这是腾讯官网的腾讯管家单文件。可以半个小时,
Android 系统备份腾讯地图程序APP资源文件,开发者根据资源data目录查看db数据文件
腾讯反Tp文件,主要针对Win8操作系统,希望可以改大家帮住一下,许多的都不可以用,试试这款
腾讯TBS浏览服务打开本地文档(word.pdf.ppt)踩过的坑
腾讯TNN示例里的model文件,使用download_model.sh下载很慢且容易失败,通过一番努力终于凑齐了。
提供腾讯通的共享桌面,共享文件插件,如您公司安装了腾讯通但是无法进行远程桌面控制去为客户解决问题,那这款插件就可以解决你的问题了
腾讯XLog的文件解密,已封装成EXE文件,把EXE文件和xlog文件放到一个文件夹内双击解密即可,注意:这个是默认加密模式的,还有android用的jni 的So库
腾讯im对接实例.zip
腾讯叮当android 客户端 临时文件
腾讯地图全国地址信息(省、市、区、gcj02 gps)sql文件
2 文件格式优化,提速导入 (10分钟压缩至15秒) 网有导出的sql 4万多行数据的单条 sql 的,我转为bulk insert 减少sql 请求, 以后也拜托同行给数据时,请按 insert into tbl (a,b,c) values('a1','b1','c1') , ('...
SpringMVC上传图片文件到 腾讯云,前端使用Ajax,亲测可用。
2016年02月25日 18:09:10 kmcfly 阅读数:4972更多 个人分类: private 简单归纳:fd只是一个整数,在open时产生。起到一个索引的作用,进程通过PCB中的文件描述符表找到该fd所指向的文件指针filp。 文件描述符的...
cos腾讯云支持1.6的镜像文件cos腾讯云支持1.6的镜像文件cos腾讯云支持1.6的镜像文件cos腾讯云支持1.6的镜像文件
腾讯十年真实创业成长史:腾讯十年 一部真实的成长过程
腾讯数字生活报告2019-腾讯研究院-201905.pdf
腾讯云CentOS8_yum换源替换文件