DIV CSS 佈局教程網

用堆(Heap)實作 Top K 問題:從 Hash 統計到小根堆的完整 JS 解法
編輯:關於JavaScript     

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 為出現次數的雜湊表:

  • 讀入一個查詢,若不在表中,加入並把計數設為 1。
  • 若已在表中,計數加一。

如此在 O(N) 時間內完成統計,而且只需讀取檔案一次。相比做法一,時間複雜度降低一個量級,IO 次數也大幅減少,工程上更實用。

第二步:找出 Top 10

算法一:完整排序

把三百萬筆依計數排序後取前十。時間複雜度 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' 為三百萬。

JavaScript 的堆實作

以下示範以陣列表示堆的三個函式:取得堆頂、建立堆、以及重複取出前 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 的堆做線上篩選,避免全量排序。若資料量更大到記憶體放不下,第一步可換成外部分片雜湊(先依雜湊值切檔,各檔獨立統計再合併),這是分散式處理的起點。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved