精华内容
下载资源
问答
  • 题目:在一个文件中有 10G 个整数,乱序排列,要求中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。 关于中位数:...

    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

    关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

    分析: 既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法 

    思想:将整形的每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个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

    展开全文
  • 题目:在一个文件中有 10G 个整数,乱序排列,要求中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。关于中位数:数据...

    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

    关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

    分析:既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法

    思想:将整形的每1byte作为一个关键字,也就是说一个整形可以拆成4个keys,而且最高位的keys越大,整数越大。如果高位keys相同,则比较次高位的keys。整个比较过程类似于字符串的字典序。

    第一步:把10G整数每2G读入一次内存,然后一次遍历这536,870,912个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶,那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中,同时在内存中统计每个桶内数据的数量,自然这个数量只需要255个整形空间即可。

    代价:

    10G数据依次读入内存的IO代价(这个是无法避免的,CPU不能直接在磁盘上运算)。

    在内存中遍历536,870,912个数据,这是一个O(n)的线性时间复杂度。

    把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的可能性很小)。

    代价:

    循环计算255个桶中的数据量累加,需要O(M)的代价,其中m<255。

    读入一个大概80M左右文件大小的IO代价。

    注意,变态的情况下,这个需要读入的第128号文件仍然大于2G,那么整个读入仍然可以按照第一步分批来进行读取。

    第三步:继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同,也是255个桶。

    第四步:一直下去,直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

    整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上,即10G数据分255个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

    欢迎点赞+收藏+转发朋友圈素质三连

    文章不错?点个【在看】吧!👇

    展开全文
  • 题目:在一个文件中有 10G 个整数,乱序排列,要求中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的...

    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

    关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

    分析: 既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法 

    思想:将整形的每1byte作为一个关键字,也就是说一个整形可以拆成4个keys,而且最高位的keys越大,整数越大。如果高位keys相同,则比较次高位的keys。整个比较过程类似于字符串的字典序。

    第一步:把10G整数每2G读入一次内存,然后一次遍历这536,870,912个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶,那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中,同时在内存中统计每个桶内数据的数量,自然这个数量只需要255个整形空间即可。

    代价:

    10G数据依次读入内存的IO代价(这个是无法避免的,CPU不能直接在磁盘上运算)。

    在内存中遍历536,870,912个数据,这是一个O(n)的线性时间复杂度。

    把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的可能性很小)。

    代价:

    循环计算255个桶中的数据量累加,需要O(M)的代价,其中m<255。

    读入一个大概80M左右文件大小的IO代价。

    注意,变态的情况下,这个需要读入的第128号文件仍然大于2G,那么整个读入仍然可以按照第一步分批来进行读取。

    第三步:继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同,也是255个桶。

    第四步:一直下去,直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。

    整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上,即10G数据分255个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

    欢迎点赞+收藏+转发朋友圈素质三连

    文章不错?点个【在看】吧! ????

    展开全文
  • ...文件中有10G个整数,乱序排列,要求中位数  (2010-09-25 18:15:03) 转载▼ 标签:  杂谈 分类: 算法   题目:在一个文件中有 10G 个整数

    链接:http://blog.sina.com.cn/s/blog_62714d6a0100m96m.html


    文件中有10G个整数,乱序排列,要求找出中位数

      (2010-09-25 18:15:03)
    标签:  

    杂谈

    分类: 算法

     

    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

     

    关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

     

    分析: 既然要找中位数,很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法 

    思想:将整形的每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个文件写回磁盘上。一般而言,如果第二步过后,内存可以容纳下存在中位数的某一个文件的话,直接快排就可以了。

    展开全文
  • 关于吸血鬼数字算法问题,我也是读《java编程思想》遇到的,觉得很有意思。于是,就去做了做。但因为我的粗心,读题的时候忽略了点问题,所以导致我的思路出现了岔口!(当时的思路就是想着把一个4位数拆分成两个2...
  • 当时很迷惑,为什么面试官总喜欢找中位数?后来了解到快速排序算法的思想后,发现如果大概知道待排序数组中位数的大小(或者提前找出中位数),将在数量级上提高快速排序算法的效率,这个后面有空再讲。 如果你想先...
  • 例如 8314925去掉4个,留下125最小,注意有前后...那么这个m,最高应该在原的最高到第m区间,要不然就不能当第m了,如下图(得到3位数最小,要是百位数在25中找,就当不了百位了):  
  • 1、如果数据量不大,千万以下级别的,可以用一个数组保存所有的int,然后排序,相邻两个元素,时间复杂度为O(nlogn) 2、如果数据量很大,内存无法保存所有的数据,这样就不能够使用排序的算法,这时可以考虑状态...
  • 例如 8314925去掉4个,留下125最小,注意有前后顺序...那么这个m,最高应该在原的最高到第m区间,要不然就不能当第m了,如下图(得到3位数最小,要是百位数在25中找,就当不了百位了): 同样...
  • 一组数据只有一个数字出现了一次。 其他所有数字都是成对出现的。 请出这个数字。(使用运算) **思想:**怎样证明是成对出现呢,可以用异或运算,1:因为自己和自己异或肯定会变成0;:2:c=a^ b; d ^ c = d^...
  • 我们不能等着系统上线,慢 SQL 吃光数据库资源之后,再出慢 SQL 来改进,那样就晚了。那么,怎样才能在开发阶段尽量避免写出慢 SQL 呢?01定量认识MySQL一台 MySQL 数据库,大致处理能力的极限是,每秒一万条左...
  • 大家都知道,在BIEE,我们一般通过字段属性的数据格式来设置我们想要的格式,比如只保留两...1、随便一个浮点类型的字段(物理层字段类型为DOUBLE),按照上图1的进行设置 2、在右下角的“另存为默认值”下拉
  • 首发公众号:码农架构我们不能等着系统上线,慢 SQL 吃光数据库资源之后,再出慢 SQL 来改进,那样就晚了。那么,怎样才能在开发阶段尽量避免写出慢 SQL 呢?定量认识 MySQL 一台 MySQL 数据库,大致处理能力的...
  • 但不管怎样,还是要读一读,因为这是迄今为止唯一一本试图回答你“模糊”问题的书。在有趣的是,bin函数确实存在!它几乎完全符合你的要求。(它在前面加了一个0b,但是因为你是从右边的,所以没关系。)抓包是编程...
  • 【简答题】任意两个几何体组合光影素描【计算题】1,2,3,4,5,6,7,8,9,【计算题】1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3【计算题】编程判断...【计算题】【填空题】计算机系统通常采用三级存储器结构,即 ( ) 、 主...
  • EXCLE表单元格数值从元如何变成万元1、在另一列单元格,用原来单元格的数值除以10000,即可得到万元;2、在另一列单元格输入=ROUND(A6,-4),也可得到万元。...excel表格金额如何将元变成万元个空白单元格...
  • 重点: 如何将问题 与 数位DP相关. 将整个问题 分成小问题的话. 就是 当一个满足 题设条件时. 它具有怎样的性质. 然后 就是去构造这个. 一个的阶乘有多少个 0 就是 阶乘的因子有多少个5. 先看看如果是暴力的...
  • 一个int比如322,我想happy number就得3平方加2平方再加2平方,怎样找到一个一个的数字,就是322%10,得到2,然后/10,然后再%,就可以依次求得每上的数字 happy number需要考虑的循环的问题,处理循环可以...
  • ``` #include #include using namespace std; //#define MaxValue 10000; //初始设定的权值最大值 //#define MaxBit 4;...怎样在main函数调用上面的void haffman函数,请大家帮忙看看,谢谢了!!!
  • ``` #include #include using namespace std; //#define MaxValue 10000; //初始设定的权值最大值 ...怎样在main函数调用上面的haffmancode函数,急求解答,各位能人帮帮忙吧,谢谢!!!
  •  第五条色环:误差(常见是棕色,误差为1%)在实践发现,有些色环电阻的排列顺序不甚分明,往往容易读错。在识别时可运用如下技巧加以判断,具体内容如下: 技巧1:先标志误差的色环,从而排定色环顺序。最常用...
  • 问题:怎样找出某个集合的所有子集,怎样找出某个集合指定元素个的所有子集? 思路:对集合所有元素进行标记,0表示未选中,1表示选中。假如有一个集合有3个元素为 {1,2,3}, 则 000 表示一个都不选, 001表示...
  • 目录 题目 ...题目明确表明除了这个单一元素外,其它元素均出现两次,那么如果其它元素两两抵消,那么最终剩下的元素不就是这个单一元素了嘛!怎样才能让相同的元素两两抵消呢?运算异或操作-...
  • 问题:怎样找出某个集合的所有子集,怎样找出某个集合指定元素个的所有子集? 思路:对集合所有元素进行标记,0表示未选中,1表示选中。假如有一个集合有3个元素为 {1,2,3}, 则 000 表示一个都不选, 001表示...
  • discuz的验证码是怎样被破解的

    千次阅读 2009-11-21 16:52:00
    应该说这个验证码已经挺复杂的,主要是字体比较奇怪,如果不到字体,用简单的模式匹配解码很难。 discuz的验证码只有四数字,用穷举的方式暴力破解,最多只需要10000次(0000-9999)就可以找到正确的验证码
  • 习题3-3 乘积的末3

    2016-08-13 09:58:32
    输入若干个整数(可以是正数、负数或者零),输出它们的乘积的末3。...出字符串的数字累乘,在计算过程注意字符串结束判断和溢出异常。#include <stdio.h> #include <string.h> #include <ctype.h>

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 212
精华内容 84
关键字:

怎样找中位数