雜記 › 技術筆記 › 文字比對的代價全在 (m+1)×(n+1) 這張表:6000 行還能跑,8000 行直接堆疊記憶體崩潰

文字比對的代價全在 (m+1)×(n+1) 這張表:6000 行還能跑,8000 行直接堆疊記憶體崩潰

代價落在這張 (m+1)×(n+1) 的表上

問題是從一次很普通的貼上開始的:兩份各 2000 行的文字貼進去,頁面沒有報錯,也沒有進度條,但就是明顯地停了一下。停在哪?停在最長共同子序列(LCS)動態規劃要填的那張二維表上。兩個輸入的行數記作 m 和 n,面積就是 (m+1)×(n+1);2000 行對 2000 行,是 4004001 個儲存格,實測堆疊記憶體增量 31.3MB,攤到每個儲存格約 8.2 位元組。

同一份輸入我分別在兩個地方計時:Node 裡中位耗時 85.4ms,Chrome 154 裡 lineDiff 是 112.7ms,而整個 doDiff 走到 176.8ms——多出來的部分是組裝結果 DOM 的錢。這就是文字比對工具裡唯一真正昂貴的開銷項,剩下的讀空白字元、切行、拼字串都是零頭。

輸入規模Node 中位耗時堆疊記憶體佔用結局
2000 行對 2000 行85.4ms增量 31.3MB正常出結果
4000 行對 4000 行402.5ms隨行數平方漲正常出結果
6000 行對 6000 行844ms280.8MB堆疊記憶體上限壓到 512MB 也過得去
8000 行對 8000 行1093.4ms773.4MB預設堆疊記憶體能過,512MB 下 exit=134
10000 行對 10000 行瀏覽器 2478.9msjsHeapLimit 3586MB仍然出結果,不崩潰

把行數翻倍來看代價:85.4ms 到 402.5ms 是 4.7 倍。面積只該翻 4 倍,多出來的那部分是分配器開始搬家——陣列越漲越大,堆疊記憶體越拷越貴,所以曲線的斜率只會越來越陡,不會自己變平。

耗時由面積決定,跟你改了幾行無關

兩組對照很能說明問題。3000 行的文字只改 5 行,內層迴圈要走 9000000 次,實測 149.0ms,最後有 3005 個差異行;300 行的文字改掉 200 行,迴圈只有 90000 次,0.8ms 就完事,差異行卻有 500 個。改動更多的一組快了近兩百倍——因為演算法只認 m×n,差異行數是它算完以後才順手統計出來的副產物。換句話說,判斷「這次比對會不會慢」,只看兩邊各有多少行,別去盯著改動幅度。

只改一個標點,也是整行標紅

拿 5 行文字做實驗,把第 3 行末尾的句號換成驚嘆號,頁面給你的統計是「新增 1 行,刪除 1 行」,左右兩欄落下 12 個 .diff-line 節點,左欄整行的 background 是 rgba(255, 80, 80, 0.12)。關鍵是行內檢查:childElems=0,那條紅色長條裡沒有任何 span,也沒有 mark。也就是說,這個工具的粒度到行為止,改在哪個字元上,介面不會告訴你,只能自己在兩行裡用眼睛找。別指望它做「詞級醒目提示」,實測它連一個字都沒有醒目提示。

統計只有兩個數,第三個分支是死代碼

結果區上面那行字的模板在 L91,輸出格式固定是「新增 N 行,刪除 M 行」。我在 18 組用例裡把 lineDiff 回傳的 type 全收集了一遍,只有 equal、removed、added 三種值;L79-85 那段處理 modified 的分支永遠不會被走到,是死代碼。所以文案裡那種「能看出多少行被修改」的想像在介面上不存在:改一行,就只能讀成一行刪、一行增,兩個數各加一。

空白字元不 trim,但換行符號被瀏覽器先吃掉了

切行用的是 split('\n'),前後不做任何修剪,於是空白字元全部參與比對:「foo 」和「foo」比出「新增 1 行,刪除 1 行」;a\nb 和 a\nb\n 只差末尾一個換行,也報「新增 1 行,刪除 0 行」;一行只有空格的空白行對上一個真正的空行,是 1 刪 1 增。這類差異肉眼看不見,但它確實消耗面積、也確實標紅。

換行符號是另一回事。給 textarea 賦一個值 "a\r\nb",讀回來已經是 "a\nb",hasCR=false——瀏覽器在 L45 取值那一步就把 CRLF 和孤立的 CR 正規化成了 LF。所以同一對文字,頁面統計是「新增 0 行,刪除 0 行」,而把這兩串原樣餵給 Node 裡的 lineDiff,結果是 1 刪 1 增。也就是說,「比對前請先統一換行符號」這句提醒,在瀏覽器這條路徑上是白說的:差異早就被抹平了;只有你繞過頁面直接呼叫函式時,它才真實存在。

400px 的結果區,一螢幕只有 17 行

渲染層的尺寸是可以算的:.diff-line 的行盒高 22.390625px,容器 max-height:400px 實得 clientHeight=400,除一下就是 17 行。1000 行的半改輸入會產生 3000 個 div,scrollHeight=33586px,兩欄嚴格等高。也就是說,一次 1000 行的比對要在這個 400px 的框裡來回翻很多輪才看得完——瓶頸從演算法轉移到了你的滾輪上。

清空不是銷毀,而且根本沒有複製入口

按鈕只有兩個:「比對差異」和「清空」。在模板裡 grep 複製、clipboard、copy、download、execCommand,零命中——想把差異結果帶走,只能選取文字自己複製,沒有匯出,也沒有下載。而點「清空」之後發生的事也值得知道:它只是把結果區 display:none,統計文字和 3 個行節點還留在 DOM 裡,要等下一次比對才被真正銷毀。

Node 耗時 85.4 402.5 844 1093.4 2000 4000 6000 8000 毫秒 512MB 崩潰

圖 1:行數翻倍,耗時翻的是面積。6000 行那個點是堆疊記憶體上限壓到 512MB 時測的,同樣 512MB 下 8000 行直接 exit=134。

三個常被問到的點

Q:幾千行的檔案到底能不能比?

能,但兩邊的天花板不一樣,這正好把那篇講線上文字比對的文章裡「幾千行沒問題」的定性說法補成了實測:Node 側 2000 行 85.4ms、4000 行 402.5ms、8000 行 1093.4ms 且吃掉 773.4MB;把堆疊記憶體上限壓到 512MB,6000 行還要 844ms 但能過,8000 行就 exit=134——這種 OOM 不是能用 try/catch 兜住的例外,整個程序直接沒了。瀏覽器側 jsHeapLimit 3586MB,10000 行實測 2478.9ms 照樣出結果。結論:卡的從來不是演算法,是給你那一次呼叫分配的堆疊記憶體。

Q:為什麼我改了個逗號,整行都紅了?

因為它是按行出結果的:句號換驚嘆號也是「新增 1 行,刪除 1 行」,行內沒有任何字元級標記。想要「只看那一處」,只能自己在那一行裡找。

Q:結果太長,有沒有匯出差異的入口?

不行,實測的按鈕只有「比對差異」和「清空」,沒有複製也沒有下載;「清空」還只是隱藏,節點留在 DOM 裡等下一次比對才銷毀。

📎 相關文章

10 萬個鍵全進 DOM:JSON 檢視的渲染規模、爆棧深度與複製重排 2026-10-28 帶 g 的正規表示式是有狀態的:同一個 RegExp 連打 4 次 test 只過 2 個 2026-10-28 27760000 個像素零差異、體積漲到 15.881 倍:JPG 轉 PNG 的三層位元組帳 2026-10-28 20 行檔名拆成 18 行兩列:貼進 Excel 只佔 1 列,1e5 變成 100000 2026-10-28 整個資料夾拖進來,候選池只多了 1 個名字:檔案隨機抽取讀不到目錄裡的 2558 個檔案 2026-10-28