做下去,遇上新難題閱讀時間約 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.
}檢查資料增加時,工作怎樣增加
測試時可用幾組有代表性的資料量,同時比較輸出結果與實際做了多少工作。回歸檢查可以直接統計建立索引或掃描列表的次數,不必只靠容易受執行環境影響的時間門檻;實際執行時間則另外量度。
迴圈裏有迴圈,不一定就是錯。要看的是:資料增加時,有沒有不必要地重複整份工作。先看輔助函式和回呼裏做了甚麼,再決定是否真的需要更大的伺服器。