作者 Chunel Feng，編程愛好者，阿里巴巴搜索引擎開發(fā)工程師。

個人微信：ChunelFeng
個人博客：一面之猿網(wǎng)^[1]
開源項目：Caiss 智能相似搜索引擎^[2]

Doocs 社區(qū)的朋友們，大家好。我是你們的新朋友 Chunel Feng^[3]。今天想跟大家聊一些常見的 topK 問題。

對于海量數(shù)據(jù)的處理經(jīng)常會涉及到 topK 問題。在設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法的時候，主要需要考慮的應(yīng)該是當(dāng)前算法（包括數(shù)據(jù)結(jié)構(gòu)）跟給定情境（比如數(shù)據(jù)量級、數(shù)據(jù)類型）的適配程度，和當(dāng)前問題最核心的瓶頸（如降低時間復(fù)雜度，還是降低空間復(fù)雜度）是什么。

首先，我們來舉幾個常見的 topK 問題的例子：

1. 給定 100 個 int 數(shù)字，在其中找出最大的 10 個；2. 給定 10 億個 int 數(shù)字，在其中找出最大的 10 個（這 10 個數(shù)字可以無序）；3. 給定 10 億個 int 數(shù)字，在其中找出最大的 10 個（這 10 個數(shù)字依次排序）；4. 給定 10 億個不重復(fù)的 int 數(shù)字，在其中找出最大的 10 個；5. 給定 10 個數(shù)組，每個數(shù)組中有 1 億個 int 數(shù)字，在其中找出最大的 10 個；6. 給定 10 億個 string 類型的數(shù)字，在其中找出最大的 10 個（僅需要查 1 次）；7. 給定 10 億個 string 類型的數(shù)字，在其中找出最大的 k 個（需要反復(fù)多次查詢，其中 k 是一個隨機(jī)數(shù)字）。

上面這些問題看起來很相似，但是解決的方式卻千差萬別。稍有不慎，就可能使得 topK 問題成為系統(tǒng)的瓶頸。不過也不用太擔(dān)心，接下來我會總結(jié)幾種常見的解決思路，遇到問題的時候，大家把這些基礎(chǔ)思路融會貫通并且雜糅組合，即可做到見招拆招。

一、堆排序法

這里說的是堆排序法，而不是快排或者希爾排序。雖然理論上時間復(fù)雜度都是 O(nlogn)，但是堆排在做 topK 的時候有一個優(yōu)勢，就是可以維護(hù)一個僅包含 k 個數(shù)字的小頂堆（想清楚，為啥是小頂堆哦），當(dāng)新加入的數(shù)字大于堆頂數(shù)字的時候，將堆頂元素剔除，并加入新的數(shù)字。

用 C++來說明，堆在 stl 中是 priority_queue（不是 set）。

int main() {    const int topK = 3;    vector<int> vec = {4,1,5,8,7,2,3,0,6,9};    priority_queue<int, vector<int>, greater<>> pq;    // 小頂堆    for (const auto& x : vec) {        pq.push(x);        if (pq.size() > topK) {            // 如果超出個數(shù)，則彈出堆頂（最小的）數(shù)據(jù)            pq.pop();        }    }    while (!pq.empty()) {        cout << pq.top() << endl;    // 輸出依次為7,8,9        pq.pop();    }    return 0;}

Java 中同樣提供了 PriorityQueue 的數(shù)據(jù)結(jié)構(gòu)。

二、類似快排法

快排大家都知道，針對 topK 問題，可以對快排進(jìn)行改進(jìn)。僅對部分?jǐn)?shù)據(jù)進(jìn)行遞歸計算。比如，在 100 個數(shù)字中，找最大的 10 個，第一次循環(huán)的時候，povit 被移動到了 80 的位置，則接下來僅需要在后面的 20 個數(shù)字中找最大的 10 個即可。

這樣做的優(yōu)勢是，理論最優(yōu)時間復(fù)雜度可以達(dá)到 O(n)，不過平均時間復(fù)雜度還是 O(nlogn)。需要說明的是，通過這種方式，找出來的最大的 k 個數(shù)字之間，是無序的。

int partition(vector<int>& arr, int begin, int end) {    int left = begin;    int right = end;    int povit = arr[begin];    while (left < right) {        while (left < right && arr[right] >= povit) {right--;}        while (left < right && arr[left] <= povit) {left++;}        if (left < right) {swap(arr[left], arr[right]);}    }    swap(arr[begin], arr[left]);    return left;}void partSort(vector<int>& arr, int begin, int end, int target) {    if (begin >= end) {        return;    }    int povit = partition(arr, begin, end);    if (target < povit) {        partSort(arr, begin, povit - 1, target);    } else if (target > povit) {        partSort(arr, povit + 1, end, target);    }}vector<int> getMaxNumbers(vector<int>& arr, int k) {    int size = (int)arr.size();    // 把求最大的k個數(shù)，轉(zhuǎn)換成求最小的size-k個數(shù)字    int target = size - k;    partSort(arr, 0, size - 1, target);    vector<int> ret(arr.end() - k, arr.end());    return ret;}int main() {    vector<int> vec = {4,1,5,8,7,2,3,0,6,9};    auto ret = getMaxNumbers(vec, 3);    for (auto x : ret) {        cout << x << endl;    // 輸出7，8，9（理論上無序）    }    return 0;}

三、使用 bitmap

有時候 topK 問題會遇到數(shù)據(jù)量過大，內(nèi)存無法全部加載。這個時候，可以考慮將數(shù)據(jù)存放至 bitmap 中，方便查詢。

比如，給出 10 個 int 類型的數(shù)據(jù)，分別是【13，12，11，1，2，3，4，5，6，7】，int 類型的數(shù)據(jù)每個占據(jù) 4 個字節(jié)，那這個數(shù)組就占據(jù)了 40 個字節(jié)。現(xiàn)在，把它們放到一個 16 個長度 bool 的 bitmap 中，結(jié)果就是【0，1，1，1，1，1，1，1，0，0，0，1，1，1，0，0】，在將空間占用降低至 4 字節(jié)的同時，也可以很方便的看出，最大的 3 個數(shù)字，分別是 11，12 和 13。

需要說明的是，bitmap 結(jié)合跳表一起使用往往有奇效。比如以上數(shù)據(jù)還可以記錄成：從第 1 位開始，有連續(xù) 7 個 1；從第 11 位開始，有連續(xù) 3 個 1。這樣做，空間復(fù)雜度又得到了進(jìn)一步的降低。

這種做法的優(yōu)勢，當(dāng)然是降低了空間復(fù)雜度。不過需要注意一點(diǎn)，bitmap 比較適合不重復(fù)且有范圍（比如，數(shù)據(jù)均在 0 ～ 10 億之間）的數(shù)據(jù)的查詢。至于有重復(fù)數(shù)據(jù)的情況，可以考慮與 hash 等結(jié)構(gòu)的混用。

四、使用 hash

如果遇到了查詢 string 類型數(shù)據(jù)的大小，可以考慮 hash 方法。

舉個例子，10 個 string 數(shù)字【"1001"，"23"，"1002"，"3003"，"2001"，"1111"，"65"，"834"，"5"，"987"】找最大的 3 個。我們先通過長度進(jìn)行 hash，得到長度最大為 4，且有 5 個長度為 4 的 string。接下來再通過最高位值做 hash，發(fā)現(xiàn)有 1 個最高位為"3"的，1 個為"2"的，3 個為"1"的。接下來，可以通過再設(shè)計 hash 函數(shù)，或者是循環(huán)的方式，在 3 個最高位為"1"的 string 中找到最大的一個，即可找到 3 個最值大的數(shù)據(jù)。

這種方法比較適合網(wǎng)址或者電話號碼的查詢。缺點(diǎn)就是如果需要多次查詢的話，需要多次計算 hash，并且需要根據(jù)實際情況設(shè)計多個 hash 函數(shù)。

五、字典樹

字典樹（trie）的具體結(jié)構(gòu)和查詢方式，不在這里贅述了，自行百度一下就有很多。這里主要說一下優(yōu)缺點(diǎn)。

字典樹的思想，還是通過前期建立索引信息，后期可以反復(fù)多次查詢，并且后期增刪數(shù)據(jù)也很方便。比較適合于需要反復(fù)多次查詢的情況。

比如，反復(fù)多次查詢字符序（例如：z>y>...>b>a）最大的 k 個 url 這種，使用字典樹把數(shù)據(jù)存儲一遍，就非常適合。既減少了空間復(fù)雜度，也加速了查詢效率。

六、混合查詢

以上幾種方法，都是比較獨(dú)立的方法。其實，在實際工作中，遇到更多的問題還是混合問題，這就需要我們對相關(guān)的內(nèi)容，融會貫通并且做到活學(xué)活用。

我舉個例子：我們的分布式服務(wù)跑在 10 臺不同機(jī)器上，每臺機(jī)器上部署的服務(wù)均被請求 10000 次，并且記錄了個這 10000 次請求的耗時（耗時值為 int 數(shù)據(jù)），找出這 10*10000 次請求中，從高到低的找出耗時最大的 50 個?？纯催@個問題，很現(xiàn)實吧。我們試著用上面介紹的方法，組合一下來求解。

方法一

首先，對每臺機(jī)器上的 10000 個做類似快排，找出每臺機(jī)器上 top50 的耗時信息。此時，單機(jī)上的這 50 條數(shù)據(jù)是無序的。

然后，再將 10 臺機(jī)器上的 50 條數(shù)據(jù)（共 500 條）放到一起，再做一次類似快排，找到最大的 50 個（此時應(yīng)該這 50 個應(yīng)該是無序的）。

最后，對這 50 個數(shù)據(jù)做快排，從而得到最終結(jié)果。

方法二

首先通過堆排，分別找出 10 臺機(jī)器上耗時最高的 50 個數(shù)據(jù)，此時的這 50 個數(shù)據(jù)，已經(jīng)是從大到小有序的了。

然后，我們依次取出 10 臺機(jī)器中，耗時最高的 5 條放入小頂堆中。

最后，遍歷 10 臺機(jī)器上的數(shù)據(jù)，每臺機(jī)器從第 6 個數(shù)據(jù)開始往下循環(huán)，如果這個值比堆頂?shù)臄?shù)據(jù)大，則拋掉堆頂數(shù)據(jù)并且把它加入，繼續(xù)用下一個值進(jìn)行同樣比較。如果這個值比堆頂?shù)闹敌?，則結(jié)束當(dāng)前循環(huán)，并且在下一臺機(jī)器上做同樣操作。

以上我介紹了兩種方法，并不是為了說明哪種方法更好，或者時間復(fù)雜度更低。而是想說同樣的事情有多種不同的解決方法，而且隨著數(shù)據(jù)量的增加，可能會需要更多組合形式。在這個領(lǐng)域，數(shù)據(jù)決定了數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)決定了算法。

沒有最好的方法，只有不斷找尋更好的方法的程序員。適合的，才會是最好的。

嗯，加油，你可以找到更好的?。?！

引用鏈接

[1] 一面之猿網(wǎng): www.chunel.cn
[2] Caiss 智能相似搜索引擎: https://github.com/ChunelFeng/caiss
[3] Chunel Feng: https://github.com/ChunelFeng

長按識別下圖二維碼，關(guān)注公眾號「Doocs 開源社區(qū)」，第一時間跟你們分享好玩、實用的技術(shù)文章與業(yè)內(nèi)最新資訊。