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

為什么正則表達式效率很重要？

雖然寫得好的正則表達式可能非常有效，但寫得不好的正則表達可能需要很長時間才能運行，并且會顯著降低系統(tǒng)的速度。編寫一個需要數(shù)小時或數(shù)天才能完成的正則表達式是很有可能的，甚至可以編寫一個在宇宙生命周期內(nèi)無法完成的正則表達，因為它是針對中等大小的字符串運行的。

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

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

低效正則表達式的剖析

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

例如，考慮匹配正則表達式a.*b*cd對字符串abc abc abc。匹配永遠不會成功，因為字符串中沒有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)，正則表達式需要執(zhí)行的比較次數(shù)與字符串長度乘以可能的中間匹配次數(shù)成比例。

在本例中，使用非貪婪運算符，即a.*?b.*?cd對匹配的數(shù)量沒有影響，因為正則表達式引擎仍然需要嘗試每個組合。

真實例子

讓我們來看一些基于實際正則表達式的示例，這些示例在實際系統(tǒng)運行中造成了問題：

\b.*xx.*foo

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

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

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

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

這通過兩種方式解決：

首先，是\b.*從正則表達式的開始處刪除，因為它除了減慢整個過程之外沒有其他用途。此更改將運行時間從幾天減少到幾秒。

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

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

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

讓我們把它分解：

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

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

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

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

此正則表達式通過刪除組重復(fù)來固定，因為它沒有任何用途：

-A(\D+)-B(\D+).運行時間從永遠下降到幾微秒。

編寫高效正則表達式的指南

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

考慮故障場景

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

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

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

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

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

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

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

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

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

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

只匹配你真正需要的

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

• \b\w+是冗余的，可以用“\w”替換。這將在原始正則表達式匹配的所有情況下匹配。
• 末尾的.*也是多余的，因為它對匹配是否成功沒有影響。

因此，整個正則表達式可以替換為\wXXX。

例外情況是，您需要使用匹配的字符串，而不是簡單地測試匹配是否成功

試著快速失敗

如果整個正則表達式達到不可能與預(yù)期目標匹配的程度，請嘗試使其失敗。

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

Profile-尤其是故障案例

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

盡量減少從主機中提取的數(shù)據(jù)

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

一個常見的錯誤是收回大量信息，例如：

cat file1 file2 file3...

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

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

更好的方法是只通過在主機上運行命令（如grep或head）來獲取您感興趣的信息。例如：

grep VERSION file1 file2 file3...

然后可以在返回的更短文本上運行正則表達式。

除非絕對必要，否則不要使用組

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

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

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

考慮正則表達式

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

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

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

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

索引

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

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

為簡單起見，每個表達式僅按其最長提示進行索引。在上面的例子中，提示將是｛｛提升｝｝。

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

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

試著給點提示

必須對給定給索引的每個字符串運行沒有提示的正則表達式。因此，嘗試使用可以計算提示的正則表達式是很重要的。

索引的提示提取算法無法處理以下類型的子表達式，將使用它們來劃分提示：

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

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

嘗試做出獨特的提示

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

總結(jié)

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

最新評論