Anthony Kan與 AI 一起實作
所有實作筆記

進入迴圈前,先建好一次索引

每行都重掃整份列表,資料多了,工作便急速增加。

做下去,遇上新難題閱讀時間約 2 分鐘

第二次掃描,藏在輔助函式裏

目錄解析程式逐行處理資料時,迴圈裏面呼叫了一個輔助函式(helper),每次都從頭掃描整份列表,計算某個僱主網址出現了多少次。這個輔助函式本身看來很小,卻令整份列表的掃描工作在每一行都重做一遍。

用 N 行作例子,完整掃描 N 次,便大約是 N × N 次比較,稱為 O(N²)。十行約一百次,五百行約二十五萬次。這是解釋增長方式的算例,不是實測指令數、時間,也不是說五百行一定會超出伺服器限制。

共用同一份索引

My Next Step 的目錄程式,會先掃描一次建立共用網址的計數,之後逐行解析時直接重用。做法是用 Map 記下正規化(normalised)後的網址與出現次數。在一般高效的查表下,統計與處理只需各自走過列表一遍,而不必每行重掃全部資料。

兩次使用的索引鍵值(key)必須採用同一套正規化規則。如果一邊去掉了網址末尾的斜線、另一邊沒有,改快之後反而會判斷出錯。這個做法亦是用一點記憶體換取減少重複計算,並非令所有操作都沒有成本。

網址計數示例,並非正式環境效能數據。
// One pass to count, then reuse the result.
const uses = new Map();
for (const row of rows) {
  uses.set(row.url, (uses.get(row.url) ?? 0) + 1);
}
for (const row of rows) {
  const shared = uses.get(row.url) > 1;
  // Process this row using the same normalised URL key.
}

檢查資料增加時,工作怎樣增加

測試時可用幾組有代表性的資料量,同時比較輸出結果與實際做了多少工作。回歸檢查可以直接統計建立索引或掃描列表的次數,不必只靠容易受執行環境影響的時間門檻;實際執行時間則另外量度。

迴圈裏有迴圈,不一定就是錯。要看的是:資料增加時,有沒有不必要地重複整份工作。先看輔助函式和回呼裏做了甚麼,再決定是否真的需要更大的伺服器。

相關專案

My Next Step