`

【腾讯】10G整数文件中寻找中位数

阅读更多

题目:在一个文件中有 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个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。关于快排的效率,可以看看我博客中的数据《基于比较的内部排序总结 》。

分享到:
评论
8 楼 荆棘鸟崽崽 2012-09-07  
blackdog1987 写道
bingjing12345 写道
futrueboy 写道
这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32,占4g内存,如果是正整数的话,应该可以。


位图是可以做的
2^32  =  4g
考虑二分法

读入所有的整数(当然分批次,这种细节我就不再说了)
所有整数转换为2进制  有   0 XXXX     1 XXXX
将0开头的输出到文件A,1开头的输出到文件B
用一个变量n记录0开头的数据个数

1、n>4G/2  则表示较小的数据更多,中位数未于A文件中。A文件读入,采用位图法(已经去掉第一位了,内存只需要2G了),从而找到所有数的详细情况。然后减去B中的数量的个数(从大到小减,保证最大的X个数和最小的X个数成对)剩下的再来找,简单了吧
2、n<4g/2  同上,不赘述
3、n==4g/2  这是最简单的情况了,说明大数,小数的数量均匀分布在两边,从A文件中找出最大的一个数(及其个数),从B文件中,找出最小的一个数,两个数,谁多,中位数就是谁,如果一样多,那么中位数就是两个


你这解法完全不对。。。n>4G/2,是错的,应该是n>5G,A文件只需2G是错的,你2G全用来做位图(只能记录0/1,只有1bit.)失去了个数的统计。相互抵消怎么处理?
你的思路其实和楼主差不多,你10G的文件分成两份显然还是处理不了的,分成255分则好些,实在不行分成1024份,单个文件的大小就难超过2G了。
7 楼 blackdog1987 2012-08-16  
bingjing12345 写道
futrueboy 写道
这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32,占4g内存,如果是正整数的话,应该可以。


位图是可以做的
2^32  =  4g
考虑二分法

读入所有的整数(当然分批次,这种细节我就不再说了)
所有整数转换为2进制  有   0 XXXX     1 XXXX
将0开头的输出到文件A,1开头的输出到文件B
用一个变量n记录0开头的数据个数

1、n>4G/2  则表示较小的数据更多,中位数未于A文件中。A文件读入,采用位图法(已经去掉第一位了,内存只需要2G了),从而找到所有数的详细情况。然后减去B中的数量的个数(从大到小减,保证最大的X个数和最小的X个数成对)剩下的再来找,简单了吧
2、n<4g/2  同上,不赘述
3、n==4g/2  这是最简单的情况了,说明大数,小数的数量均匀分布在两边,从A文件中找出最大的一个数(及其个数),从B文件中,找出最小的一个数,两个数,谁多,中位数就是谁,如果一样多,那么中位数就是两个
6 楼 bingjing12345 2012-08-04  
首先, 你没有审对题。 题目是10G个  int型数, 你做的是10G整数。
其次,即使你做的是对的,也应该选16bit。
再次,这些数据没说是均匀分布的,用桶排序时,桶的大小不确定。有链式存储,影响效率。并且你没有考虑桶排序的空间复杂度,将2G数据读到内存后,内存已经用完了,辅助空间没地方分了。
5 楼 bingjing12345 2012-08-04  
futrueboy 写道
这题我怎么觉得用位图就可以做的

位图做不了
整数总范围是2^32,占4g内存,如果是正整数的话,应该可以。
4 楼 explore 2012-05-29  
两个地方比较困惑:1,为什么8bits(-128到127)最多只能表示255个桶,不是256?2.10G/128=80M 是怎么得出来的哪
3 楼 futrueboy 2011-10-12  
这题我怎么觉得用位图就可以做的
2 楼 liuxinglanyue 2010-12-23  
(平均而言,每个文件的大小估计在10G/128=80M左右,当然也不一定,但是超过2G的可能性很小)

一开始以为是除以255,原来作者用的是概率来做的呀。
学习了。
1 楼 frankwan 2010-04-27  
排序算法与查找算法都写的很好,比教科书容易理解多了

相关推荐

    腾讯公司C_C++笔试题

    每个字符(数字)对应链表中的一个节点,通过遍历两个数的每一位,逐位进行乘法和累加操作。 6. 操作系统:虽然题目没有直接涉及操作系统,但作为腾讯的笔试题,可以推断出可能会有对操作系统基础知识的考察,如...

    腾讯笔试题2010

    - 在内存限制的情况下,需要从10G个乱序整数中找出中位数。 **知识点详细解析**: - **初步筛选**:将整数空间划分为256M个取值范围,统计每个范围内的整数个数。 - **细化搜索**:确定中位数所在的范围后,进一步...

    腾讯2016研发工程师编程题

    根据给定文件的信息,我们可以分析出这是一组与腾讯2016年研发工程师笔试相关的编程题目。在这些题目中,我们主要关注两个问题:一个是关于格雷码(Gray Code)的问题;另一个则是关于礼物(gifts)分配的问题。下面我们...

    海量数据处理 百度、腾讯、Google面试

    1. **双层桶划分**:双层桶划分是一种处理海量数据的算法设计思想,适用于寻找第k大数、中位数以及不重复或重复数字的问题。当数据量过大,无法一次性处理时,通过多次划分数据,逐步缩小处理范围,最终在可接受的...

    腾讯俱乐部ACM训练赛进阶组解题报告.pdf

    进一步地,可以证明如果存在一段连续长度为m1 (其中m1是这些数字中的最小值) 的整数序列,使得这段序列中的每个数都可以通过给定数字的整数倍表示出来,则之后的任意数也都可以表示出来。因此,可以通过动态规划的...

    腾讯考试题.docx

    1. **内存限制下的整数查找**:这是一个典型的计算机科学问题,要求在有限内存条件下找出40亿个整数中缺失的一个。解决方案通常涉及外部排序和哈希表。可以先将内存分为多个块,读取每个块的整数,计算其与所有已...

    腾讯历年面试试题汇总

    与0x1(即2的31次方,32位系统中最大的正整数)进行按位与操作,得到的结果是0x1,然后右移31位,得到0或1,从而实现大小比较。 2. 输出源文件标题和当前行数:这段代码利用预处理器宏`__LINE__`和`__FILE__`来获取...

    腾讯笔试试题整理(包括答案)

    ### 腾讯笔试知识点详解 #### 一、笔试流程及内容概述 - **笔试流程**:腾讯的招聘流程通常包含一次...以上就是基于“腾讯笔试试题整理(包括答案)”文件中的知识点总结,希望能够帮助到准备参加腾讯笔试的朋友们。

    腾讯试题.pdf

    宏的定义使用#define指令,并且可以用来进行编译时的计算或函数式编程,如文件中提到的比较两个数a、b大小的宏定义。 - 宏定义可以实现代码的复用,例如在宏中使用三元运算符或其他逻辑来模拟if语句的功能,但宏不...

    易语言计算QQ空间G_tk值

    综上所述,这个“易语言计算QQ空间G_tk值”的项目中,开发者需要理解易语言的基本语法,掌握十六进制与十进制之间的转换,了解ANSI与UNICODE字符编码的区别以及如何进行转换,并能灵活运用字符串到整数的转换函数。...

    腾讯笔试题及其答案

    ### 腾讯笔试题解析 #### 题目一:过桥问题 **题目描述**:假设A、B、C、D四个人要在黑夜中过一座桥,他们各自通过这座桥所需的时间分别是1分钟、2分钟、5分钟、10分钟。桥上只能容纳两个人同时通过,并且他们必须...

    BAT面试题——海量整数,找出不重复整数

    【海量整数中找出不重复整数的问题】是面试中常见的数据处理挑战,尤其是在BAT(百度、阿里巴巴、腾讯)这样的大型互联网公司。这个问题的核心在于如何有效地处理大量数据,尤其是在内存有限的情况下。 首先,我们...

    数据结构与算法 腾讯精选练习50 V1.0.pdf

    - 寻找两个有序数组的中位数(Day02):考查二分查找算法的使用和对有序数据进行查找的效率。 - 最长回文子串(Day03):学习字符串处理和动态规划的解题思想。 - 整数反转(Day04):练习对于整数运算和边界条件的...

    腾讯笔试题1.doc

    腾讯笔试题经常考察优化算法以降低时间复杂度,如在海量数据中寻找最大值或最小值,或高效排序。 12. **逻辑思维与智力题**: 笔试中可能包含逻辑题和智力题,例如桥的问题,需要策略规划和时间优化。 13. **C++...

    腾讯公司考试题

    从给定的文件信息中,我们可以提取出一系列与IT行业相关的知识点,主要集中在算法、编程、数据结构以及数据库管理等方面。下面将详细解析这些知识点: ### 知识点1:算法设计与分析 #### 例题1:桥过河问题(时间...

    TensorflowTTS fastspeech2 mbmelgan 中文模型 .tflite文件

    `fastspeech2_quant_zh.tflite` 是FastSpeech2模型的量化版本,它通过减少模型的精度(例如,从浮点32位转换为16位或8位整数),进一步减小了模型的大小,以适应更有限的计算资源。`mbmelgan_zh.tflite` 则是...

Global site tag (gtag.js) - Google Analytics