在講 String 對象優(yōu)化時，提到了 Split() 方法，該方法使用的正則表達(dá)式可能引起回溯問題，今天就來深入了解下，這究竟是怎么回事？

開始之前，我們先來看一個案例，可以幫助你更好地理解內(nèi)容。

在一次小型項(xiàng)目開發(fā)中，我遇到過這樣一個問題。為了宣傳新品，我們開發(fā)了一個小程序，按照之前評估的訪問量，這次活動預(yù)計(jì)參與用戶量 30W+，TPS（每秒事務(wù)處理量）最高 3000 左右。

這個結(jié)果來自我對接口做的微基準(zhǔn)性能測試。我習(xí)慣使用 ab 工具（通過 yum -y install httpd-tools 可以快速安裝）在另一臺機(jī)器上對 http 請求接口進(jìn)行測試。

我可以通過設(shè)置 -n 請求數(shù) /-c 并發(fā)用戶數(shù)來模擬線上的峰值請求，再通過 TPS、RT（每秒響應(yīng)時間）以及每秒請求時間分布情況這三個指標(biāo)來衡量接口的性能，如下圖所示（圖中隱藏部分為我的服務(wù)器地址）：

就在做性能測試的時候，我發(fā)現(xiàn)有一個提交接口的 TPS 一直上不去，按理說這個業(yè)務(wù)非常簡單，存在性能瓶頸的可能性并不大。

我迅速使用了排除法查找問題。首先將方法里面的業(yè)務(wù)代碼全部注釋，留一個空方法在這里，再看性能如何。這種方式能夠很好地區(qū)分是框架性能問題，還是業(yè)務(wù)代碼性能問題。

我快速定位到了是業(yè)務(wù)代碼問題，就馬上逐一查看代碼查找原因。我將插入數(shù)據(jù)庫操作代碼加上之后，TPS 稍微下降了，但還是沒有找到原因。最后，就只剩下 Split() 方法操作了，果然，我將 Split() 方法加入之后，TPS 明顯下降了。

可是一個 Split() 方法為什么會影響到 TPS 呢？下面我們就來了解下正則表達(dá)式的相關(guān)內(nèi)容，學(xué)完了答案也就出來了。

1、什么是正則表達(dá)式？

很基礎(chǔ)，這里帶你簡單回顧一下。

正則表達(dá)式是計(jì)算機(jī)科學(xué)的一個概念，很多語言都實(shí)現(xiàn)了它。正則表達(dá)式使用一些特定的元字符來檢索、匹配以及替換符合規(guī)則的字符串。

構(gòu)造正則表達(dá)式語法的元字符，由普通字符、標(biāo)準(zhǔn)字符、限定字符（量詞）、定位字符（邊界字符）組成。詳情可見下圖：

2、正則表達(dá)式引擎

正則表達(dá)式是一個用正則符號寫出的公式，程序?qū)@個公式進(jìn)行語法分析，建立一個語法分析樹，再根據(jù)這個分析樹結(jié)合正則表達(dá)式的引擎生成執(zhí)行程序（這個執(zhí)行程序我們把它稱作狀態(tài)機(jī)，也叫狀態(tài)自動機(jī)），用于字符匹配。

而這里的正則表達(dá)式引擎就是一套核心算法，用于建立狀態(tài)機(jī)。

目前實(shí)現(xiàn)正則表達(dá)式引擎的方式有兩種：DFA 自動機(jī)（Deterministic Final Automata 確定有限狀態(tài)自動機(jī)）和 NFA 自動機(jī)（Non deterministic Finite Automaton 非確定有限狀態(tài)自動機(jī)）。

對比來看，構(gòu)造 DFA 自動機(jī)的代價遠(yuǎn)大于 NFA 自動機(jī)，但 DFA 自動機(jī)的執(zhí)行效率高于 NFA 自動機(jī)。

假設(shè)一個字符串的長度是 n，如果用 DFA 自動機(jī)作為正則表達(dá)式引擎，則匹配的時間復(fù)雜度為 O(n)；如果用 NFA 自動機(jī)作為正則表達(dá)式引擎，由于 NFA 自動機(jī)在匹配過程中存在大量的分支和回溯，假設(shè) NFA 的狀態(tài)數(shù)為 s，則該匹配算法的時間復(fù)雜度為 O（ns）。

NFA 自動機(jī)的優(yōu)勢是支持更多功能。例如，捕獲 group、環(huán)視、占有優(yōu)先量詞等高級功能。這些功能都是基于子表達(dá)式獨(dú)立進(jìn)行匹配，因此在編程語言里，使用的正則表達(dá)式庫都是基于 NFA 實(shí)現(xiàn)的。

那么 NFA 自動機(jī)到底是怎么進(jìn)行匹配的呢？我以下面的字符和表達(dá)式來舉例說明。

text=“aabcab” regex=“bc”

NFA 自動機(jī)會讀取正則表達(dá)式的每一個字符，拿去和目標(biāo)字符串匹配，匹配成功就換正則表達(dá)式的下一個字符，反之就繼續(xù)和目標(biāo)字符串的下一個字符進(jìn)行匹配。分解一下過程。

首先，讀取正則表達(dá)式的第一個匹配符和字符串的第一個字符進(jìn)行比較，b 對 a，不匹配；繼續(xù)換字符串的下一個字符，也是 a，不匹配；繼續(xù)換下一個，是 b，匹配。

然后，同理，讀取正則表達(dá)式的第二個匹配符和字符串的第四個字符進(jìn)行比較，c 對 c，匹配；繼續(xù)讀取正則表達(dá)式的下一個字符，然而后面已經(jīng)沒有可匹配的字符了，結(jié)束。

這就是 NFA 自動機(jī)的匹配過程，雖然在實(shí)際應(yīng)用中，碰到的正則表達(dá)式都要比這復(fù)雜，但匹配方法是一樣的。

3、NFA 自動機(jī)的回溯?

用 NFA 自動機(jī)實(shí)現(xiàn)的比較復(fù)雜的正則表達(dá)式，在匹配過程中經(jīng)常會引起回溯問題。大量的回溯會長時間地占用 CPU，從而帶來系統(tǒng)性能開銷。我來舉例說明。

text=“abbc” regex=“ab{1,3}c”

這個例子，匹配目的比較簡單。匹配以 a 開頭，以 c 結(jié)尾，中間有 1-3 個 b 字符的字符串。NFA 自動機(jī)對其解析的過程是這樣的：

首先，讀取正則表達(dá)式第一個匹配符 a 和字符串第一個字符 a 進(jìn)行比較，a 對 a，匹配。

然后，讀取正則表達(dá)式第二個匹配符 b{1,3} 和字符串的第二個字符 b 進(jìn)行比較，匹配。但因?yàn)?b{1,3} 表示 1-3 個 b 字符串，NFA 自動機(jī)又具有貪婪特性，所以此時不會繼續(xù)讀取正則表達(dá)式的下一個匹配符，而是依舊使用 b{1,3} 和字符串的第三個字符 b 進(jìn)行比較，結(jié)果還是匹配。

接著繼續(xù)使用 b{1,3} 和字符串的第四個字符 c 進(jìn)行比較，發(fā)現(xiàn)不匹配了，此時就會發(fā)生回溯，已經(jīng)讀取的字符串第四個字符 c 將被吐出去，指針回到第三個字符 b 的位置。

那么發(fā)生回溯以后，匹配過程怎么繼續(xù)呢？程序會讀取正則表達(dá)式的下一個匹配符 c，和字符串中的第四個字符 c 進(jìn)行比較，結(jié)果匹配，結(jié)束。

4、如何避免回溯問題？

既然回溯會給系統(tǒng)帶來性能開銷，那我們?nèi)绾螒?yīng)對呢？如果你有仔細(xì)看上面那個案例的話，你會發(fā)現(xiàn) NFA 自動機(jī)的貪婪特性就是導(dǎo)火索，這和正則表達(dá)式的匹配模式息息相關(guān)，一起來了解一下。

4.1、貪婪模式（Greedy）

顧名思義，就是在數(shù)量匹配中，如果單獨(dú)使用 +、 ? 、* 或{min,max} 等量詞，正則表達(dá)式會匹配盡可能多的內(nèi)容。

例如，上邊那個例子：

text=“abbc” regex=“ab{1,3}c”

就是在貪婪模式下，NFA 自動機(jī)讀取了最大的匹配范圍，即匹配 3 個 b 字符。匹配發(fā)生了一次失敗，就引起了一次回溯。如果匹配結(jié)果是“abbbc”，就會匹配成功。

text=“abbbc” regex=“ab{1,3}c”

4.2、懶惰模式（Reluctant）

在該模式下，正則表達(dá)式會盡可能少地重復(fù)匹配字符。如果匹配成功，它會繼續(xù)匹配剩余的字符串。

例如，在上面例子的字符后面加一個“？”，就可以開啟懶惰模式。

text=“abc” regex=“ab{1,3}?c”

匹配結(jié)果是“abc”，該模式下 NFA 自動機(jī)首先選擇最小的匹配范圍，即匹配 1 個 b 字符，因此就避免了回溯問題。

4.3、獨(dú)占模式（Possessive）

同貪婪模式一樣，獨(dú)占模式一樣會最大限度地匹配更多內(nèi)容；不同的是，在獨(dú)占模式下，匹配失敗就會結(jié)束匹配，不會發(fā)生回溯問題。

還是上邊的例子，在字符后面加一個“+”，就可以開啟獨(dú)占模式。

text=“abbc” regex=“ab{1,3}+bc”

結(jié)果是不匹配，結(jié)束匹配，不會發(fā)生回溯問題。講到這里，你應(yīng)該非常清楚了，避免回溯的方法就是：使用懶惰模式和獨(dú)占模式。

還有開頭那道“一個 split() 方法為什么會影響到 TPS”的存疑，你應(yīng)該也清楚了吧？

我使用了 split() 方法提取域名，并檢查請求參數(shù)是否符合規(guī)定。split() 在匹配分組時遇到特殊字符產(chǎn)生了大量回溯，我當(dāng)時是在正則表達(dá)式后加了一個需要匹配的字符和“+”，解決了這個問題。

\\?(([A-Za-z0-9-~_=%]++\\&{0,1})+)

5、正則表達(dá)式的優(yōu)化

正則表達(dá)式帶來的性能問題，給我敲了個警鐘，在這里我也希望分享給你一些心得。任何一個細(xì)節(jié)問題，都有可能導(dǎo)致性能問題，而這背后折射出來的是我們對這項(xiàng)技術(shù)的了解不夠透徹。所以我鼓勵你學(xué)習(xí)性能調(diào)優(yōu)，要掌握方法論，學(xué)會透過現(xiàn)象看本質(zhì)。下面我就總結(jié)幾種正則表達(dá)式的優(yōu)化方法給你。

5.1、少用貪婪模式，多用獨(dú)占模式

貪婪模式會引起回溯問題，我們可以使用獨(dú)占模式來避免回溯。前面詳解過了，這里我就不再解釋了。

5.2、減少分支選擇

分支選擇類型“(X|Y|Z)”的正則表達(dá)式會降低性能，我們在開發(fā)的時候要盡量減少使用。如果一定要用，我們可以通過以下幾種方式來優(yōu)化：

首先，我們需要考慮選擇的順序，將比較常用的選擇項(xiàng)放在前面，使它們可以較快地被匹配；

其次，我們可以嘗試提取共用模式，例如，將“(abcd|abef)”替換為“ab(cd|ef)”，后者匹配速度較快，因?yàn)?NFA 自動機(jī)會嘗試匹配 ab，如果沒有找到，就不會再嘗試任何選項(xiàng)；

最后，如果是簡單的分支選擇類型，我們可以用三次 index 代替“(X|Y|Z)”，如果測試的話，你就會發(fā)現(xiàn)三次 index 的效率要比“(X|Y|Z)”高出一些。

5.3、減少捕獲嵌套

在講這個方法之前，我先簡單介紹下什么是捕獲組和非捕獲組。

捕獲組是指把正則表達(dá)式中，子表達(dá)式匹配的內(nèi)容保存到以數(shù)字編號或顯式命名的數(shù)組中，方便后面引用。一般一個 () 就是一個捕獲組，捕獲組可以進(jìn)行嵌套。

非捕獲組則是指參與匹配卻不進(jìn)行分組編號的捕獲組，其表達(dá)式一般由（?:exp）組成。

在正則表達(dá)式中，每個捕獲組都有一個編號，編號 0 代表整個匹配到的內(nèi)容。我們可以看下面的例子：

public static void main( String[] args )
{
	String text = "<input high=\"20\" weight=\"70\">test</input>";
	String reg="(<input.*?>)(.*?)(</input>)";
	Pattern p = Pattern.compile(reg);
	Matcher m = p.matcher(text);
	while(m.find()) {
		System.out.println(m.group(0));// 整個匹配到的內(nèi)容
		System.out.println(m.group(1));//(<input.*?>)
		System.out.println(m.group(2));//(.*?)
		System.out.println(m.group(3));//(</input>)
	}
}

運(yùn)行結(jié)果：

<input high=\"20\" weight=\"70\">test</input>
<input high=\"20\" weight=\"70\">
test
</input>

如果你并不需要獲取某一個分組內(nèi)的文本，那么就使用非捕獲分組。例如，使用“(?:X)”代替“(X)”，我們再看下面的例子：

public static void main( String[] args )
{
	String text = "<input high=\"20\" weight=\"70\">test</input>";
	String reg="(?:<input.*?>)(.*?)(?:</input>)";
	Pattern p = Pattern.compile(reg);
	Matcher m = p.matcher(text);
	while(m.find()) {
		System.out.println(m.group(0));// 整個匹配到的內(nèi)容
		System.out.println(m.group(1));//(.*?)
	}
}

運(yùn)行結(jié)果：

<input high=\"20\" weight=\"70\">test</input>
test

綜上可知：減少不需要獲取的分組，可以提高正則表達(dá)式的性能。

6、總結(jié)

正則表達(dá)式雖然小，卻有著強(qiáng)大的匹配功能。我們經(jīng)常用到它，比如，注冊頁面手機(jī)號或郵箱的校驗(yàn)。

但很多時候，我們又會因?yàn)樗《雎运氖褂靡?guī)則，測試用例中又沒有覆蓋到一些特殊用例，不乏上線就中招的情況發(fā)生。

綜合我以往的經(jīng)驗(yàn)來看，如果使用正則表達(dá)式能使你的代碼簡潔方便，那么在做好性能排查的前提下，可以去使用；如果不能，那么正則表達(dá)式能不用就不用，以此避免造成更多的性能問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-606114.html

到了這里，關(guān)于04 - 慎重使用正則表達(dá)式的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！