海量无序数据寻找第K大的数

本文转载自微信公众号「Kirito的技术分享」，作者kiritomoe。转载本文请联系Kirito的技术分享公众号。

创新互联建站2013年开创至今，先为江城等服务建站，江城等地企业，进行企业商务咨询服务。为江城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

简单抽象一下问题，便是今天的主题：在一个百万级无序的 long 数组中，寻找第 K 大的数。要求当然是越快找到越好。

top K 问题

题面一描述出来，很多人都会联想到 top K 问题，这道题无论是算法领域还是工程领域，都讨论的极其广泛，并且在实际项目中也很容易会遇到类似的问题，我也正好趁着这个机会总结成一篇文章。

常见的 top K 问题，及其变种：

  1. 有 10000000 个记录，这些查询串的重复度比较高，如果除去重复后，不超过 3000000 个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的 10 个查询串，要求使用的内存不能超过 1GB。
  2. 有 10 个文件，每个文件 1GB，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。按照 query 的频度排序。
  3. 有一个 1GB 大小的文件，里面的每一行是一个词，词的大小不超过 16 个字节，内存限制大小是 1MB。返回频数最高的 100 个词。
  4. 提取某日访问网站次数最多的那个 IP。
  5. 10 亿个整数找出重复次数最多的 100 个整数。
  6. 搜索的输入信息是一个字符串，统计 300 万条输入信息中最热门的前 10 条，每次输入的一个字符串为不超过 255B，内存使用只有 1GB。
  7. 有 1000 万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。

传统 top K 问题的描述：

在海量数据中找出最大的前 K 个数

注意我这次提出的问题和传统 top K 有一点区别，传统的 top K 问题要求的一般是”前 K 大的数“，而我现在遇到的是”第 K 大的数“。区别要说大也不大，但对于我们最终选择的方案可能会有很大的区别。

我下面会介绍一些传统的 top K 问题的解决思路。并且，按照我一贯的风格，肯定会有代码放出来，你如果是为了寻找一个”海量无序数据寻找第 K 大的数“问题的答案，相信你可以直接 copy 我的代码。

方案一：排序法

排序法是最容易想到的思路，复杂度为 O(nlogn) 。能够想到的各类排序算法呼之欲出，快速排序、归并排序、插入排序、猴子排序...etc

但是工程领域选择方案，往往不能仅仅使用算法复杂度来评估：

  • 每个排序方案数据的交换量
  • 额外空间的申请量
  • 平均复杂度
  • 最坏复杂度
  • 不同数据量下的表现

那这个时候有人就要问了，我该如何选择合适的方案呢?哎，那我又要提到那句话了，benchmark everything!虽然你肯定知道我最终没有选择使用排序来解决第 K 大的问题，但我还是想分享给你我的一些测试结论。

在 100w~1000w 数据量级别的无序 long 数组中，JDK 自带的 Array.sort() 比任何一个排序方案都要快。

Array.sort 的内部实现为 timsort，是一种优化过后的归并排序。

排序单纯靠想也知道不是最优的方案，因为我提出的问题中，仅仅需要找到第 K 大的数，排序方案却兴师动众把整个数组理顺了，没必要。

方案二：堆

针对一般的 top K 问题，一般都会默认 K 很小，所以一般的 top K 问题，可以选择使用堆来解决。

堆有个重要的性质：每个结点的值均不大于其左右孩子结点的值，则堆顶元素即为整个堆的最小值。JDK 中 PriorityQueue 实现了堆这个数据结构堆，通过指定 comparator 字段来表示小顶堆或大顶堆，默认为自然序(natural ordering)。

小顶堆解决 Top K 问题的思路：小顶堆维护当前扫描到的最大 K 个数，其后每一次扫描到的元素，若大于堆顶则入堆，然后删除堆顶;依此往复，直至扫描完所有元素。Java 实现第 K 大整数代码如下：

 
 
 
 
    
  
  
  
  
  1. public int findKthLargest(int[] nums, int k) { 
    2. 
  
  
  
  
  2.   PriorityQueue minQueue = new PriorityQueue<>(k); 
    3. 
  
  
  
  
  3.   for (int num : nums) { 
    4. 
  
  
  
  
  4.     if (minQueue.size() < k || num > minQueue.peek()) 
    5. 
  
  
  
  
  5.       minQueue.offer(num); 
    6. 
  
  
  
  
  6.     if (minQueue.size() > k) 
    7. 
  
  
  
  
  7.       minQueue.poll(); 
    8. 
  
  
  
  
  8.   } 
    9. 
  
  
  
  
  9.   return minQueue.peek(); 
    10. 
  
  
  
  
  10. } 
    11.

回到我遇到的问题，求第 K 大的数，这里没有说明 K 的范围，那么最坏情况下，K == N/2，无论维护一个 top K 的小顶堆还是维护一个 top(N - K) 的大顶堆，都需要占用 O(N/2) 的内存，而对于海量数据而言，这显示是一笔非常大的开销。所以针对我比赛的场景，堆的方案可以直接 pass。

堆的解法适用于 K 较小的场景，而且非常方便维护前 K 个数。

方案三：Quick Select

Quick Select 你可能没听过，但快速排序(Quick Sort)你肯定有所耳闻，其实他们两个算法的作者都是 Hoare，并且思想也非常接近：选取一个基准元素 pivot，将数组切分(partition)为两个子数组，比 pivot 大的扔左子数组，比 pivot 小的扔右子数组，然后递推地切分子数组。Quick Select 不同于 Quick Sort 之处在于其没有对每个子数组做切分，而是对目标子数组做切分。其次，Quick Select 与Quick Sort 一样，是一个不稳定的算法;pivot 选取直接影响了算法的好坏，最坏情况下的时间复杂度达到了 O(n2)。

在大学参加 ACM 时，我便第一次接触了该算法，记得那时数据量正好卡的 Quick Sort 无法通过，Quick Select 可以通过。

Quick Select 的 Java 实现如下：

 
 
 
 
    
  
  
  
  
  1. public static long quickSelect(long[] nums, int start, int end, int k) { 
    2. 
  
  
  
  
  2.         if (start == end) { 
    3. 
  
  
  
  
  3.             return nums[start]; 
    4. 
  
  
  
  
  4.         } 
    5. 
  
  
  
  
  5.         int left = start; 
    6. 
  
  
  
  
  6.         int right = end; 
    7. 
  
  
  
  
  7.         long pivot = nums[(start + end) / 2]; 
    8. 
  
  
  
  
  8.         while (left <= right) { 
    9. 
  
  
  
  
  9.             while (left <= right && nums[left] > pivot) { 
    10. 
  
  
  
  
  10.                 left++; 
    11. 
  
  
  
  
  11.             } 
    12. 
  
  
  
  
  12.             while (left <= right && nums[right] < pivot) { 
    13. 
  
  
  
  
  13.                 right--; 
    14. 
  
  
  
  
  14.             } 
    15. 
  
  
  
  
  15.             if (left <= right) { 
    16. 
  
  
  
  
  16.                 long temp = nums[left]; 
    17. 
  
  
  
  
  17.                 nums[left] = nums[right]; 
    18. 
  
  
  
  
  18.                 nums[right] = temp; 
    19. 
  
  
  
  
  19.                 left++; 
    20. 
  
  
  
  
  20.                 right--; 
    21. 
  
  
  
  
  21.             } 
    22. 
  
  
  
  
  22.         } 
    23. 
  
  
  
  
  23.         if (start + k - 1 <= right) { 
    24. 
  
  
  
  
  24.             return quickSelect(nums, start, right, k); 
    25. 
  
  
  
  
  25.         } 
    26. 
  
  
  
  
  26.         if (start + k - 1 >= left) { 
    27. 
  
  
  
  
  27.             return quickSelect(nums, left, end, k - (left - start)); 
    28. 
  
  
  
  
  28.         } 
    29. 
  
  
  
  
  29.         return nums[right + 1]; 
    30.

最终，我选择使用了方案三：Quick Select 作为我求解第 K 大数的方案，也是 benchmark 下来最快的方案。在 10 次查询中，排序方案耗时为 6s，而 Quick Select 方案，仅需要 300ms，可以说是非常大的优化。

总结

本文简单介绍了无序数组求 Top K 问题和无序数组求第 K 大数字两类非常相似的问题，并且提供了常见的三种解决方案。当然，该问题也有很多变种，例如在多核机器，多主机上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其实已经是在考虑其他层面的优化了，我在这里就不过多阐释了。

名称栏目：海量无序数据寻找第K大的数
文章起源：http://www.csdahua.cn/qtweb/news46/272196.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

App设计知识

分类信息网

软文推广　　 　成都手机网站报价　　 　成都外贸网站建设　　 　成都铁科精智测控　　 　网站建设策划方案　　 　东电技服　　 　app制作　　 　高端网站设计　　 　微信开发　　 　四川國際商會　　 　添翼二手车鉴定　　 　新华建筑装饰　　 　南充网站建设　　 　网站优化排名　　 　等级保护测评　　 　成都定制网站　　 　眉山做网站　　 　网站改版　　 　威斯达宇　　 　成都App定制