TopK问题:什么是TopK问题?用堆和快排这两种方…

2019-12-01 11:25:22来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

TopK问题:什么是TopK问题?用堆和快排这两种方式来实现TopK

  目录

一、什么是Top K问题

二、Top K的实际应用场景

三、Top K问题的代码实现及其效率对比

  1.用堆来实现Top K

  2.用快排来实现Top K

  3.用堆或用快排来实现 TopK 的效率对比

 

  正文

一、什么是Top K问题?

  给一个无序的数组,长度为N,  请输出最小 (或最大)的K个数。

 

二、Top K的实际应用场景

  排行榜:用户数量有几百万, 但是只需要前100名的用户成绩。 要显示出来, 且这个排行榜是实时变化的。

 

三、Top K问题的代码实现

  需求:给一个无序的数组,长度为N, 请输出最小的5个数。 

  1. 用堆来实现Top K——小顶堆

  (1)步骤梳理:

    ①创建一个结点个数为 k 的小顶堆;

    ②当数据量 < k 时,将数据直接放到这个小顶堆中,此时堆的顶结点是最小值;

    ③当数据量 >= k时,每产生一个新数据都与堆的顶结点进行比较: 

      如果新数据 > 顶结点数据,则将顶结点删除,将新数据放到堆中,此时堆会进行排序,且维护了堆的总结点数为k;

  (2)中心思想:使堆的总结点数维持在 k 个。

  (3)代码实现:

 1     @Test
 2     public void getTopKByHeapInsertTopKElement() {
 3         int arrayLength = 10000000 + 10;
 4         int topK = 5;
 5 
 6         // 准备一个长度为arrayLength的无序数组:
 7         int[] array = A03TopKByQuickSortAndNewArray.getDisorderlyArray(arrayLength);
 8 
 9         // 准备一个总结点数为topK的小顶堆:
10         PriorityQueue<Integer> heap = new PriorityQueue<>(topK);
11 
12         long start = System.currentTimeMillis();
13         
14         // 始终维持一个总结点个数为k的堆:
15         insertButmaintainTheHeapAtTopK(heap, array, topK);
16         
17         //获得最大topK:
18         printHeap(heap);
19         
20         long end = System.currentTimeMillis();
21         System.out.println("获得最大top5总耗时: " + (end - start));
22     }
23     
24     /**
25      * 用小顶堆来获取topK:当数据量超过topK后,新产生的数据直接和heap的顶结点进行比较。
26      */
27     private static void insertButmaintainTheHeapAtTopK(PriorityQueue<Integer> heap, int[] array, int topK) {
28         for (int i = 0; i < array.length; i++) {
29             if (i < topK) {
30                 heap.add(array[i]);
31             } else {// 怎么维持堆的总结点个数,下面的代码是关键:
32                 if (null != heap.peek() && array[i] > heap.peek()) {
33                     heap.poll();
34                     heap.add(array[i]);
35                 }
36             }
37         }
38     }
39     
40     /**
41      * 获取最大TopK
42      * @param heap
43      */
44     static void printHeap(PriorityQueue<Integer> heap) {
45         Iterator<Integer> iterator = heap.iterator();
46         while (iterator.hasNext()) {
47             System.out.println(iterator.next());
48         }
49     }

  

 

  2. 用快排来实现Top K

  (1)步骤梳理:

    ①通过快排,先将无序数组array进行排序;

    ②取出最小Top 5,并放到topArray中;【关键】

    ③超过arrayLength个数据后,又产生了insertNumber个新数据:直接和topArray数组比较,要放也是放到topArray中了;【关键】

  (2)时间复杂度:

    ①排序的时间复杂度:O(N*logN);

    ②取出top k的时间复杂度:O(1),就是遍历数组。

  (3)代码实现:

  1     @Test
  2     public void testGetTopKByQuickSortToNewArray() {
  3         int topK = 5;
  4         int arrayLength = 10000000;
  5         
  6         //准备一个无序数组
  7         int[] array = getDisorderlyArray(arrayLength);
  8         
  9         long start = System.currentTimeMillis();
 10         
 11         //1.通过快排,先将无序数组array进行排序
 12         quickSort(array, 0, array.length-1);
 13         
 14         //2.取出最小Top 5,并放到topArray中:
 15         int[] topKArray = insertToTopArrayFromDisorderlyArray(array, topK);
 16         
 17         //3.超过arrayLength个数据后,又产生了insertNumber个新数据:直接和topArray[topKArray.length-1]比较,要放也是放到topArray中了
 18         insertToTopKArray(topKArray, 10, 100, topKArray.length-1);//生成10个100以内的随机数作为新数据,和topKArray[topKArray.length-1]
 19         
 20         long end = System.currentTimeMillis();
 21         System.out.println("获得最大top5总耗时: " + (end - start));
 22     }
 23     
 24     /**
 25      * 产生新的数据后,再和topKArray数组进行比较,看新数据时候需要插入到topKArray中,若需要插入,则堆topKArray进行重新快排。
 26      * 
 27      * @param topKArray topK数组
 28      * @param insertNumber 新产生的数据的个数
 29      * @param randomIntRange 在什么范围内产生新数据,如生成10以内的随机数。
 30      * @param topK 在topKArray中,确定要替换的元素的下标。获得最小topK,则topK是从小到大排序的topKArray的最后一个元素。
 31      */
 32     private static void insertToTopKArray(int[] topKArray, int insertNumber, int randomIntRange, int topK) {
 33         Random random = new Random();
 34         int randomInt;
 35         for(int i = 0; i < insertNumber; i++) {
 36             randomInt = random.nextInt(100);
 37             if(randomInt < topKArray[topK]) {//新数据如果小于topArray[topK],则直接用该数去替换topArray,然后再将topArray进行重新排序。
 38                 topKArray[topK] = randomInt;
 39                 quickSort(topKArray, 0, topKArray.length-1);
 40             }
 41         }
 42     }
 43     
 44     /**
 45      * 从有序数组中取出需要的TopK,放到TopK数组中。
 46      * 
 47      * @param sourceArray 有序数组
 48      * @param topK 需要获取到Top K
 49      * @return TopK数组
 50      */
 51     private static int[] insertToTopArrayFromDisorderlyArray(int[] sourceArray, int topK) {
 52         int[] topArray = new int[topK];
 53         for(int i = 0; i < 5; i++) {
 54             topArray[i] = sourceArray[i];
 55         }
 56         return topArray;
 57     }
 58     
 59     /**
 60      * 快排
 61      * @param target
 62      * @param left
 63      * @param right
 64      */
 65     static void quickSort(int[] target, int left, int right) {
 66         if (left >= right) {
 67             return;
 68         }
 69         int pivot = target[left];// 基准点
 70         int temp;
 71         int i = left;
 72         int j = right;
 73         while (i < j) {
 74             while (target[j] >= pivot && i < j) {
 75                 j--;
 76             }
 77             while (target[i] <= pivot && i < j) {
 78                 i++;
 79             }
 80             if (i < j) {
 81                 temp = target[i];
 82                 target[i] = target[j];
 83                 target[j] = temp;
 84             }
 85         }
 86         // left和right相遇了:
 87         // ①将相遇点的元素和pivot做交换:
 88         target[left] = target[j];
 89         target[j] = pivot;
 90         // ②基准点两边的元素的分别再做排序:
 91         quickSort(target, left, j - 1);
 92         quickSort(target, j + 1, right);
 93     }
 94     
 95     /**
 96      * 准备一个无序数组
 97      * 
 98      * @param arrayLength
 99      * @return int[]
100      */
101     static int[] getDisorderlyArray(int arrayLength) {
102         int[] disorderlyArray = new int[arrayLength];
103         Random random = new Random();
104         for (int i = 0; i < arrayLength; i++) {
105             disorderlyArray[i] = random.nextInt(arrayLength);
106         }
107         return disorderlyArray;
108     }
109     
110     /**
111      * 遍历数组
112      */
113     static void showArray(int[] target) {
114         for (Integer element : target) {
115             System.out.println(element);
116         }
117     }

 

  3. 用堆来实现TopK 和 用快排来实现TopK 的效率对比:

                  “小顶堆”    |    “快排”

    数据量为100万+10时:    11毫秒    |    124毫秒

    数据量为1000万+10时:    28毫秒    |    1438毫秒

 


原文链接:https://www.cnblogs.com/laipimei/p/11715064.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:JVM系列一(Java内存区域和对象创建).

下一篇:写自定义参数验证方式