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

大数据Top K问题

程序员文章站 2024-03-15 21:39:06
...

大数据下的2个Top K场景:

1、 1亿个数字中找出最大或最小的前100个数字(考虑判重和内存空间限制)?

思路: 考虑将数字分散存储在不同文件中, 然后依次读取各个文件, 例如1~10000存到1.txt、 2~20000存到2.tx、以此类推;

        如果不判重,可以将前100个数字做成最大堆或最小堆的数据结构(找最大的Top100用最小堆, 找最小的Top100用最大堆), 然后依次遍历所有数字, 符合条件时替换根节点后并重新构建堆。堆的缺点是允许有重复数字!!!

        如果要判重,则创建一个100个空间的空数组, 遍历1亿个数字依次插入值(按照升序), 使用二分查找算法判断新值在数组中的位置并插入, 该数组最多容纳100个值。 当有101个值时先判重, 如果重复继续向后遍历, 如果值大于数组最小值则插入到指定位置,数组第一个元素移出数组, 因为数组是连续的,所有可以用内存拷贝方式赋值,只有新插入的值要单独赋值到对应的下标(原理类似于android.util.SparseArray)。   因内存拷贝可认为不占用时间, 该思路的总会时间复杂度是O(1亿*log100), log100是二分查找的复杂度。

  

2、 1亿个搜索关键词找出次数最多的前100个搜索词(考虑内存空间限制)? 

思路: 核心是“分治”、“归并”和哈希,  第一次遍历将关键词散列到不同的文件中(散列算法是性能关键,哈希函数的性能直接影响散列的结果, 尽量避免数据倾斜), 同一个关键词一定会散列到同一个文件, 理想情况是所有关键词均匀散列到不同的文件中(即分治思想,将大文件分解为小问题)。

       读取每个文件并记录各关键词的次数, 做个冒泡排序, 从每个文件中排序出前100的关键词;

       取第一个文件的记录结果, 和第二个文件做合并, 即200个结果中排序出前100个关键词, 然后依次合并第三个、第四个。。。。第N个文件(将子结果合并为总结果)。


PS:   大道同源, 我想到2个类似的场景。

1、 电脑里有众多的文件,但我们还是能从众多文件中找到你想要的。 这是为什么呢?  因为使用了文件夹, 按照文件类型保存在各个层级的目录里。 这个目录层级跟”在1亿个搜索词中找出频率最高的100个“的解决思路是一样的, 即将关键词分散存储到不同的文件里(也可以使用层级目录, 目录越深分散的粒度越细, 到底分几个文件/目录层级其实是时间空间的权衡)

2、 数据库用户表里要存储几亿个记录,该怎么办? 跟上面管理电脑文件的问题类似, 可以按地域、年龄、姓名等等因素将数据存储到N张表里, 术语叫做”横向切割“


名词解释:

1、”数据倾斜“是大数据里的一个概念,就是数据集中到几个文件、处理器, 没均匀分散到各个处理单元。说白了就是忙的忙死,闲的闲死。

2、”分治“就是将大问题分解为小问题, 处理每个小问题并得到结果, 然后将所有子结果汇总成最终结果。

3、”横向切割“是数据库的一个概念, 就是将表记录分散存储到不同的表里,每个表里的记录都是完整的。 还有个“纵向切割”,就是将分拆表的列为多个表, 即一条记录要存到多张表里且每个表只存几个属性。 

4、“哈希”即散列, 就是通过哈希值找到存储位置, 理想情况下时间复杂度O(1)。 


下面开撸堆排序算法和代码:

       堆是个完全二叉树, 节点先从上到下后从左到右都是满的, 说白了叶子节点可以不满且非叶节点都有。 用Java数组形容的话, 数组下标从0到N-1。 如果节点i有左子树,那么左子树的下标是2i+1;如果节点i有右子树,那么右子树的下标是2i+2;如果有父节点,对应下标是(i-1)/2取整。

       堆分为最大堆和最小堆,也可以叫大根堆和小根堆; 最大堆的定义是任意子树根节点大于或等于子节点,所以根节点是最大值; 最小堆的定义是任意子树根节点小于或等于子节点, 所以根节点是最小值。

       堆排序思想是先构造堆,然后做N次循环, 每次交互根节点和最后一个值(最后节点是递减的)重新构建堆。

       构造堆是堆排序的核心, 算法是从最后一个非叶节点(即N/2)开始,先从右到左后从下到上依次判断交换值。详见堆排序动画: http://www.benfrederickson.com/heap-visualization/


 使用最小堆找出最大的前10个数字:

 //得到最大的前length个数字, 使用最小堆数据结果,理论上可能有重复数字
    public static void topNums(final int length)throws Exception{
        Scanner scanner=new Scanner(new FileInputStream("input.txt"));

        long array[]=new long[length];
        for(int i=0; i<array.length; i++){
            array[i]=scanner.nextLong();
        }

        buildMinHeap(array); //构造小顶堆

        while (scanner.hasNextLong()){
            long value = scanner.nextLong();

            if(value < array[0]) {
                continue;   //根节点是数组最小值, 如果当前值比最小值还小就跳过
            }

            array[0] = value;   //丢掉根节点,即替换array[0]
            ajustHeap(array, length,0);  //重新构造小根堆
        }

        //将一个小根堆进行排序,用堆排序思想
        heapSort(array);

        for(int i=0; i<length; i++)
            System.out.println(array[i]);

        scanner.close();
    }



    public static void main(String[]args)throws Exception{
        randomData();  //生成随机数并保持到文件里
        long start=System.currentTimeMillis();
        topNums(10);   //从文件中找出最大的前10个数字
        long end=System.currentTimeMillis();
        System.out.println(end-start);


        //验证堆排序是否正确的测试数据
        long[] array = {1, 3, -1, -5, 5, 10, 20, -10, 100, 30, 11, 16};
        System.out.println("原始数组:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        heapSort(array);
        System.out.println("排序后:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

    }

    //得到从大到小的降序
    public static void heapSort(long[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        buildMinHeap(array);  //构造堆

        for (int i = array.length - 1; i >= 1; i--) {
            long temp = array[i];
            array[i] = array[0];
            array[0] = temp;

            ajustHeap(array, i, 0);  //重新调整第0个下标节点
        }
    }

    //构造小根堆
    private static void buildMinHeap(long[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int half = array.length / 2;
        for (int i = half; i >= 0; i--) {
            ajustHeap(array, array.length, i);
        }
    }

    //构造小顶堆, 按照分治的思想递归
    private static void ajustHeap(long[] array, int heapSize, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;

        int smallest = index;
        if (left < heapSize && array[left] < array[index]) {
            smallest = left;
        }

        if (right < heapSize && array[right] < array[smallest]) {
            smallest = right;
        }

        if (index != smallest) {
            long temp = array[smallest];
            array[smallest] = array[index];
            array[index] = temp;

            ajustHeap(array, heapSize, smallest);
        }
    }

    //随机生成100000个数字并保存到文件里
    public static void randomData()throws Exception{//随机100万数据

        File file=new File("input.txt");
        if(!file.exists())
            file.createNewFile();

        PrintStream printStream=new PrintStream(new FileOutputStream(file));

        Random random=new Random(System.currentTimeMillis());

        for(int i=0;i<1000000;i++){
            long k=Math.abs(random.nextLong());
            printStream.println(k);
            //printStream.println(k);  //连续写2个相同值, 验证使用堆得到的top k结果有重复数字
        }
        printStream.close();
    }

       其中adjustHeap函数是核心函数, 思想是找出当前节点、左子节点、右子节点的最大或最小值, 如果当前节点已经是最大或最小则退出, 否则交换当前节点和子节点的值,然后递归处理子节点, 这是“分治法“的体现。

构造堆结果也可以使用非递归的方式实现:

    //构造最大堆的非递归实现
    public void adjustHeapExt(long[] array, int parent, int length) {
        long temp = array[parent];
        int child = 2 * parent + 1;  //左子节点

        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;   //右子节点比左子节点更大
            }
            
            if (temp >= array[child]) {
                break;  //当前节点最大则退出
            }
            
            array[parent] = array[child];  //替换根节点的值
            
            parent = child;  //向下遍历
            child = 2 * child + 1;  //从左子节点开始比较
        }
        array[parent] = temp;   //存储原根节点值
    }

  补充一下: 1亿个数字找出top 100的二分查找原理, 对于有序数组先比较array[0], 然后二分查找并数组前移、后移加上赋值。  

大数据Top K问题

摘自SparsArray.java

 /**
     * 二分查找数据中是否存在值
     * @param array,数组,升序数组
     * @param value,要查找的值
     * @return  找到就返回数组下标, 找不到就返回负数(需要插入的位置)
     */
    static int binarySearch(long[] array, long value) {
        int lo = 0;
        int hi = array.length - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final long midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

     小结, 对于大数据第一步是要"分治”,  “分治”算法是影响性能的关键。