Java最佳實踐–字符串性能和精確字符串匹配

在使用Java編程語言時，我們將繼續討論與建議的實踐有關的系列文章，我們將討論String性能調優。我們將專注于如何有效地處理字符串創建，字符串更改和字符串匹配操作。此外，我們將提供我們自己的用于精確字符串匹配的最常用算法的實現。與Java開發工具包中提供的用于精確字符串匹配的幼稚方法相比，這些算法中的許多算法都可以實現更好的性能。本文以上述精確字符串匹配算法之間的性能比較作為結束。

所有討論的主題均基于用例，這些用例來自于電信行業的關鍵任務超高性能生產系統的開發。

在閱讀本文的每個部分之前，強烈建議您參考相關的Java API文檔以獲取詳細信息和代碼示例。

所有測試均針對具有以下特征的Sony Vaio進行：

系統：openSUSE 11.1（x86_64）
處理器（CPU）：Intel（R）Core（TM）2 Duo CPU T6670 @ 2.20GHz
處理器速度：1,200.00 MHz
總內存（RAM）：2.8 GB
Java：OpenJDK 1.6.0_0 64位

應用以下測試配置：

并發工作者線程數：1
每個工作人員重復測試的次數：1000
整體測試次數：100

字符串性能調優

許多人在使用String對象時并沒有考慮性能。但是，濫用String類可能會嚴重降低應用程序的性能。您應該記住的最重要的事情是：

字符串對象是不可變的。一旦創建了String對象，就無法更改它。每個更改String的操作都會導致至少創建一個新的對象實例。例如，使用串聯運算符（+）串聯兩個字符串會導致創建兩個新對象，一個用于實際串聯的臨時StringBuffer對象，一個指向串聯結果的新String實例（ StringBuffer “ toString（）”操作為用于實例化生成的String ）。另一方面，與串聯運算符（+）相比，使用String “ concat（String ..）”操作執行String串聯將提供更好的性能結果。在后臺，字符串 “ concat（String ..）”操作利用本機“ System.arrayCopy”操作來準備一個帶有兩個串聯字符串內容的字符數組。最后，創建一個新的String實例，該實例指向連接的結果
字符串引用是指向實際String對象實例的指針。因此，如果實際的String對象不同，則使用“ ==”運算符比較表示相同文字內容的兩個String實例將返回“ false”。此外，使用String “ equals（String ..）”或String “ equalsIgnoreCase（String ..）”操作比較兩個String實例可提供有效的結果，但如果兩個比較的String分別由不同的實例表示，則執行字符與字符的比較。它們的文字內容具有相同的長度。可以想象，“ equals（String ..）”和“ equalsIgnoreCase（String ..）”操作比“ ==”運算符要昂貴得多，后者在實例級別比較字符串。然而，上述操作在所有文字內容檢查之前執行實例相等性檢查（ this == obj ）。為了能夠在比較String實例時受益于“ this == obj”的相等性檢查，應將String值定義為文字字符串和/或字符串值常量表達式。這樣做，您的String實例將被JVM自動插入。另一種但不受歡??迎的方法是使用字符串 “ intern（）”操作，以便手動插入字符串。正如Java文檔中針對“ intern（）”方法明確指出的那樣，

“最初為空的字符串池由String類私下維護。
調用intern方法時，如果池已經包含等于equals（Object）方法確定的此String對象的字符串，則返回池中的字符串。

否則，將此String對象添加到池中，并返回對此String對象的引用。

因此，對于任何兩個字符串s和t，當且僅當s.equals（t）為true時，s.intern（）== t.intern（）為true。

所有文字字符串和字符串值常量表達式都將被嵌入。”

我們建議在處理String類時的最佳做法如下：

贊成創建文字字符串和字符串值常量表達式，而不是使用String構造函數方法之一創建新的String對象
利用字符數組執行String轉換操作可獲得最佳性能結果，但靈活性較差
在執行String轉換操作（例如，刪除，插入，替換或附加字符，連接或拆分String）時，請使用StringBuilder或StringBuffer類。 StringBuilder類在Java 1.5中引入，并且是StringBuffer類的非同步對等形式。因此，如果只有一個線程將執行String轉換操作，則傾向于使用StringBuilder類，因為它是性能最好的

模式優先精確字符串匹配

Java語言缺少快速的字符串搜索算法。字符串 “ indexOf（…）”和“ lastIndexOf（…）”操作針對源文本對所提供的模式執行幼稚搜索。天真的搜索基于“強力”模式第一個精確的字符串匹配算法。 “強力”算法包括檢查文本中所有位置的模式是否從那里開始。然后，每次嘗試后，它都會將圖案恰好向右移動一個位置。但是，仍然存在其他幾種算法，它們在速度和效率上都遠勝過“蠻力”算法。

應用程序需要兩種解決方案，具體取決于首先給出哪個字符串，模式或文本。在我們的例子中，模式是預先提供的，這意味著我們總是針對未知文本搜索提供的模式。對于需要全文搜索（文本優先精確字符串匹配）的所有應用程序，需要一套不同的算法來提供索引掃描。 Apache Lucene是實現后一種算法家族的最受歡迎的文本搜索引擎庫之一。盡管如此，本文只會研究第一種算法。

感謝這項偉大的工作，來自魯昂大學信息學院的魯昂大學的Christian Charras和Thierry Lecroq的一本書名為“ 精確字符串匹配算法 ”，我們得以用Java實現最精確的字符串匹配算法。，先給出模式。下面的列表顯示Christian Charras和Thierry Lecroq所提供的算法名稱，并在括號中顯示我們的算法實現“代碼名稱”。有關每種算法的更多信息，請單擊相應的鏈接，以便重定向到“精確字符串匹配算法”一書的相關部分。

蠻力算法（BF）
確定性有限自動機算法（DFA）
Karp-Rabin算法（KR）
移位或算法（SO）
Morris-Pratt算法（MP）
Knuth-Morris-Pratt算法（KMP）
西蒙算法（SMN）
Colussi算法（CLS）
Galil-Giancarlo算法（GG）
Apostolico-Crochemore算法（AC）
不太天真算法（NSN）
Boyer-Moore算法（BM）
Turbo BM算法（TBM）
Apostolico-Giancarlo算法（AG）
反向Colussi算法（RC）
Horspool算法（HP）
快速搜索算法（QS）
調優的Boyer-Moore算法（BMT）
Zhu-Takaoka算法（ZT）
Berry-Ravindran算法（BR）
史密斯算法（SMT）
Raita算法（RT）
逆因子算法（RF）
Turbo逆因子算法（TRF）
前向Dawg匹配算法（FDM）
后向不確定Dawg匹配算法（BNDM）
向后Oracle匹配算法（BOM）
Galil-Seiferas算法（GS）
雙向算法（TW）
有序字母算法中的字符串匹配（SMOA）
最佳失配算法（OM）
最大移位算法（MS）
跳過搜索算法（SS）
KMP跳過搜索算法（KPMSS）

在“精確字符串搜索算法”套件的初始版本（1.0.0）中，對于每種算法，我們都實現了三個實用程序操作：

compile（String pattern）–基于提供的模式執行所有必要預處理的靜態操作
findAll（String source）–返回包含所有索引的列表，其中搜索算法指示有效的模式匹配
findAll（String pattern，String source）–這是一個輔助靜態操作，封裝了上述兩個操作的功能

下面是使用Boyer-Moore算法（BM）的示例：

情況1

 BM bm = BM.compile(pattern);  List<Integer> idx = bm.findAll(source);  List<Integer> idx2 = bm.findAll(source2);  List<Integer> idx3 = bm.findAll(source3);

情況＃2

 List<Integer> idx = BM.findAll(pattern, source);

在第一種情況下，我們編譯模式并以兩個不同的步驟執行搜索。當我們必須在多個源文本中搜索同一模式時，此方法是合適的。通過編譯模式，由于預處理通常是繁重的操作，因此我們可以最大化性能結果。另一方面，對于一次搜索，第二種方法提供了更方便的API。

我們必須指出我們提供的實現是線程安全的，并且當前我們不支持模式中的正則表達式。

以下是我們的精確字符串搜索算法套件的算法實現之間的示例性能比較。我們使用65535個字符的完整字母大小搜索了1150000個字符的文本，以查找故意不存在的37個字符的短語。請不要忘記這是一個相對的性能比較。絕大多數提供的搜索算法的性能結果在很大程度上取決于提供的文本，提供的模式和字母大小。因此，您應該只將String搜索算法之間的所有性能比較視為相對的。

在本節的開頭，我們已經聲明Java語言缺少快速的String搜索算法。但是，與我們的算法套件相比，標準的Java天真的實現有多慢？為了回答上述問題，我們實現了兩種方法，以便使用標準Java API檢索潛在模式匹配的所有索引值：

方法1 – indexOf（）方法

 public static List<Integer> findAll(String pattern, String source) { List<Integer> idx = new ArrayList&ltInteger>(); int id = - 1 ; int shift = pattern.length(); int scnIdx = -shift; while (scnIdx != - 1 || id == - 1 ) { idx.add(scnIdx); id = scnIdx + shift; scnIdx = source.indexOf(pattern, id); } idx.remove( 0 ); return idx; }

方法2 – Matcher find（）方法

 public static List<Integer> findAll(String pattern, String source) { List<Integer> idx = new ArrayList&ltInteger>(); Pattern ptrn = Pattern.compile(pattern); Matcher mtch = ptrn.matcher(source); while (mtch.find()) idx.add(mtch.start()); ??return idx; }

下面我們給出上述搜索算法之間的性能比較表

水平軸表示每種算法進行預處理和解析提供的文本所需的平均時間（以毫秒為單位）。因此，較低的值更好。如您所見，Java天真實現（indexOf（）方法）以及幾乎所有我們的搜索算法實現都優于Java Matcher“ find（）”方法。換句話說，當您處理中小型字符串搜索時，最好實現類似于我們上面提供的代碼片段之類的東西，而不要使用更復雜的字符串搜索算法。另一方面，處理大型文檔時，我們套件中最快的算法之一肯定會派上用場！

您可以在此處下載精確字符串搜索算法套件發行版的1.0.0版

快樂編碼

賈斯汀

相關文章：