天天看點

js 正則學習小記之比對字元串優化篇

從性能上來說,他非常糟糕,為什麼這麼說呢,因為 傳統型NFA引擎 遇到分支是從左往右比對的,

是以它會用 \\. 去比對每一個字元,發現不對後才用 [^"] 去比對。

比如這樣一個字元串: "123456\'78\"90"

共 16 個字元,除了第一個 " 直接比對成功,還剩餘 15 個,隻有 2 個轉義(4 個字元),是以 \\. 會失敗 10 次,隻有 2 次成功。

這 10 次比對失敗,需要回溯後用 [^"] 才能比對成功,當然最後一個 " 會直接比對成功。

很明顯,正常的字元串不可能全是轉義,正常的字元串才是主流,當然不排除有人故意全轉義的情況。

是以這個正則需要10次回溯後才能比對完成,如果字元串增長到 1K 1M 腫麼破呢?

是以我們要修改下這個正則,前後換下位置麼?

難道是 /"(?:[^"]|\\.)*"/ ? 呵呵,好像不太對,這樣的話轉義就不能被比對了。

js 正則學習小記之比對字元串優化篇

是以還要修改下 /"(?:[^"\\]|\\.)*"/ 這樣就OK了,遇到 \ 轉義就會用 \\. 去嘗試比對。

js 正則學習小記之比對字元串優化篇

可是還是有問題,因為我們在 [^"\\] 過濾掉了 \n 是以沒法比對多行字元的情況。

js 正則學習小記之比對字元串優化篇

js 中 字元串用 \ 折行是允許的,但是修改後的 正則 沒法比對這樣的字元串了,是以我們還得繼續修複。

因為 . 沒法比對換行,是以我們要用其他方式表達。

. 是用于比對除換行符之外的所有字元,難道我們要 [.\n] 來表示麼?

這樣是不對的,因為 [] 字元集中的 . 不再表示除換行符之外的所有字元,而是字元 . 也就是他本身一個字元而已。

那怎麼辦呢?

其實換個思路,

\d 表示 0-9

\D 表示 [^0-9]

那麼 [\d\D] 就表示所有了,不是麼。(新人朋友不知道能不能消化這個知識點。)

同理 [\s\S] [\w\W] 同樣可以。

是以 /"(?:[^"\\]|\\[\d\D])*"/ 這樣就滿足我們的要求了。

js 正則學習小記之比對字元串優化篇

效果不錯。

回頭過來分分析下他現在的性能吧。

還是這個字元串: "123456\'78\"90" , 正則 /"(?:[^"\\]|\\[\d\D])*"/

共 16 個字元,除了第一個 " 直接比對成功,還剩餘 15 個,有 2 個轉義(4 個字元),[^"\\] 能比對成功 10 個字元,隻有 2 次失敗。

為什麼不是 4 次失敗呢,明明有4個字元啊。\\ 雖然是2個字元,但是讀到第一個 \ 就比對失敗,然後用 \\[\d\D] 比對成功,

占用掉了兩個字元 \\ 下次用下一個o開始比對,是以隻有2次回溯。

隻有 2 次需要回溯,然後用 \\[\d\D] 比對成功。當然最後一個 " 還是會直接比對成功。

是以從 10 次回溯,減少到了 2 次,雖然正則比昨天臃腫了很多,但至少性能提升了不止一個等級。

OK,今天的分享完畢,明天見。

js 正則學習小記之比對字元串優化篇

繼續閱讀