大数据量获取TopK的方案是什么
大数据量获取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
三:局部淘汰法 -- 借助数据结构"堆"获取TopK
思路:
堆:分为大顶堆(堆顶元素大于其他所有元素)和小顶堆(堆顶其他元素小于所有其他元素)
我们使用小顶堆来实现,为什么不适用大顶堆下面会介绍~
取出K个元素放在另外的数组中,对这K个元素进行建堆
然后循环从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。
如果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个字符,而每个字符都是用0\1标识,我们初始化所有字符为0。
我们申请N/8+1容量的char数组,总共有N+8个字符。
对数据进行遍历,对每个元素S进行S/8操作获得char数组中的下标位置,S%8操作获得该char的第几个字符置1。
在遍历过程中,如果发现对应的字符位置上已经为1,则代表该值为重复值,可以去除。
主要还是根据内存、核数、最大创建线程数来动态判断如何获取前TopK。
看完上述内容,你们掌握大数据量获取TopK的方案是什么的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注行业资讯频道,感谢各位的阅读!