在10亿个数中找出前1000个最大的
程序员文章站
2024-03-15 21:43:36
...
在10亿个数中找出前1000个最大的
假设现在有一个文件,里面存放了10亿个整数,需要找出前1000个最大的。
方法:
1、普通排序,部分排序:几乎不可取。
2、分治法:随机选一个数t,然后对整个数组进行partition,会得到两个部分,前一个部分都是大于t,后一个部分都是小鱼t,然后判断个数,继续进行。
3、分布式:将数据分块到n个机器上,分别取top1000,然后合并。
4、堆操作:维护一个1000个节点的订堆。
5、用数组实现:先取出1000个数据排序成数组A,然后每次从剩下取一个数和数组A比较,删除与插入。
方法1:
10亿个数几乎无法全部加载到内存中,如果内存大小为2G,所以冒泡排序这种方式不可行。
方法2:
先选择一个数t,一般先选择第一个数,然后以t为标准,将数组拆分成数组A和数组B;并且A都小于t,B都大于t;
如果B刚好为1000个,则B就是结果。
如果B大于1000个,则继续在B中拆分。
如果B小于1000个,则在A中继续拆分,寻找剩下的部分。
同样存在的问题就是内存限制,只能拆分成多个文件,然后分别统计top1000,最后汇总;但是这种方式进行了多次磁盘的读写,效率很低。
方法3:
使用多台机器,是对方法1和2的补救,不是很合理,实现个功能还大动干戈。
方法4:
维护一个1000个节点的顶堆,根据堆的特点,每一个子节点都比他的左右子节点要小。
先去1000个数构成小顶堆,然后从文件中读取数据,如果比对顶还小,就直接丢弃,否则重新调整堆,所以数据处理完毕后,堆就是top1000。
方法5:
和方法4类似,只是将堆换成了数组。
关于使用file_get_contents分步读取文件
一下是堆的操作:
public class TopN {
// 父节点
private int parent(int n) {
return (n - 1) / 2;
}
// 左孩子
private int left(int n) {
return 2 * n + 1;
}
// 右孩子
private int right(int n) {
return 2 * n + 2;
}
// 构建堆
private void buildHeap(int n, int[] data) {
for(int i = 1; i < n; i++) {
int t = i;
// 调整堆
while(t != 0 && data[parent(t)] > data[t]) {
int temp = data[t];
data[t] = data[parent(t)];
data[parent(t)] = temp;
t = parent(t);
}
}
}
// 调整data[i]
private void adjust(int i, int n, int[] data) {
if(data[i] <= data[0]) {
return;
}
// 置换堆顶
int temp = data[i];
data[i] = data[0];
data[0] = temp;
// 调整堆顶
int t = 0;
while( (left(t) < n && data[t] > data[left(t)])
|| (right(t) < n && data[t] > data[right(t)]) ) {
if(right(t) < n && data[right(t)] < data[left(t)]) {
// 右孩子更小,置换右孩子
temp = data[t];
data[t] = data[right(t)];
data[right(t)] = temp;
t = right(t);
} else {
// 否则置换左孩子
temp = data[t];
data[t] = data[left(t)];
data[left(t)] = temp;
t = left(t);
}
}
}
// 寻找topN,该方法改变data,将topN排到最前面
public void findTopN(int n, int[] data) {
// 先构建n个数的小顶堆
buildHeap(n, data);
// n往后的数进行调整
for(int i = n; i < data.length; i++) {
adjust(i, n, data);
}
}
// 打印数组
public void print(int[] data) {
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
推荐阅读
-
在一亿个数据中找出最大的100个
-
在Java中找出1到n个数字之间的重复数
-
从一个无序的数字序列中查找出前K个最大的数字[递归方式] 博客分类: algorithm TopKAlgorithmJava
-
洛谷OJP1008在1~9共9个数字中找出三个三位数,使它们的比例为1:2:3
-
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的 两个 整数。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素
-
php中在输入的数中找出最大值没有解决.希望得到大家的帮助解决方法
-
php中在输入的数中找出最大值没有解决.希望得到大家的帮助解决方法
-
算法设计与分析(第一篇)(分治与递归)(二分查找)在n+logn-2次比较中找出a[n]的最大元素与次大元素
-
php中在输入的数中找出最大值没有解决.希望得到大家的帮助解决方法
-
100亿个数中找出最大的前K个数(海量TopK问题)