大數(shù)據(jù)中 TopK 問題的常用套路
作者 Chunel Feng，編程愛好者，阿里巴巴搜索引擎開發(fā)工程師。
個(gè)人微信：ChunelFeng
個(gè)人博客：一面之猿網(wǎng)[1]
開源項(xiàng)目：Caiss 智能相似搜索引擎[2]
Doocs 社區(qū)的朋友們，大家好。我是你們的新朋友 Chunel Feng[3]。今天想跟大家聊一些常見的 topK 問題。
對(duì)于海量數(shù)據(jù)的處理經(jīng)常會(huì)涉及到 topK 問題。在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法的時(shí)候，主要需要考慮的應(yīng)該是當(dāng)前算法（包括數(shù)據(jù)結(jié)構(gòu)）跟給定情境（比如數(shù)據(jù)量級(jí)、數(shù)據(jù)類型）的適配程度，和當(dāng)前問題最核心的瓶頸（如降低時(shí)間復(fù)雜度，還是降低空間復(fù)雜度）是什么。
首先，我們來(lái)舉幾個(gè)常見的 topK 問題的例子：
1. 給定 100 個(gè) int 數(shù)字，在其中找出最大的 10 個(gè)；2. 給定 10 億個(gè) int 數(shù)字，在其中找出最大的 10 個(gè)（這 10 個(gè)數(shù)字可以無(wú)序）；3. 給定 10 億個(gè) int 數(shù)字，在其中找出最大的 10 個(gè)（這 10 個(gè)數(shù)字依次排序）；4. 給定 10 億個(gè)不重復(fù)的 int 數(shù)字，在其中找出最大的 10 個(gè)；5. 給定 10 個(gè)數(shù)組，每個(gè)數(shù)組中有 1 億個(gè) int 數(shù)字，在其中找出最大的 10 個(gè)；6. 給定 10 億個(gè) string 類型的數(shù)字，在其中找出最大的 10 個(gè)（僅需要查 1 次）；7. 給定 10 億個(gè) string 類型的數(shù)字，在其中找出最大的 k 個(gè)（需要反復(fù)多次查詢，其中 k 是一個(gè)隨機(jī)數(shù)字）。
上面這些問題看起來(lái)很相似，但是解決的方式卻千差萬(wàn)別。稍有不慎，就可能使得 topK 問題成為系統(tǒng)的瓶頸。不過也不用太擔(dān)心，接下來(lái)我會(huì)總結(jié)幾種常見的解決思路，遇到問題的時(shí)候，大家把這些基礎(chǔ)思路融會(huì)貫通并且雜糅組合，即可做到見招拆招。
一、堆排序法
這里說的是堆排序法，而不是快排或者希爾排序。雖然理論上時(shí)間復(fù)雜度都是 O(nlogn)，但是堆排在做 topK 的時(shí)候有一個(gè)優(yōu)勢(shì)，就是可以維護(hù)一個(gè)僅包含 k 個(gè)數(shù)字的小頂堆（想清楚，為啥是小頂堆哦），當(dāng)新加入的數(shù)字大于堆頂數(shù)字的時(shí)候，將堆頂元素剔除，并加入新的數(shù)字。
用 C++來(lái)說明，堆在 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) {// 如果超出個(gè)數(shù)，則彈出堆頂（最小的）數(shù)據(jù)pq.pop();}}while (!pq.empty()) {cout << pq.top() << endl; // 輸出依次為7,8,9pq.pop();}return 0;}
Java 中同樣提供了 PriorityQueue 的數(shù)據(jù)結(jié)構(gòu)。
二、類似快排法
快排大家都知道，針對(duì) topK 問題，可以對(duì)快排進(jìn)行改進(jìn)。僅對(duì)部分?jǐn)?shù)據(jù)進(jìn)行遞歸計(jì)算。比如，在 100 個(gè)數(shù)字中，找最大的 10 個(gè)，第一次循環(huán)的時(shí)候，povit 被移動(dòng)到了 80 的位置，則接下來(lái)僅需要在后面的 20 個(gè)數(shù)字中找最大的 10 個(gè)即可。
這樣做的優(yōu)勢(shì)是，理論最優(yōu)時(shí)間復(fù)雜度可以達(dá)到 O(n)，不過平均時(shí)間復(fù)雜度還是 O(nlogn)。需要說明的是，通過這種方式，找出來(lái)的最大的 k 個(gè)數(shù)字之間，是無(wú)序的。
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個(gè)數(shù)，轉(zhuǎn)換成求最小的size-k個(gè)數(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（理論上無(wú)序）}return 0;}
三、使用 bitmap
有時(shí)候 topK 問題會(huì)遇到數(shù)據(jù)量過大，內(nèi)存無(wú)法全部加載。這個(gè)時(shí)候，可以考慮將數(shù)據(jù)存放至 bitmap 中，方便查詢。
比如，給出 10 個(gè) int 類型的數(shù)據(jù)，分別是【13，12，11，1，2，3，4，5，6，7】，int 類型的數(shù)據(jù)每個(gè)占據(jù) 4 個(gè)字節(jié)，那這個(gè)數(shù)組就占據(jù)了 40 個(gè)字節(jié)?，F(xiàn)在，把它們放到一個(gè) 16 個(gè)長(zhǎng)度 bool 的 bitmap 中，結(jié)果就是【0，1，1，1，1，1，1，1，0，0，0，1，1，1，0，0】，在將空間占用降低至 4 字節(jié)的同時(shí)，也可以很方便的看出，最大的 3 個(gè)數(shù)字，分別是 11，12 和 13。
需要說明的是，bitmap 結(jié)合跳表一起使用往往有奇效。比如以上數(shù)據(jù)還可以記錄成：從第 1 位開始，有連續(xù) 7 個(gè) 1；從第 11 位開始，有連續(xù) 3 個(gè) 1。這樣做，空間復(fù)雜度又得到了進(jìn)一步的降低。
這種做法的優(yōu)勢(shì)，當(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 方法。
舉個(gè)例子，10 個(gè) string 數(shù)字【"1001"，"23"，"1002"，"3003"，"2001"，"1111"，"65"，"834"，"5"，"987"】找最大的 3 個(gè)。我們先通過長(zhǎng)度進(jìn)行 hash，得到長(zhǎng)度最大為 4，且有 5 個(gè)長(zhǎng)度為 4 的 string。接下來(lái)再通過最高位值做 hash，發(fā)現(xiàn)有 1 個(gè)最高位為"3"的，1 個(gè)為"2"的，3 個(gè)為"1"的。接下來(lái)，可以通過再設(shè)計(jì) hash 函數(shù)，或者是循環(huán)的方式，在 3 個(gè)最高位為"1"的 string 中找到最大的一個(gè)，即可找到 3 個(gè)最值大的數(shù)據(jù)。
這種方法比較適合網(wǎng)址或者電話號(hào)碼的查詢。缺點(diǎn)就是如果需要多次查詢的話，需要多次計(jì)算 hash，并且需要根據(jù)實(shí)際情況設(shè)計(jì)多個(gè) hash 函數(shù)。
五、字典樹
字典樹（trie）的具體結(jié)構(gòu)和查詢方式，不在這里贅述了，自行百度一下就有很多。這里主要說一下優(yōu)缺點(diǎn)。
字典樹的思想，還是通過前期建立索引信息，后期可以反復(fù)多次查詢，并且后期增刪數(shù)據(jù)也很方便。比較適合于需要反復(fù)多次查詢的情況。
比如，反復(fù)多次查詢字符序（例如：z>y>...>b>a）最大的 k 個(gè) url 這種，使用字典樹把數(shù)據(jù)存儲(chǔ)一遍，就非常適合。既減少了空間復(fù)雜度，也加速了查詢效率。
六、混合查詢
以上幾種方法，都是比較獨(dú)立的方法。其實(shí)，在實(shí)際工作中，遇到更多的問題還是混合問題，這就需要我們對(duì)相關(guān)的內(nèi)容，融會(huì)貫通并且做到活學(xué)活用。
我舉個(gè)例子：我們的分布式服務(wù)跑在 10 臺(tái)不同機(jī)器上，每臺(tái)機(jī)器上部署的服務(wù)均被請(qǐng)求 10000 次，并且記錄了個(gè)這 10000 次請(qǐng)求的耗時(shí)（耗時(shí)值為 int 數(shù)據(jù)），找出這 10*10000 次請(qǐng)求中，從高到低的找出耗時(shí)最大的 50 個(gè)。看看這個(gè)問題，很現(xiàn)實(shí)吧。我們?cè)囍蒙厦娼榻B的方法，組合一下來(lái)求解。
方法一
首先，對(duì)每臺(tái)機(jī)器上的 10000 個(gè)做類似快排，找出每臺(tái)機(jī)器上 top50 的耗時(shí)信息。此時(shí)，單機(jī)上的這 50 條數(shù)據(jù)是無(wú)序的。
然后，再將 10 臺(tái)機(jī)器上的 50 條數(shù)據(jù)（共 500 條）放到一起，再做一次類似快排，找到最大的 50 個(gè)（此時(shí)應(yīng)該這 50 個(gè)應(yīng)該是無(wú)序的）。
最后，對(duì)這 50 個(gè)數(shù)據(jù)做快排，從而得到最終結(jié)果。
方法二
首先通過堆排，分別找出 10 臺(tái)機(jī)器上耗時(shí)最高的 50 個(gè)數(shù)據(jù)，此時(shí)的這 50 個(gè)數(shù)據(jù)，已經(jīng)是從大到小有序的了。
然后，我們依次取出 10 臺(tái)機(jī)器中，耗時(shí)最高的 5 條放入小頂堆中。
最后，遍歷 10 臺(tái)機(jī)器上的數(shù)據(jù)，每臺(tái)機(jī)器從第 6 個(gè)數(shù)據(jù)開始往下循環(huán)，如果這個(gè)值比堆頂?shù)臄?shù)據(jù)大，則拋掉堆頂數(shù)據(jù)并且把它加入，繼續(xù)用下一個(gè)值進(jìn)行同樣比較。如果這個(gè)值比堆頂?shù)闹敌?，則結(jié)束當(dāng)前循環(huán)，并且在下一臺(tái)機(jī)器上做同樣操作。
以上我介紹了兩種方法，并不是為了說明哪種方法更好，或者時(shí)間復(fù)雜度更低。而是想說同樣的事情有多種不同的解決方法，而且隨著數(shù)據(jù)量的增加，可能會(huì)需要更多組合形式。在這個(gè)領(lǐng)域，數(shù)據(jù)決定了數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)決定了算法。
沒有最好的方法，只有不斷找尋更好的方法的程序員。適合的，才會(huì)是最好的。
嗯，加油，你可以找到更好的?。?！
引用鏈接
[1] 一面之猿網(wǎng): www.chunel.cn[2] Caiss 智能相似搜索引擎: https://github.com/ChunelFeng/caiss[3] Chunel Feng: https://github.com/ChunelFeng
長(zhǎng)按識(shí)別下圖二維碼，關(guān)注公眾號(hào)「Doocs 開源社區(qū)」，第一時(shí)間跟你們分享好玩、實(shí)用的技術(shù)文章與業(yè)內(nèi)最新資訊。