在10亿个数中找出前1000个最大的

80 阅读 0 评论 53 点赞

我是靠谱客的博主傲娇小熊猫，最近开发中收集的这篇文章主要介绍在10亿个数中找出前1000个最大的，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在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();
    }

}