10G数中找到前5G大的数

简介: 处理海量数据常用【堆排序】:(1)不需要一次性将所有数据加载到内存中;

堆排序(转换为求前5G大的元素)

处理海量数据常用【堆排序】:

(1)不需要一次性将所有数据加载到内存中;

(2)不用对所有元素进行排序,只需要和堆的根结点比较大小即可;

(3)对于海量数据而言,要求前k小/大的数,我们只需要构建一个k个大小的堆,然后将读入的数依次和根节点比较就行了(当然这里的前提是内存需要存的下k个数)

最大堆求前n小,最小堆求前n大。

1、前k小:

构建一个k个数的最大堆,当读取的数大于根节点时,舍弃;当读取的数小于根节点时,替换根节点,重新塑造最大堆,然后继续读取,最后读取完所有的数据之后,最大堆中的数就是最小k个数

2、前k大:

构建一个k个数的最小堆,当读取的数小于根节点时舍弃;当读取的数大于根节点时,替换根节点,重新塑造最小堆,然后继续读取,读取完所有的数据之后,最小堆中的数就是最大k个数

所以我们本题采用堆排序来求中位数

对于10G的数据,它的中位数就是第5G个元素,按常理来说我们需要构建一个5G大小的堆,但是允许的内存只有两个G,所以我们先构建一个1G大小的大顶堆,然后求出第1G个元素(根节点),然后利用该元素构建一个新的1G大小的堆,求出第2G大的元素,依次类推,求出第5G大的元素

每次构建一个堆求第几G大的元素,都需要重新遍历完所有10G的数据,相当于要遍历5 * 10G次,这需要频繁的IO操作,需要不断的从硬盘中读取数据

另外

还有其他方法,参考(https://zhuanlan.zhihu.com/p/75397875

相关文章
|
7月前
|
算法
给定两个数,求这两个数的最大公约数
给定两个数,求这两个数的最大公约数
|
C语言
C 语言实例 - 判断三个数中的最大数
C 语言实例 - 判断三个数中的最大数。
159 36
|
7月前
2.任意输入三个数,求最大数
2.任意输入三个数,求最大数
39 0
|
7月前
|
算法 测试技术 C#
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
判断数的奇偶性
判断数的奇偶性
99 0
|
机器学习/深度学习
欧拉函数:求小于等于n且与n互质的数的个数
求小于等于n且与n互质的数的个数 互质穷举法 互质:两个数互质代表两者最大公约数为1 最大公约数求法:辗转相除法,最小公倍数:较大值除以最大公约数乘以较小值 辗转相除法: 较大的数a取模较小的数b,得取模值c 若取模值等于0 则最大公约数为取模值,否则继续下一步 a与c再次取模,回到第二步 //求最大公约数gcd以及最大公倍数lcm // 36 24 36/24 // 24 12 24/12 // 0 结束最大公约数为12 // 求最小公倍数 // lcm(a, b) = (a * b)/g
151 0
【那些年那些题】杨氏矩阵查找目标数
【那些年那些题】杨氏矩阵查找目标数
43 0
|
C语言
求十个数中最大的数
C语言求十个数中最大的数流程图
63 0
求十个数中最大的数
AcWing 742. 最小数和它的位置
AcWing 742. 最小数和它的位置
69 0
AcWing 742. 最小数和它的位置
|
测试技术
软件测试面试题:如果一个数恰好等于它的因子之和,则称该数为“完全数”,又称完美数或完备数。 例如:第一个完全数是6,它有约数1、2、3、6,除去它本身6外,其余3个数相加, 1+2+3=6。第二个完全
软件测试面试题:如果一个数恰好等于它的因子之和,则称该数为“完全数”,又称完美数或完备数。 例如:第一个完全数是6,它有约数1、2、3、6,除去它本身6外,其余3个数相加, 1+2+3=6。第二个完全
471 0