欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

}

上一篇: POJ:3273-Monthly Expense

下一篇: