大數(shù)據(jù)量獲取TopK的方案是什么

一：介紹

    生活中經(jīng)常會遇到求TopK的問題，在小數(shù)據(jù)量的情況下可以先將所有數(shù)據(jù)排序，最后進(jìn)行遍歷。但是在大數(shù)據(jù)量情況下，這種的時(shí)間復(fù)雜度最低的也就是O(NlogN)此處的N可能為10億這么大的數(shù)字，時(shí)間復(fù)雜度過高，那么什么方法可以減少時(shí)間復(fù)雜度呢，以下幾種方式，與大家分享。

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

1. 思路：

• 可以避免對所有數(shù)據(jù)進(jìn)行排序，只排序部分

• 冒泡排序是每一輪排序都會獲得一個(gè)最大值，則K輪排序即可獲得TopK

2. 時(shí)間復(fù)雜度空間復(fù)雜度

• 時(shí)間復(fù)雜度：排序一輪是O(N)，則K次排序總時(shí)間復(fù)雜度為：O(KN)

• 空間復(fù)雜度：O(K)，用來存放獲得的topK，也可以O(shè)(1)遍歷原數(shù)組的最后K個(gè)元素即可。ps:冒泡排序請參考：https://blog.csdn.net/CSDN___LYY/article/details/81478583

三：局部淘汰法 -- 借助數(shù)據(jù)結(jié)構(gòu)"堆"獲取TopK

1. 思路：

• 堆：分為大頂堆（堆頂元素大于其他所有元素）和小頂堆（堆頂其他元素小于所有其他元素）

• 我們使用小頂堆來實(shí)現(xiàn)，為什么不適用大頂堆下面會介紹~

• 取出K個(gè)元素放在另外的數(shù)組中，對這K個(gè)元素進(jìn)行建堆

• 然后循環(huán)從K下標(biāo)位置遍歷數(shù)據(jù)，只要元素大于堆頂，我們就將堆頂賦值為該元素，然后重新調(diào)整為小頂堆

• 循環(huán)完畢后，K個(gè)元素的堆數(shù)組就是我們所需要的TopK

2. 為什么使用小頂堆呢？

• 我們在比較的過程中使用堆頂是最小值的小頂堆，元素大于堆頂我們對堆頂進(jìn)行重新賦值，那么堆頂永遠(yuǎn)是這K個(gè)值中最小的值，當(dāng)我們下一個(gè)元素和堆頂比較時(shí)，如果不大于堆頂?shù)脑?，那么一定不屬于topK范圍的

3. 時(shí)間復(fù)雜度與空間復(fù)雜度

• 時(shí)間復(fù)雜度：每次對K個(gè)元素進(jìn)行建堆，時(shí)間復(fù)雜度為：O(KlogK)，加上N-K次的循環(huán)，則總時(shí)間復(fù)雜度為O((K+(N-K))logK)，即O(NlogK)，其中K為想要獲取的TopK的數(shù)量N為總數(shù)據(jù)量

• 空間復(fù)雜度：O(K)，只需要新建一個(gè)K大小的數(shù)組用來存儲topK即可

4. 適用環(huán)境

• 適用于單核單機(jī)環(huán)境，不會發(fā)揮多核的優(yōu)勢

• 也可用于分治法中獲取每一份元素的Top，下面會介紹

5. 代碼實(shí)現(xiàn)

• 使用的java代碼實(shí)現(xiàn)的，代碼內(nèi)每一步都有注釋便于理解

import java.util.Arrays;/*** 通過堆這種數(shù)據(jù)結(jié)構(gòu)* 獲得大數(shù)據(jù)量中的TopK*/public class TopKStack {    public static void main(String[] args) {        //定義一個(gè)數(shù)組，找出該數(shù)組中的topK，大數(shù)據(jù)量不好搞到，先用這個(gè)數(shù)組測試        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 原數(shù)組    * @param num 前topNum    * @return 最后的topNum的堆數(shù)組    */    static int[] getTopK(int[] datas,int num){        //定義存儲前num個(gè)元素的數(shù)組，用于建堆        int[] res = new int[num];        //初始化數(shù)組        for (int i = 0; i < num; i++) {            res[i] = datas[i];        }        //建造初始化堆        for (int i = (num - 1)/2; i >= 0 ; i--) {            shift(res,i);        }        //遍歷查找num個(gè)最大值        for (int i = num; i < datas.length; i++) {            if (datas[i] > res[0]){                res[0] = datas[i];                shift(res,0);            }        }        return res;    }    /**    * 調(diào)整元素滿足堆結(jié)構(gòu)    * @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; //標(biāo)識自身節(jié)點(diǎn)和孩子節(jié)點(diǎn)中最小值的位置            //判斷是否存在左右孩子，并且得到左右孩子和自身的最小值            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是因?yàn)槲覀兪菑臉涞淖钕旅孢M(jìn)行調(diào)整的，如果上層節(jié)點(diǎn)符合堆，則下層節(jié)點(diǎn)一定符合！            break;        }        //執(zhí)行到此處，說明可能需要調(diào)整下面的節(jié)點(diǎn)，則將初始節(jié)點(diǎn)賦值為最小值所在的節(jié)點(diǎn)位置，        // 因?yàn)樽畲笾迭c(diǎn)的位置進(jìn)行了交換，可能下層節(jié)點(diǎn)就不滿足堆性質(zhì)        index = min_num;    }    return datas;   }}

四：分治法 -- 借助”快速排序“方法獲取TopK

1. 思路：

• 比如有10億的數(shù)據(jù)，找處Top1000，我們先將10億的數(shù)據(jù)分成1000份，每份100萬條數(shù)據(jù)

• 在每一份中找出對應(yīng)的Top 1000，整合到一個(gè)數(shù)組中，得到100萬條數(shù)據(jù)，這樣過濾掉了999%%的數(shù)據(jù)

• 使用快速排序?qū)@100萬條數(shù)據(jù)進(jìn)行”一輪“排序，一輪排序之后指針的位置指向的數(shù)字假設(shè)為S，會將數(shù)組分為兩部分，一部分大于S記作Si，一部分小于S記作Sj。

• 如果Si元素個(gè)數(shù)大于1000，我們對Si數(shù)組再進(jìn)行一輪排序，再次將Si分成了Si和Sj。如果Si的元素小于1000，則我們需要在Sj中獲取1000-count(Si)個(gè)元素的，也就是對Sj進(jìn)行排序

• 如此遞歸下去即可獲得TopK

2. 和第一種方法有什么不同呢？相對來說的優(yōu)點(diǎn)是什么？

• 第二種方法中我們可以采用多核的優(yōu)勢，創(chuàng)建多個(gè)線程，分別去操作不同的數(shù)據(jù)。

• 當(dāng)然我們在分治的第二步可以使用第一種方法去獲取每一份的Top。

3. 適用環(huán)境

• 多核多機(jī)的情況，分治法會將多核的作用發(fā)揮到最大，節(jié)省大量時(shí)間

4. 時(shí)間復(fù)雜度與空間復(fù)雜度

• 時(shí)間復(fù)雜度：一份獲取前TopK的時(shí)間復(fù)雜度：O((N/n)logK)。則所有份數(shù)為：O(NlogK)，但是分治法我們會使用多核多機(jī)的資源，比如我們有S個(gè)線程同時(shí)處理。則時(shí)間復(fù)雜度為：O((N/S)logK)。之后進(jìn)行快排序，一次的時(shí)間復(fù)雜度為：O(N),假設(shè)排序了M次之后得到結(jié)果，則時(shí)間復(fù)雜度為：O(MN)。所以 ，總時(shí)間復(fù)雜度大約為O(MN+(N/S)logK) 。

• 空間復(fù)雜度：需要每一份一個(gè)數(shù)組，則空間復(fù)雜度為O(N)

五：其他情況

• 通常我們要根據(jù)數(shù)據(jù)的情況去判斷我們使用什么方法，在獲取TopK前我們可以做什么操作減少數(shù)據(jù)量。

• 比如：數(shù)據(jù)集中有許多重復(fù)的數(shù)據(jù)并且我們需要的是前TopK個(gè)不同的數(shù)，我們可以先進(jìn)行去重之后再獲取前TopK。如何進(jìn)行大數(shù)據(jù)量的去重操作呢，簡單的說一下：

1. 采用bitmap來進(jìn)行去重。

2. 一個(gè)char類型的數(shù)據(jù)為一個(gè)字節(jié)也就是8個(gè)字符，而每個(gè)字符都是用0\1標(biāo)識，我們初始化所有字符為0。

3. 我們申請N/8+1容量的char數(shù)組，總共有N+8個(gè)字符。

4. 對數(shù)據(jù)進(jìn)行遍歷，對每個(gè)元素S進(jìn)行S/8操作獲得char數(shù)組中的下標(biāo)位置，S%8操作獲得該char的第幾個(gè)字符置1。

5. 在遍歷過程中，如果發(fā)現(xiàn)對應(yīng)的字符位置上已經(jīng)為1,則代表該值為重復(fù)值，可以去除。

• 主要還是根據(jù)內(nèi)存、核數(shù)、最大創(chuàng)建線程數(shù)來動態(tài)判斷如何獲取前TopK。