當(dāng)正則表達(dá)式通常與大型數(shù)據(jù)集相匹配時(shí)它們的編寫必須高效。

為什么正則表達(dá)式效率很重要？

雖然寫得好的正則表達(dá)式可能非常有效，但寫得不好的正則表達(dá)可能需要很長(zhǎng)時(shí)間才能運(yùn)行，并且會(huì)顯著降低系統(tǒng)的速度。編寫一個(gè)需要數(shù)小時(shí)或數(shù)天才能完成的正則表達(dá)式是很有可能的，甚至可以編寫一個(gè)在宇宙生命周期內(nèi)無(wú)法完成的正則表達(dá)，因?yàn)樗轻槍?duì)中等大小的字符串運(yùn)行的。

在實(shí)踐中已經(jīng)做了一些改進(jìn)，使其比以前的版本更能抵抗低效的正則表達(dá)式。它現(xiàn)在最小化了在決定運(yùn)行哪些TPL模式時(shí)所需的正則表達(dá)式匹配。它還擴(kuò)展了在多個(gè)處理器之間運(yùn)行TPL模式的工作，這樣，如果一個(gè)處理器忙于長(zhǎng)正則表達(dá)式匹配，其他處理器可以繼續(xù)工作。

盡管有了這些改進(jìn)，編寫高效的正則表達(dá)式對(duì)于保持系統(tǒng)發(fā)現(xiàn)的最佳運(yùn)行仍然很重要。如果掃描網(wǎng)絡(luò)時(shí)系統(tǒng)發(fā)現(xiàn)速度明顯減慢，并且推理或發(fā)現(xiàn)服務(wù)長(zhǎng)時(shí)間使用100%CPU，則一個(gè)可能的原因是效率低下的正則表達(dá)式。

低效正則表達(dá)式的剖析

那么，如何編寫低效的正則表達(dá)式呢？一個(gè)問(wèn)題是當(dāng)正則表達(dá)式執(zhí)行過(guò)度回溯時(shí)；當(dāng)正則表達(dá)式中有多個(gè)重復(fù)運(yùn)算符時(shí)，可能會(huì)發(fā)生這種情況。重復(fù)運(yùn)算符是+，*，或{n，m}。如果正則表達(dá)式進(jìn)行了部分匹配，但隨后失敗，那么它必須返回并嘗試任何其他可能的部分匹配，以防其中任何一個(gè)成功。

例如，考慮匹配正則表達(dá)式a.*b*cd對(duì)字符串abc abc abc。匹配永遠(yuǎn)不會(huì)成功，因?yàn)樽址袥](méi)有d，但正則表達(dá)式在放棄之前仍必須檢查字母a、b和c的所有可能組合。即：

"*abc* abc abc",
"*ab*c ab*c* abc",
"*ab*c abc ab*c*",
"*a*bc a*bc* abc",
"*a*bc a*b*c ab*c*",
"*a*bc abc a*bc*",
"abc *abc* abc",
"abc *ab*c ab*c*",
"abc *a*bc a*bc*",
"abc abc *abc*"

作為粗略的指導(dǎo)，正則表達(dá)式需要執(zhí)行的比較次數(shù)與字符串長(zhǎng)度乘以可能的中間匹配次數(shù)成比例。

在本例中，使用非貪婪運(yùn)算符，即a.*?b.*?cd對(duì)匹配的數(shù)量沒(méi)有影響，因?yàn)檎齽t表達(dá)式引擎仍然需要嘗試每個(gè)組合。

真實(shí)例子

讓我們來(lái)看一些基于實(shí)際正則表達(dá)式的示例，這些示例在實(shí)際系統(tǒng)運(yùn)行中造成了問(wèn)題：

\b.*xx.*foo

這是一個(gè)正則表達(dá)式，與主機(jī)上的進(jìn)程命令行進(jìn)行比較。當(dāng)運(yùn)行一個(gè)半兆字節(jié)的字符串時(shí)，它失敗了，該字符串包含大量的xx重復(fù)，但不包含foo。

讓我們來(lái)分析它與字符串匹配時(shí)發(fā)生的情況：

• 引擎從字符串的開頭開始掃描。
• 引擎向前掃描，直到找到單詞邊界\b。
• 引擎從單詞邊界向前掃描，直到找到匹配的xx。
• 引擎從xx向前掃描，直到找到字符串foo或到達(dá)字符串的末尾。
• 如果它已經(jīng)到達(dá)字符串的末尾，并且不匹配foo，則它將返回到步驟3并向前掃描到下一個(gè)xx。
• 如果它匹配了所有的xx，但仍然沒(méi)有找到foo，那么它將返回到步驟2，并向前掃描到下一個(gè)單詞邊界。

因此正則表達(dá)式匹配包含嵌套循環(huán)；總處理時(shí)間由字符串長(zhǎng)度（對(duì)于導(dǎo)致問(wèn)題的命令行，該長(zhǎng)度約為500000）乘以xx子字符串?dāng)?shù)（約500）乘以字邊界數(shù)（約80000）確定。這大致相當(dāng)于掃描一個(gè)20萬(wàn)億字符長(zhǎng)的字符串，需要一天多的時(shí)間才能完成。

這通過(guò)兩種方式解決：

首先，是\b.*從正則表達(dá)式的開始處刪除，因?yàn)樗藴p慢整個(gè)過(guò)程之外沒(méi)有其他用途。此更改將運(yùn)行時(shí)間從幾天減少到幾秒。

其次，我們可以使用關(guān)于我們想要匹配的數(shù)據(jù)的知識(shí)；在這種情況下，我們只對(duì)從字符串開始到第一個(gè)空格的文本感興趣。因此，為了停止正則表達(dá)式掃描整個(gè)字符串，我們可以將正則表達(dá)式錨定到字符串的開頭，并使用\S標(biāo)記匹配非空白字符。最后一個(gè)正則表達(dá)式^\S*xx\S*foo將在到達(dá)空白字符時(shí)立即停止?，F(xiàn)在，對(duì)同一字符串運(yùn)行時(shí)需要幾微秒。

-A(\D+)+-B(\D+)

這被用作敏感數(shù)據(jù)過(guò)濾器。其目的是掃描命令行并刪除以-A和-B開頭的選項(xiàng)。然而，它不僅沒(méi)有達(dá)到作者的意圖，而且它的執(zhí)行方式可能永遠(yuǎn)無(wú)法處理。

讓我們把它分解：

• 從字符串開始掃描，直到找到-A。
• 匹配所有非數(shù)字字符，直到找到-B。
• 如果找不到-B，請(qǐng)嘗試匹配-A和字符串末尾或下一個(gè)數(shù)字之間的每個(gè)組組合。例如，如果字符串的其余部分是abcd，則它將與（\D+）的以下每個(gè)組匹配+

(abcd)
(abc)(d)
(ab)(cd)
(ab)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(a)(b)(c)(d).

對(duì)于剩余字符串中的每個(gè)附加字符，組合數(shù)將加倍。

因此，對(duì)于命令行包含-A但不后跟-B的情況，它將花費(fèi)與2n成比例的時(shí)間，其中N是-A和下一個(gè)數(shù)字或字符串結(jié)尾之間的字符數(shù)。為了更好地理解這一點(diǎn)，在標(biāo)準(zhǔn)PC上，22個(gè)字符的字符串大約需要一秒鐘。一個(gè)40個(gè)字符的字符串大約需要3天，而一個(gè)100個(gè)字符的串需要95836965945500年，盡管這尚未經(jīng)過(guò)測(cè)試。

此正則表達(dá)式通過(guò)刪除組重復(fù)來(lái)固定，因?yàn)樗鼪](méi)有任何用途：

-A(\D+)-B(\D+).運(yùn)行時(shí)間從永遠(yuǎn)下降到幾微秒。

編寫高效正則表達(dá)式的指南

本節(jié)提供了幫助您避免常見問(wèn)題和編寫高效正則表達(dá)式的指南。

考慮故障場(chǎng)景

如前面的示例所示，當(dāng)正則表達(dá)式無(wú)法完全匹配，但存在多個(gè)部分匹配時(shí)，就會(huì)出現(xiàn)問(wèn)題。編寫正則表達(dá)式時(shí)，僅考慮正則表達(dá)式成功時(shí)會(huì)發(fā)生什么是不夠的，還需要考慮正則表達(dá)式失敗時(shí)的執(zhí)行情況。實(shí)際發(fā)現(xiàn)中使用的正則表達(dá)式通常與大量的命令行相匹配，這些命令行可能非常長(zhǎng)（多達(dá)一百萬(wàn)個(gè)字符不是未知的），并且可能包含與正則表達(dá)式部分匹配的文本，而不是全部。

注意通配符標(biāo)記的多次重復(fù)

通配符標(biāo)記是可以匹配多個(gè)字符的任何內(nèi)容；這包括：.、\w、\D、字符類、否定字符類等。

如果一個(gè)正則表達(dá)式有兩個(gè)或多個(gè)連續(xù)的通配符重復(fù)，則存在回溯的可能性。例如，如果目標(biāo)字符串以a開頭，長(zhǎng)度為N個(gè)字符，并且不包含x，則：

• a.*.*x - 需要N2場(chǎng)比賽。
• a.*x*.*x -也需要N2個(gè)匹配，因?yàn)閤*可以是零長(zhǎng)度匹配，所以可以匹配字符串中的任何位置。
• a.*y.*x -將取N*M個(gè)匹配，其中M是y的出現(xiàn)次數(shù)。

真的要當(dāng)心嵌套組重復(fù)

如上所述，如果存在一個(gè)包含重復(fù)的組，并且該組本身也被重復(fù)，例如（.*），則可能的匹配數(shù)可能呈指數(shù)增長(zhǎng)。

不要以通配符重復(fù)開始正則表達(dá)式

這是上述第二點(diǎn)的特例。正則表達(dá)式引擎在字符串中的任何位置搜索匹配項(xiàng)，因此它嘗試從第一個(gè)字符開始匹配正則表達(dá)式，然后從第二個(gè)字符開始，依此類推，直到找到匹配項(xiàng)。*x的正則表達(dá)式等價(jià)于^.*的正則表達(dá)式*x，其遭受上述回溯問(wèn)題。

由于這是一個(gè)非常常見的錯(cuò)誤，實(shí)際發(fā)現(xiàn)會(huì)查找以不必要的*開頭的正則表達(dá)式，并在可能的情況下將其去掉。

只匹配你真正需要的

正則表達(dá)式應(yīng)設(shè)計(jì)為在有足夠的匹配項(xiàng)時(shí)立即停止，或者知道它無(wú)法匹配。例如，考慮正則表達(dá)式\b\w+XXX*

• \b\w+是冗余的，可以用“\w”替換。這將在原始正則表達(dá)式匹配的所有情況下匹配。
• 末尾的.*也是多余的，因?yàn)樗鼘?duì)匹配是否成功沒(méi)有影響。

因此，整個(gè)正則表達(dá)式可以替換為\wXXX。

例外情況是，您需要使用匹配的字符串，而不是簡(jiǎn)單地測(cè)試匹配是否成功

試著快速失敗

如果整個(gè)正則表達(dá)式達(dá)到不可能與預(yù)期目標(biāo)匹配的程度，請(qǐng)嘗試使其失敗。

上面所示的第一個(gè)真實(shí)世界示例就是一個(gè)例子。正則表達(dá)式^\S*xx\S*foo永遠(yuǎn)不會(huì)掃描超過(guò)第一個(gè)空格字符的字符串，無(wú)論它是否成功。在使用它的上下文中，這意味著掃描一個(gè)大約100個(gè)字符的序列和掃描一個(gè)數(shù)十萬(wàn)個(gè)字符的順序之間的區(qū)別。

Profile-尤其是故障案例

測(cè)試正則表達(dá)式以確保它與您期望的匹配是很重要的。但是，測(cè)試與正則表達(dá)式部分匹配的長(zhǎng)字符串（例如，隨機(jī)字符的兆字節(jié)字符串）的性能也是很重要的。

盡量減少?gòu)闹鳈C(jī)中提取的數(shù)據(jù)

TPL模式允許您在主機(jī)上運(yùn)行命令，并檢索要用正則表達(dá)式搜索的數(shù)據(jù)，例如版本信息。

一個(gè)常見的錯(cuò)誤是收回大量信息，例如：

cat file1 file2 file3...

然后對(duì)數(shù)據(jù)運(yùn)行正則表達(dá)式以提取一條信息。

這可能會(huì)返回大量數(shù)據(jù)，因此正則表達(dá)式匹配不僅需要很長(zhǎng)時(shí)間，而且在網(wǎng)絡(luò)上傳輸數(shù)據(jù)也會(huì)很慢，并占用數(shù)據(jù)存儲(chǔ)中的大量空間。

更好的方法是只通過(guò)在主機(jī)上運(yùn)行命令（如grep或head）來(lái)獲取您感興趣的信息。例如：

grep VERSION file1 file2 file3...

然后可以在返回的更短文本上運(yùn)行正則表達(dá)式。

除非絕對(duì)必要，否則不要使用組

當(dāng)使用括號(hào)將正則表達(dá)式的一部分括在組中時(shí)，正則表達(dá)式引擎必須做額外的工作來(lái)保存組匹配的文本，以備以后需要。在某些情況下，這可能會(huì)使匹配過(guò)程減慢四倍或更多。

如果需要使用括號(hào)，例如對(duì)于重復(fù)的正則表達(dá)式的一部分，但不需要在之后使用組的內(nèi)容，則可以使用非分組版本的括號(hào)- (?:...).這通常仍然比沒(méi)有括號(hào)慢，但比普通括號(hào)快。例如：

• (abc|def) -*慢速。僅在以后需要使用匹配文本時(shí)使用。
• (?:abc|def) - 更快
• abc|def -最快

考慮正則表達(dá)式

雖然這些指導(dǎo)方針可能會(huì)有所幫助，但沒(méi)有什么可以替代退一步重新檢查正則表達(dá)式以提高效率和準(zhǔn)確性所帶來(lái)的思想和理解。

TPL觸發(fā)器的正則表達(dá)式優(yōu)化

使用正則表達(dá)式索引來(lái)提高模式性能。索引用于快速消除那些顯然無(wú)法與給定字符串匹配的正則表達(dá)式。這大大減少了必須執(zhí)行的正則表達(dá)式的數(shù)量。因此，推理通?？梢员苊鈭?zhí)行本文檔其余部分描述的病理正則表達(dá)式。

在優(yōu)化TPL模式觸發(fā)器的正則表達(dá)式時(shí)，有助于基本了解索引的工作方式。

索引

正則表達(dá)式由一個(gè)稱為提示的屬性索引。提示是不區(qū)分大小寫的字符串，是與表達(dá)式匹配的每個(gè)字符串的子字符串。例如，表達(dá)式提升（后桅|主支架），ye（陸上流浪狗124壞血病狗）！它有三個(gè)明顯的提示：

• {{Hoist the }}
• , ye "
• !

為簡(jiǎn)單起見，每個(gè)表達(dá)式僅按其最長(zhǎng)提示進(jìn)行索引。在上面的例子中，提示將是｛｛提升｝｝。

一些正則表達(dá)式?jīng)]有任何提示。例如，\d+[-/]\d++[-]\d+沒(méi)有必須作為匹配字符串一部分的子字符串。提示計(jì)算器（目前）也相當(dāng)幼稚，遺漏了一些可能被提取的提示。沒(méi)有提示的表達(dá)式必須單獨(dú)處理。

當(dāng)嘗試匹配字符串時(shí)，將查詢索引中的一組正則表達(dá)式，其提示顯示為所匹配字符串的子字符串。一旦建立，索引可以非?？斓貓?zhí)行此查詢。這個(gè)集合與一組沒(méi)有提示的表達(dá)式組合在一起，形成了所有可能與字符串匹配的正則表達(dá)式的集合。嘗試依次將字符串與每個(gè)表達(dá)式匹配，直到找到一個(gè)表達(dá)式或沒(méi)有表達(dá)式，這意味著字符串不匹配。

試著給點(diǎn)提示

必須對(duì)給定給索引的每個(gè)字符串運(yùn)行沒(méi)有提示的正則表達(dá)式。因此，嘗試使用可以計(jì)算提示的正則表達(dá)式是很重要的。

索引的提示提取算法無(wú)法處理以下類型的子表達(dá)式，將使用它們來(lái)劃分提示：

• 內(nèi)置字符類，如\d、\w和。
• 自定義字符類，如[ijkxyz]
• 可選表達(dá)式，如？和*
• 組，如（foo）+
• 交替，如foo|bar

在表達(dá)式的頂層使用交替始終會(huì)阻止提取提示。組內(nèi)的交替不會(huì)阻止從組外的表達(dá)式部分提取提示。

嘗試做出獨(dú)特的提示

如果正則表達(dá)式只有一個(gè)類似java的提示，則需要對(duì)照大量字符串進(jìn)行檢查。嘗試設(shè)計(jì)您的表達(dá)式，使其最長(zhǎng)的提示相當(dāng)罕見。

總結(jié)

到此這篇關(guān)于提高正則表達(dá)式性能的幾點(diǎn)實(shí)用建議的文章就介紹到這了,更多相關(guān)提高正則表達(dá)式性能內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論