TopK

栏目: 编程工具 · 发布时间: 4年前

内容简介:在大规模数据处理中,经常会遇到TopK问题,也就是在海量数据中找到最大/小的k个数。这也是校招面试常问的算法题,TopK问题的应用场景很多,比如微博中找到搜索关键字中最热的10个词作为热搜、搜索引擎中找到一段时间中搜索次数最多的k个关键字,歌曲库中统计下载次数最多的k首歌曲等等。最容易想到的肯定是排序算法,然后取其排序的最大/小的k个数就完事了。其时间复杂度是既然只需要k个数,那么我们可以再优化一下,先用一个容器装这个数组的前k个数,然后找到这个容器中最小的那个数,再依次遍历后面的数,如果后面的数比这个最小

在大规模数据处理中,经常会遇到TopK问题,也就是在海量数据中找到最大/小的k个数。这也是校招面试常问的算法题,TopK问题的应用场景很多,比如微博中找到搜索关键字中最热的10个词作为热搜、搜索引擎中找到一段时间中搜索次数最多的k个关键字,歌曲库中统计下载次数最多的k首歌曲等等。

思路优化

排序

最容易想到的肯定是 排序 算法,然后取其排序的最大/小的k个数就完事了。其时间复杂度是 O(nlogn) ,但是问题来了,如果前提是以亿为单位的数据,你还敢用 排序算法 吗?明明只需要k个数,为啥要对所有数都排序呢?并且对这种海量数据,计算机内存不一定能扛得住。

局部淘汰法

既然只需要k个数,那么我们可以再优化一下,先用一个容器装这个数组的前k个数,然后找到这个容器中最小的那个数,再依次遍历后面的数,如果后面的数比这个最小的数要大,那么两者交换。一直到剩余的所有数都比这个容器中的数要小,那么这个容器中的数就是最大的k个数。

这种算法的时间复杂度为O(n*m),其中m为容器的长度。

具体地,其过程如下图所示:

TopK

那么这种方法的时间复杂度也太大,同样的思路,我们其实还可以利用最大/小堆来实现,这就引出了下一个实现方法。

我们可以先用前k个元素生成一个小顶堆,这个小顶堆用于存储当前k个元素,例子同上,可以构造小顶堆如下:

TopK

然后从第k+1个元素开始扫描,和堆顶元素比较(最小值),如果当前元素大于堆顶元素,则替换堆顶值,并调整堆,以保证堆内k个元素一直是当前最大的k个元素,如图所示:

TopK

直到,扫描完所有n-k个元素,最终堆中的k个元素,就是猥琐求的TopK:

TopK

这种堆解法的时间复杂度为 O(N*logk) ,并且堆解法也是求解TopK问题的经典解法,用代码实现如下:

public int findKthLargest(int[] nums, int k) {
    k = nums.length - k + 1;
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆
    for (int val : nums) {
        pq.add(val);
        if (pq.size() > k)  // 维护堆的大小为 K
            pq.poll();
    }
    return pq.peek();
}

那么还有没有更高效的解法呢?

快速排序

我们知道,快排的思想就是分治法,即分而治之,简而言之,就是把一个大问题分解为若干个子问题,然后把每个子问题都求解出来,最后整个大问题就解决了,其伪代码如下:

public void quick_sort(int[]arr, int low, inthigh){ 
     if(low== high) return; 
     int i = partition(arr, low, high); 
     quick_sort(arr, low, i-1); 
     quick_sort(arr, i+1, high); 
}

那么其中的核心就在于 partition(arr, low, high) 上,这个 partition 是什么意思呢?顾名思义,就是通过这个方法把数组分为两部分。更具体地,就是以数组arr中的一个元素(一般默认是第一个元素 t=arr[low] )作为划分依据,将数组 arr[low,high] 分为左右两个子数组:

  • 左半部分,都比t小
  • 右半部分,都比t大

如下图所示:

TopK

那么 partition 的返回结果就是t最终的位置i。

很容易知道, partition 的时间复杂度为O(n)。

那么快排跟Topk问题有什么关系呢?回到问题本身,TopK就是希望求出数组 arr[1,n] 中最大的k个数,那么如果找到了第 k 大的数,做一次 partition ,不就一次性找到最大的k个数了么?结果也就是 partition 的右半区间的数。

那么问题最终就变成了找数组中第k大的数,回过头来看看第一次 partition 划分之后:

int i = partition(arr,1,n);

那么这时候有两种情况:

  1. i > k ,那么说明 arr[i] 左边的元素都大于k,于是只需要随后递归 arr[1,i-1] 里面第k大的元素即可;
  2. i < k ,那么说明第k大的元素在右边,于是只需要递归 arr[i+1,n] 里第k-i大的元素即可。

上面这段非常重要,可以多读几遍。

使用代码实现上述算法可以如下:

public int findKthElement(int[] nums, int k) {
    k = nums.length - k;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int j = partition(nums, l, h);
        if (j == k) {
            break;
        } else if (j < k) {
            l = j + 1;
        } else {
            h = j - 1;
        }
    }
    return nums[k];
}

private int partition(int[] a, int l, int h) {
    int i = l, j = h + 1;
    while (true) {
        while (a[++i] < a[l] && i < h) ;
        while (a[--j] > a[l] && j > l) ;
        if (i >= j) {
            break;
        }
        swap(a, i, j);
    }
    swap(a, l, j);
    return j;
}

private void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

TopK的其它问题

海量数据

海量数据前提下,肯定不可能放在单机上。

  • 拆分,可以按照哈希取模或者其它方法拆分到多台机器上,并在每个机器上维护最小堆
  • 整合,将每台机器上得到的最小堆合并成最终的最小堆

频率统计

找出一个数据流中最频繁出现的k个数,比如热门搜索词汇等。

  • 使用HashMap进行频率统计,数据量不大时可用
  • Count-Min Sketch方法,具体可以 Google
  • Trie树解决,可以参考 这里

参考文章

  1. TopK
  2. 拜托,面试别再问我TopK了
  3. 海量数据处理–topK问题
  4. 海量数据处理问题(Top k问题)的实现

以上所述就是小编给大家介绍的《TopK》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

口碑

口碑

[美] David Meerman Scott / 高游、郭成钢、薛松 / 人民邮电出版社 / 2010-10 / 25.00

Web 2.0时代,怎样让你的产品或创意风靡一时,为百万大众喜闻乐道?本书将为你揭开其中的奥秘。作者将理论创新与实务操作相结合,总结出了利用Web 2.0营销手段制造网络狂欢效应的六条金科玉律,并介绍了一个个生动鲜活的成功范例,如:哈利?波特魔法公园如何策划一场小型活动,达到引爆网络热潮的效果;贝克?霍尔克拉夫特如何通过网络发布音乐作品,从默默无闻成长为全球炙手可热的明星;看似平淡无奇的电子书,如......一起来看看 《口碑》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具