Top K 是資料處理與面試中的高頻題型:在龐大的資料集合中找出出現頻率最高的前 K 項。本文從經典情境出發,逐步優化,最後給出 JavaScript 的堆實作。
搜尋引擎會把使用者每次的查詢字串寫進日誌,每條長度 1 到 255 位元組。假設現有一千萬筆記錄,去重後不超過三百萬筆。重複度越高代表越熱門。請統計出最熱門的 10 個查詢串,且記憶體使用不得超過 1G。
雜湊表(Hash table,又稱散列表)是根據鍵值直接進行存取的一種資料結構。它透過一個雜湊函式把 key 映射成整數,再對陣列長度取餘作為索引,把 value 存在該位置。
查詢時重複同一套計算即可定位到索引,因此平均查找時間接近 O(1)。這種「以位置換搜尋」的特性,讓它成為統計字串出現次數的首選工具。
最直覺的算法是先把全部查詢排序,再順著掃一遍統計相鄰相同項。在伺服器上常見的指令寫法就是這個思路:
cat file | format key | sort | uniq -c | sort -nr | head -n 10
但題目限制記憶體 1G,而一千萬筆 × 255 Byte 約需 2.375G,直接放進記憶體不可行。此時可以採用外部排序,例如歸併排序,時間複雜度 O(N log N),排序後再遍歷統計寫回檔案。整體複雜度仍是 O(N log N),而且需要多次 IO。
題目已說明去重後只有三百萬筆,這個量級放進記憶體是可行的。於是維護一個 key 為查詢字串、value 為出現次數的雜湊表:
如此在 O(N) 時間內完成統計,而且只需讀取檔案一次。相比做法一,時間複雜度降低一個量級,IO 次數也大幅減少,工程上更實用。
把三百萬筆依計數排序後取前十。時間複雜度 O(N log N),在 1G 記憶體下可行,但對「只要前 10 名」的需求來說,其餘的排序都是多餘的。
既然只要 10 個,那就維護一個大小為 10 的陣列,先放入前 10 筆並由大到小排序。之後遍歷其餘資料,每筆都與陣列中最後(最小)的元素比較:若比它小就跳過;否則淘汰最後一項,把新元素插入合適位置維持有序。全部掃完後,陣列中的 10 項就是答案。
最壞時間複雜度為 O(N × K),K 為要取的名次數。
算法二每次插入都要線性搬移,成本是 O(K)。若改用二分搜尋定位,比較成本降到 O(log K),但陣列的元素搬移次數反而增加。
有沒有一種結構同時支援快速查找與快速調整?有的,就是堆。維護一個大小為 K 的小根堆,遍歷所有查詢並與堆頂(最小值)比較:比堆頂大就替換掉堆頂再重新調整。查找與調整都是 O(log K),整體複雜度降為 O(N log K)。
兩步驟合起來,最終複雜度是 O(N) + N' × O(log K),其中 N 為一千萬,N' 為三百萬。
以下示範以陣列表示堆的三個函式:取得堆頂、建立堆、以及重複取出前 K 名。
// 取出堆頂元素,時間複雜度 O(log N)
function top(arr, comp) {
if (arr.length === 0) return;
var i = arr.length / 2 | 0;
for (; i >= 0; i--) {
if (comp(arr[i], arr[i * 2])) exch(arr, i, i * 2);
if (comp(arr[i], arr[i * 2 + 1])) exch(arr, i, i * 2 + 1);
}
return arr[0];
}
function exch(arr, i, j) {
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// 調用 K 次取得前 K 名,時間複雜度 O(K * log N)
function topK(arr, n, comp) {
if (!arr || arr.length === 0 || n <= 0 || n > arr.length) return -1;
var ret = [];
for (var i = 0; i < n; i++) {
var max = top(arr, comp);
ret.push(max);
arr.splice(0, 1);
}
return ret;
}
var ret = topK([16, 22, 91, 0, 51, 44, 23], 3, function (a, b) {
return a < b;
});
console.log(ret);
Top K 這類問題的通用套路是兩段式:先用雜湊表把「值 → 頻次」的統計做掉,把資料規模壓下來;再用容量為 K 的堆做線上篩選,避免全量排序。若資料量更大到記憶體放不下,第一步可換成外部分片雜湊(先依雜湊值切檔,各檔獨立統計再合併),這是分散式處理的起點。