题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。
关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。
分析:明显是一道工程性很强的题目,和一般的查找中位数的题目有几点不同。
1. 原数据不能读进内存,不然可以用快速选择,如果数的范围合适的话还可以考虑桶排序或者计数排序,但这里假设是32位整数,仍有4G种取值,需要一个16G 大小的数组来计数。
2. 若看成从N个数中找出第K大的数,如果K个数可以读进内存,可以利用最小或最大堆,但这里K=N/2,有5G个数,仍然不能读进内存。
3. 接上,对于N个数和K个数都不能一次读进内存的情况,《编程之美》里给出一个方案:设k<K,且k个数可以完全读进内存,那么先构建k个数的堆,先找出第0到k大的数,再扫描一遍数组找出第k+1到2k的数,再扫描直到找出第K个数。虽然每次时间大约是nlog(k),但需要扫描ceil(K/k) 次,这里要扫描5次。
解法:首先假设是32位无符号整数。
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~2^64-1,这里先不考虑溢出的情况。总共占用内存256M×8Byte=2GB。(64位整数占8个字节,每段使用一个64位整数,只对每段值进行计数)
2. 从前到后对每一段的计数累加,当累加的和超过5G时停止,找出这个区段(即累加停止时达到的区段,也是中位数所在的区段)的数值范围,设为 [a,a+15],同时记录累加到前一个区段的总数,设为m。然后,释放除这个区段占用的内存。
3. 再读一遍10G个整数,把在[a,a+15]内的每个值计数,即有16个计数。
4. 对新的计数依次累加,每次的和设为n,当m+n的值超过5G时停止,此时的这个计数所对应的数就是中位数。
总结:
1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线性时间。
2. 考虑其他情况。
若是有符号的整数,只需改变映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。
3. 时空权衡。
花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。
4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。
原文地址 http://www.cppblog.com/richbirdandy/
JavaEye问题出处http://www.iteye.com/topic/630831
分享到:
相关推荐
18 世纪以前的科学进步均属于此列,其核⼼特征是对有限的客观对象进⾏观察、总结、 提炼,⽤归纳法找出其中的科学规律,如伽利略提出的物理学定律。 "第⼆范式"是指 19 世纪以来的理论科学阶段,以模型和归纳为特征...
bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。...2)2.5亿个整数中找出
JAVA⼤数据处理题 ⼤数据处理题 1. 给定a、b两个⽂件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、... 海量数据分布在100台电脑中,想个办法⾼校统计出这批数据的TOP10。 ⽅案1: s 在每台电脑上求
适⽤范围:第k⼤,中位数,不重复或重复的数字 基本原理及要点:因为元素范围很⼤,不能利⽤直接寻址表,所以通过多次划分,逐步确定范围,然后最后在⼀个可以接受的范围内进⾏。 可以通过多次缩⼩,双层只是⼀个例...
课程内容: 第 1 课 面向小白的统计学:描述性统计(均值,中位数,众数,方差,标准差, 与常见的统计图表) 第 2 课 赌博设计:概率的基本概念,古典概型 第 3 课 每人脑袋里有个贝叶斯:条件概率与贝叶斯公式,...
Step3:找出每个⼩⽂中出现频率最⼤的IP(可以采⽤hash_map进⾏频率统计,然后再找出频率最⼤的⼏个)及相应的频率; Step4:在这1000个最⼤的IP中,找出那个频率最⼤的IP,即为所求。 草图如下:
一、BitMap 解决的问题:大数据量下的排序、查找、去重。 1、关键 通过 bit位 表示一个数值的状态(是否存在),那么1MB能大约表示 800万数值 (1,000,000B * 8 bit ) 2、局限性: ...找出没有重复的数
通过对海量词汇的对比,找出哪些是网民关注的。这就是大数据的应用。 第三个故事,阿里云知道谁需要贷款 这是阿里人讲述的一个故事。每天,海量的交易和数据在阿里的平台上跑着,阿里通过对商户最近100天的数据分析...
5、在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。 方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存内存,还可以接受。然后扫描这2....
物流市场有很强的动态性和随机性,需要实时分析市场变化情况 ,从海量的数据中提取当前的物流需求信息,同时对已配置和将要配置的资源进行优化 ,从而实现对物流资源的合理利用。 2)降低物流成本 由于交通运输、...
通过对海量词汇的对比,找出哪些是网民关注的。这就是大数据的应用。 第三个故事,阿里云知道谁需要贷款 这是阿里人讲述的一个故事。每天,海量的交易和数据在阿里的平台上跑着,阿里通过对商户最近100天的数据...
机器学习 安 防 曙能监控 安保机器人 商汤科技,格灵深輛、神州云海 机器人、计算机视 觉'图像识别 自动骂驶 智能找车、公共交通、快递出 车、工业应用 谷歌丄咯、特斯拉、亚马逊、奔驰 计算机观堂 医疗健嘰 医疗傩...
785.5.2 地球不是二维平面 78第6章 聚合 796.1 count 796.2 distinct 796.3 group 806.3.1 使用完成器 826.3.2 将函数做为键使用 846.4 MapReduce 846.4.1 例1:找出集合中的所有键 856.4.2 例2...
1.4.8. 计算 1 到 N 的十进制数中 1 的出现次数 ............................................. 97 1.4.9. 栈的 push、pop 序列[数据结构] .......................................................... 99 1.4.10....
2018年7月,疯狂游戏旗下的《海盗来了》月流水过亿,让无数开发者眼羡,他们旗下还有《头脑王者》等IP,开发实力超强,品质均属上乘,并且已经积累了海量的用户和口碑,作为游戏入口的公众号矩阵用户也达到了数千万...