10亿条数据找出最大的1000个数
10亿条数据找出最大的1000个数
文川simple 发表于3个月前
10亿条数据找出最大的1000个数
  • 发表于 3个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

方法1:全部排序(适合大内存)

先利用快拍全部排序,在提取最大的1000个数。单机+单核+足够大内存复杂度O(nlogn)。

方法2:局部淘汰法

先排序个10000个数据maxs数组,然后之后的数据和最小的相比较,大于最小的说明之前的最小值不是最大的10000个数。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000。在maxs数组插入新的数据之后的排序必须要优化,否则会造成很大的不必要的排序。

方法3:分治法 (适合小内存)

将一亿个数据分为100分,没分100万数据。依次取每组的前10000大的数据,最后通过分治进行merge操作。

方法4:Hash法

没接触过

方法5:堆排序(最优)

思想类似于方法2,构建小根堆,剩下的元素和最小的(堆顶)进行比较,如果小于最小的,说明肯定不是最大的10000个数。 为什么要构建小根堆? 如果是大根堆的话,与堆顶元素的比较,不管是大于还是小于,都难以取舍,既不能判断该数是否是10000个最大数之一。

show you the code //快排的代码见第6题

package a_a_problems;

import Utils.ArrayUtils;
import g_quicksortupdate.QuickSort;
import g_quicksortupdate.QuickSort2;
import g_quicksortupdate.QuickSort33;

import java.util.Arrays;

/**
 * Created by tangwc on 2017/8/20.
 */
public class Top10000 {

    /**
     * 方法1:利用快排全部排序,内存要求高,单线程
     */
    public static int[] top1000AllSort(int[]arr){
        QuickSort33.quickSort(arr);

        return Arrays.copyOf(arr, 10000);
    }

    /**
     * 方法2:先找10000个数排序,之后的数与其最小的数进行比较,
     * 如果小于则跳过,大于则替换,再排序。遍历完之后剩下的10000size的数组就是最大数组
     */
    public static int[] top1000First10000(int[] arr){
        int index = 10000;
        int[] maxs = Arrays.copyOf(arr, index);
        QuickSort33.quickSort(maxs);//利用快排先将10000有序方便查找最小值与之后的数进行比较
        for(int i = 10000;i<arr.length;i++) {
            if(arr[i]>maxs[0]){
                maxs[0] = arr[i];
                //QuickSort33.quickSort(maxs);//如果用快排将会耗费大量的时间比较原本有序的序列,应该用优化过的插入排序
            }
        }
        return maxs;
    }
    //方法2的改进,提高性能
    public static int[] top1000First10000_2(int[] arr){
        int index = 10000;
        int[] maxs = Arrays.copyOf(arr, index);
        QuickSort33.quickSort(maxs);
        for(int i = 10000;i<arr.length;i++) {
            if(arr[i]>maxs[0]){
                maxs[0] = arr[i];
                insertSort(maxs);//改进后的插入排序
            }
        }
        return maxs;
    }
    //传过来的除了第一个数之外都有序
    private static void insertSort(int[] arr){
        for(int i = 0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }else
                break;
        }
    }

    /**
     * 方法3:分治的思想,分为100组,每组100万条,取每组的前10000条maxs,进行merge,最后返回的maxs就是最大的10000个数
     * 与方法1相比,1亿条数据排序效率低于100个100万数据的排序。 从结果来看,效率并没有提高,可能是快排还可以进一步优化。
     */
    public  static int[] top10000partition(int[]arr){
        return fun(arr,0,arr.length-1);
    }

    private static int[] fun(int[]arr,int left,int right){
        if (left + 1000000 <= right) {//100万返回前10000大的数组
            QuickSort2.quickSort2(arr,left,right);
            int l = right-left;
            int[] m = new int[l];
            for (int i = 0;i<l;i++){
                m[i] = arr[left+i];
            }
            return m;
        }else{
            int[] maxs1 = fun(arr,left,left+1000000);
            int[] maxs2 = fun(arr,left+1000001,right);
            return merge(maxs1, maxs2);
        }
    }
    //取两个数组的前10000个数据
    private static int[] merge(int[] arr1,int[] arr2){
        int i = 0,a1 = 0,a2 = 0;
        int[] mergemax = new int[10000];
        while(i<10000){
            if(arr1[a1]>arr2[a2]){
                mergemax[i++] = arr1[a1++];
            }
            else{
                mergemax[i++] = arr2[a2++];
            }
        }
        return mergemax;
    }


    /**
     * 最小堆法,思想和方法2相似。只不过使用二叉堆的结构存储maxs,效率更高一点。
     * 并且!!!!:这种方法的拓展性更好,如果源数据量变化,或者需要提取的数据变化,只需要修改很小的地方就可以;
     */
    public static int[] top10000minHeap(int[] arr){
       int[] maxs = new int[10000];
       //构建小根堆,为什么是小根堆,因为堆顶是最小的,插入的数如果比最小的还小,
        // 肯定不是最大的10000之一。如果是大根堆,小于和大于堆顶没有任何意义
        maxs = Arrays.copyOf(arr,10000);
       buildHeap(maxs);
       //遍历数组进行插堆下滤,小于堆顶直接跳过,大于堆顶则插入
        for(int i = 10000;i<arr.length;i++){
            if(arr[i]>maxs[0]){
                maxs[0] = arr[i];
                percDown(maxs,0);//重新构建小顶堆
            }
        }
        //层级遍历堆
       return maxs;
    }
    private static void buildHeap(int[] arr){
        int len = arr.length;
        for (int i = len/2;i>=0;i--){
            percDown(arr,i);
        }
    }
    //hole是需要下滤的元素的index而不是元素本身
    private static void percDown(int[]arr,int hole){
        int len = arr.length;
        int insert = arr[hole];
        int child;
        for (;hole*2+1<len;hole = child){
            child = hole*2+1;
            if(child != len-1&&arr[child+1]<arr[child]){
                child++;
            }
            if(arr[child]<insert){
                arr[hole] = arr[child];
            }else
                break;
        }
        arr[hole] = insert;
        //此时的hole就是之前的child,如果跳进过循环,则hole==child。
        // 如果没有跳进过循环,则表示hole*2+1 = child会越界
    }


    public static void main(String[] args) {
        int[] arr = ArrayUtils.arrGenerator(100000000, 10000000);
        long start = System.nanoTime();


        //int[] ints = top1000AllSort(arr);//14998ms
        //int[] ints = top1000First10000(arr);//stackOverFlow,内存不够用。因为多次快排进行了不必要的比较。
        //int[] ints = top1000First10000_2(arr);//526ms
        //int[] ints = top10000partition(arr);//16563ms,分治的效率并没提高。
        int[] ints = top10000minHeap(arr);//105ms 效率最高,输出的数据并不单调,因为二叉堆同一层的元素大小关系并不确定,如果需要单调。
        //可以使用带下标和层数的层级遍历。

        long end = System.nanoTime();
        System.out.println(Arrays.toString(ints));
        System.out.println(ArrayUtils.isMono(ints));
        System.out.println("cost"+(end-start)/1000000+"ms");
    }
}

实际运行: 实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。 下面针对不容的应用场景,分析了适合相应应用场景的解决方案。 (1)单机+单核+足够大内存 如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。 (2)单机+多核+足够大内存 这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。 该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。 (3)单机+单核+受限内存 这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。 (4)多机+受限内存 这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。因此上述方法中堆排序的方法最优

共有 人打赏支持
粉丝 0
博文 7
码字总数 26464
×
文川simple
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: