陷阱 - 效率關注正規表示式

Created: November-22, 2018

正規表示式匹配是一個強大的工具（在 Java 和其他上下文中）但它確實有一些缺點。其中一個正規表示式往往相當昂貴。

應重用 Pattern 和 Matcher 例項

請考慮以下示例：

/**
 * Test if all strings in a list consist of English letters and numbers.
 * @param strings the list to be checked
 * @return 'true' if an only if all strings satisfy the criteria
 * @throws NullPointerException if 'strings' is 'null' or a 'null' element.
 */
public boolean allAlphanumeric(List<String> strings) {
    for (String s : strings) {
        if (!s.matches("[A-Za-z0-9]*")) {
            return false;
        }  
    }
    return true;
}

這段程式碼是正確的，但效率很低。問題出在 matches(...) 呼叫中。在引擎蓋下，s.matches("[A-Za-z0-9]*") 相當於：

Pattern.matches(s, "[A-Za-z0-9]*")

這相當於

Pattern.compile("[A-Za-z0-9]*").matcher(s).matches()

Pattern.compile("[A-Za-z0-9]*") 呼叫解析正規表示式，對其進行分析，並構造一個 Pattern 物件，該物件包含將由正規表示式引擎使用的資料結構。這是一個非平凡的計算。然後建立一個 Matcher 物件來包裝 s 引數。最後我們呼叫 match() 來進行實際的模式匹配。

問題是每次迴圈迭代都會重複這項工作。解決方案是重構程式碼如下：

private static Pattern ALPHA_NUMERIC = Pattern.compile("[A-Za-z0-9]*");

public boolean allAlphanumeric(List<String> strings) {
    Matcher matcher = ALPHA_NUMERIC.matcher("");
    for (String s : strings) {
        matcher.reset(s);
        if (!matcher.matches()) {
            return false;
        }  
    }
    return true;
}

請注意，Pattern 的 javadoc 指出：

此類的例項是不可變的，並且可以安全地供多個併發執行緒使用。Matcher 類的例項對於此類使用並不安全。

你應該使用 `find()` 時不要使用 `match()`

假設你要測試字串 s 是否包含一行中的三個或更多數字。你可以通過各種方式表達這一點，包括：

  if (s.matches(".*[0-9]{3}.*")) {
      System.out.println("matches");
  }

要麼

  if (Pattern.compile("[0-9]{3}").matcher(s).find()) {
      System.out.println("matches");
  }

第一個更簡潔，但也可能效率較低。從表面上看，第一個版本將嘗試將整個字串與模式匹配。此外，由於“。*”是一種貪婪模式，模式匹配器很可能急切地嘗試到字串的末尾，然後回溯直到找到匹配。

相比之下，第二個版本將從左到右進行搜尋，並在連續找到 3 個數字後立即停止搜尋。

使用更有效的正規表示式替代方法

正規表示式是一個強大的工具，但它們不應該是你唯一的工具。可以通過其他方式更有效地完成許多工。例如：

 Pattern.compile("ABC").matcher(s).find()

做同樣的事情：

 s.contains("ABC")

除了後者效率更高。（即使你可以分攤編譯正規表示式的成本。）

通常，非正規表示式更復雜。例如，由 matches() 執行的測試呼叫早期的 allAlplanumeric 方法可以重寫為：

 public boolean matches(String s) {
     for (char c : s) {
         if ((c >= 'A' && c <= 'Z') ||
             (c >= 'a' && c <= 'z') ||
             (c >= '0' && c <= '9')) {
              return false;
         }
     }
     return true;
 }

現在這比使用 Matcher 更多的程式碼，但它也會明顯更快。

災難性的回溯

（這可能是正規表示式的所有實現的問題，但我們在這裡會提到它，因為它是 Pattern 使用的一個陷阱。）

考慮這個（人為的）例子：

Pattern pat = Pattern.compile("(A+)+B");
System.out.println(pat.matcher("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB").matches());
System.out.println(pat.matcher("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC").matches());

第一個 println 呼叫將快速列印 true。第二個將列印 false。最終。實際上，如果你試驗上面的程式碼，你會發現每次在 C 之前新增 A 時，時間會加倍。

這是行為是災難性回溯的一個例子。實現正規表示式匹配的模式匹配引擎無效地嘗試模式可能匹配的所有可能方式。 **

讓我們來看看 (A+)+B 究竟意味著什麼。從表面上看，它似乎說“一個或多個 A 個字元後跟一個 B 值”，但實際上它表示一個或多個組，每個組由一個或多個 A 字元組成。所以，例如：

‘AB’僅匹配一種方式：’（A）B’
‘AAB’匹配兩種方式：’（AA）B’或’（A）（A）B`
‘AAAB’匹配四種方式：’（AAA）B’或’（AA）（A）Bor '(A)(AA)B 或’（A）（A）（A）B`
等等

換句話說，可能的匹配數是 2 N ，其中 N 是 A 個字元的數量。

上面的例子顯然是設計的，但是當使用考慮不周的正規表示式時，經常會出現表現出這種效能特徵的模式（即，對於大型的 thhuan28，O(2^N) 或 O(N^K)）。有一些標準的補救措施：

避免在其他重複模式中巢狀重複模式。
避免使用太多重複模式。
適當時使用非回溯重複。
不要將 regex 用於複雜的解析任務。（改為編寫一個合適的解析器。）

最後，請注意使用者或 API 客戶端可以提供具有病理特徵的正規表示式字串的情況。這可能導致意外或故意拒絕服務。

參考文獻：

在正規表示式的標籤，尤其是 http://stackoverflow.com/documentation/regex/977/backtracking#t=201610010339131361163 和 http://stackoverflow.com/documentation/regex/4527/when-you-should-not-use-正規表示式#噸= 201610010339593564913
傑夫阿特伍德的正則表演 。
Andreas Haufler 撰寫的 “如何用正規表示式殺死 Java” 。

應重用 Pattern 和 Matcher 例項

你應該使用 find() 時不要使用 match()

使用更有效的正規表示式替代方法

災難性的回溯

你應該使用 `find()` 時不要使用 `match()`