大数据量获取TopK的几种方案

一：介绍

生活中经常会遇到求TopK的问题，在小数据量的情况下可以先将所有数据排序，最后进行遍历。但是在大数据量情况下，这种的时间复杂度最低的也就是O(NlogN)此处的N可能为10亿这么大的数字，时间复杂度过高，那么什么方法可以减少时间复杂度呢，以下几种方式，与大家分享。

二：局部淘汰法 -- 借助“冒泡排序”获取TopK

思路：

可以避免对所有数据进行排序，只排序部分

冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK

时间复杂度空间复杂度

时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)

空间复杂度：O(K)，用来存放获得的topK，也可以O(1)遍历原数组的最后K个元素即可。ps:冒泡排序请参考： https://blog.csdn.net/CSDN___LYY/article/details/81478583

代码比较简单就不贴了，只要会写冒泡就ok了

三：局部淘汰法 -- 借助数据结构"堆"获取TopK

思路：

堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）

我们使用小顶堆来实现，为什么不适用大顶堆下面会介绍~

取出K个元素放在另外的数组中，对这K个元素进行建堆 ps:堆排序请参考：https://blog.csdn.net/CSDN___LYY/article/details/81454613

然后循环从K下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后重新调整为小顶堆

循环完毕后，K个元素的堆数组就是我们所需要的TopK

为什么使用小顶堆呢？

我们在比较的过程中使用堆顶是最小值的小顶堆，元素大于堆顶我们对堆顶进行重新赋值，那么堆顶永远是这K个值中最小的值，当我们下一个元素和堆顶比较时，如果不大于堆顶的话，那么一定不属于topK范围的

时间复杂度与空间复杂度

时间复杂度：每次对K个元素进行建堆，时间复杂度为：O(KlogK)，加上N-K次的循环，则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)，其中K为想要获取的TopK的数量N为总数据量

空间复杂度：O(K)，只需要新建一个K大小的数组用来存储topK即可

适用环境

适用于单核单机环境，不会发挥多核的优势

也可用于分治法中获取每一份元素的Top，下面会介绍

代码实现

使用的java代码实现的，代码内每一步都有注释便于理解

import java.util.Arrays;

/**
* 通过堆这种数据结构
* 获得大数据量中的TopK
*/

public class TopKStack {
public static void main(String[] args) {
//定义一个数组，找出该数组中的topK，大数据量不好搞到，先用这个数组测试
int [] datas = {2,3,42,1,34,5,6,67,3,243,8,246,123,6,32,3451,23,5,6,31,5,6,2346,36};
int [] re = getTopK(datas,10);
System.out.println(Arrays.toString(re));
}

/**
* 获取前topk的方法
* @param datas 原数组
* @param num 前topNum
* @return 最后的topNum的堆数组
*/
static int[] getTopK(int[] datas,int num){
//定义存储前num个元素的数组，用于建堆
int[] res = new int[num];
//初始化数组
for (int i = 0; i < num; i++) {
res[i] = datas[i];
}
//建造初始化堆
for (int i = (num - 1)/2; i >= 0 ; i--) {
shift(res,i);
}
//遍历查找num个最大值
for (int i = num; i < datas.length; i++) {
if (datas[i] > res[0]){
res[0] = datas[i];
shift(res,0);
}
}
return res;
}

/**
* 调整元素满足堆结构
* @param datas
* @param index
* @return
*/
static int[] shift(int[] datas ,int index){
while(true){
int left = (index<<1) + 1; //左孩子
int right = (index<<1) + 2; //右孩子

int min_num = index; //标识自身节点和孩子节点中最小值的位置
//判断是否存在左右孩子，并且得到左右孩子和自身的最小值
if (left <= datas.length-1&&datas[left] < datas[index]){
min_num = left;
}
if (right <= datas.length-1&&datas[right] < datas[min_num]){
min_num = right;
}
//如果最小值不等于自身，则将最小值与自身交换
if (min_num != index){
int temp = datas[index];
datas[index] = datas[min_num];
datas[min_num] = temp;
}else{
//此处break是因为我们是从树的最下面进行调整的，如果上层节点符合堆，则下层节点一定符合！
break;
}

//执行到此处，说明可能需要调整下面的节点，则将初始节点赋值为最小值所在的节点位置，
// 因为最大值点的位置进行了交换，可能下层节点就不满足堆性质
index = min_num;
}
return datas;
}
}
四：分治法 -- 借助”快速排序“方法获取TopK

思路：

比如有10亿的数据，找处Top1000，我们先将10亿的数据分成1000份，每份100万条数据

在每一份中找出对应的Top 1000，整合到一个数组中，得到100万条数据，这样过滤掉了999%%的数据

使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。 ps:快速排序请参考：https://blog.csdn.net/CSDN___LYY/article/details/81478583

如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Si和Sj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序

如此递归下去即可获得TopK

和第一种方法有什么不同呢？相对来说的优点是什么？

第二种方法中我们可以采用多核的优势，创建多个线程，分别去操作不同的数据。

当然我们在分治的第二步可以使用第一种方法去获取每一份的Top。

适用环境

多核多机的情况，分治法会将多核的作用发挥到最大，节省大量时间

时间复杂度与空间复杂度

时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但是分治法我们会使用多核多机的资源，比如我们有S个线程同时处理。则时间复杂度为：O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)。所以，总时间复杂度大约为O(MN+(N/S)logK) 。

空间复杂度：需要每一份一个数组，则空间复杂度为O(N)

五：其他情况

通常我们要根据数据的情况去判断我们使用什么方法，在获取TopK前我们可以做什么操作减少数据量。

比如：数据集中有许多重复的数据并且我们需要的是前TopK个不同的数，我们可以先进行去重之后再获取前TopK。如何进行大数据量的去重操作呢，简单的说一下：

采用bitmap来进行去重。

一个char类型的数据为一个字节也就是8个字符，而每个字符都是用01标识，我们初始化所有字符为0。

我们申请N/8+1容量的char数组，总共有N+8个字符。

对数据进行遍历，对每个元素S进行S/8操作获得char数组中的下标位置，S%8操作获得该char的第几个字符置1。

在遍历过程中，如果发现对应的字符位置上已经为1,则代表该值为重复值，可以去除。

主要还是根据内存、核数、最大创建线程数来动态判断如何获取前TopK。

原文链接：https://liyangyang.blog.csdn.net/article/details/82909081

大数据量获取TopK的几种方案

相关推荐