提高正規表示式效能的幾點實用建議彙總

2022-08-22 14:02:15

為什麼正規表示式效率很重要？

雖然寫得好的正規表示式可能非常有效，但寫得不好的正則表達可能需要很長時間才能執行，並且會顯著降低系統的速度。編寫一個需要數小時或數天才能完成的正規表示式是很有可能的，甚至可以編寫一個在宇宙生命週期內無法完成的正則表達，因為它是針對中等大小的字串執行的。

在實踐中已經做了一些改進，使其比以前的版本更能抵抗低效的正規表示式。它現在最小化了在決定執行哪些TPL模式時所需的正規表示式匹配。它還擴充套件了在多個處理器之間執行TPL模式的工作，這樣，如果一個處理器忙於長正規表示式匹配，其他處理器可以繼續工作。

儘管有了這些改進，編寫高效的正規表示式對於保持系統發現的最佳執行仍然很重要。如果掃描網路時系統發現速度明顯減慢，並且推理或發現服務長時間使用100%CPU，則一個可能的原因是效率低下的正規表示式。

低效正規表示式的剖析

那麼，如何編寫低效的正規表示式呢？一個問題是當正規表示式執行過度回溯時；當正規表示式中有多個重複運運算元時，可能會發生這種情況。重複運運算元是+，*，或{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*"

作為粗略的指導，正規表示式需要執行的比較次數與字串長度乘以可能的中間匹配次數成比例。

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

真範例子

讓我們來看一些基於實際正規表示式的範例，這些範例在實際系統執行中造成了問題：

b.*xx.*foo

這是一個正規表示式，與主機上的程序命令列進行比較。當執行一個半兆位元組的字串時，它失敗了，該字串包含大量的xx重複，但不包含foo。

讓我們來分析它與字串匹配時發生的情況：

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

因此正規表示式匹配包含巢狀迴圈；總處理時間由字串長度（對於導致問題的命令列，該長度約為500000）乘以xx子字串數（約500）乘以字邊界數（約80000）確定。這大致相當於掃描一個20萬億字元長的字串，需要一天多的時間才能完成。

這通過兩種方式解決：

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

其次，我們可以使用關於我們想要匹配的資料的知識；在這種情況下，我們只對從字串開始到第一個空格的文字感興趣。因此，為了停止正規表示式掃描整個字串，我們可以將正規表示式錨定到字串的開頭，並使用S標記匹配非空白字元。最後一個正規表示式^S*xxS*foo將在到達空白字元時立即停止。現在，對同一字串執行時需要幾微秒。

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

這被用作敏感資料過濾器。其目的是掃描命令列並刪除以-A和-B開頭的選項。然而，它不僅沒有達到作者的意圖，而且它的執行方式可能永遠無法處理。

讓我們把它分解：

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

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

對於剩餘字串中的每個附加字元，組合數將加倍。

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

此正規表示式通過刪除組重複來固定，因為它沒有任何用途：

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

編寫高效正規表示式的指南

本節提供了幫助您避免常見問題和編寫高效正規表示式的指南。

考慮故障場景

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

注意萬用字元標記的多次重複

萬用字元標記是可以匹配多個字元的任何內容；這包括：.、w、D、字元類、否定字元類等。

如果一個正規表示式有兩個或多個連續的萬用字元重複，則存在回溯的可能性。例如，如果目標字串以a開頭，長度為N個字元，並且不包含x，則：

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

真的要當心巢狀組重複

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

不要以萬用字元重複開始正規表示式

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

由於這是一個非常常見的錯誤，實際發現會查詢以不必要的*開頭的正規表示式，並在可能的情況下將其去掉。

只匹配你真正需要的

正規表示式應設計為在有足夠的匹配項時立即停止，或者知道它無法匹配。例如，考慮正規表示式bw+XXX*

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

因此，整個正規表示式可以替換為wXXX。

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

試著快速失敗

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

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

Profile-尤其是故障案例

測試正規表示式以確保它與您期望的匹配是很重要的。但是，測試與正規表示式部分匹配的長字串（例如，隨機字元的兆位元組字串）的效能也是很重要的。

儘量減少從主機中提取的資料

TPL模式允許您在主機上執行命令，並檢索要用正規表示式搜尋的資料，例如版本資訊。

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

cat file1 file2 file3...

然後對資料執行正規表示式以提取一條資訊。

這可能會返回大量資料，因此正規表示式匹配不僅需要很長時間，而且在網路上傳輸資料也會很慢，並佔用資料儲存中的大量空間。

更好的方法是隻通過在主機上執行命令（如grep或head）來獲取您感興趣的資訊。例如：

grep VERSION file1 file2 file3...

然後可以在返回的更短文字上執行正規表示式。

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

當使用括號將正規表示式的一部分括在組中時，正規表示式引擎必須做額外的工作來儲存組匹配的文字，以備以後需要。在某些情況下，這可能會使匹配過程減慢四倍或更多。

如果需要使用括號，例如對於重複的正規表示式的一部分，但不需要在之後使用組的內容，則可以使用非分組版本的括號- (?:...).這通常仍然比沒有括號慢，但比普通括號快。例如：

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

考慮正規表示式

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

TPL觸發器的正規表示式優化

使用正規表示式索引來提高模式效能。索參照於快速消除那些顯然無法與給定字串匹配的正規表示式。這大大減少了必須執行的正規表示式的數量。因此，推理通常可以避免執行本檔案其餘部分描述的病理正規表示式。

在優化TPL模式觸發器的正規表示式時，有助於基本瞭解索引的工作方式。

索引

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

{{Hoist the }}
, ye "
!

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

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

當嘗試匹配字串時，將查詢索引中的一組正規表示式，其提示顯示為所匹配字串的子字串。一旦建立，索引可以非常快地執行此查詢。這個集合與一組沒有提示的表示式組合在一起，形成了所有可能與字串匹配的正規表示式的集合。嘗試依次將字串與每個表示式匹配，直到找到一個表示式或沒有表示式，這意味著字串不匹配。

試著給點提示

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

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

內建字元類，如d、w和。
自定義字元類，如[ijkxyz]
可選表示式，如？和*
組，如（foo）+
交替，如foo|bar

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

嘗試做出獨特的提示

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

總結

到此這篇關於提高正規表示式效能的幾點實用建議的文章就介紹到這了,更多相關提高正規表示式效能內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！