這個測評的方法是，從輸入字符串中選取隨機(jī)范圍的字符附加到它本身。這個測試的有趣之處在于：StringBuffer正是為了執(zhí)行快速附加而優(yōu)化的。圖 3 顯示了這個測評的結(jié)果。

不幸的是，圖 3 的視圖顯示 String的性能非常糟糕。但是，如預(yù)期所料，StringBuffer的性能非常好。

圖 4 從比較中撤出 String的結(jié)果，調(diào)整了圖表的比例，更清楚地顯示了 Rope和 StringBuffer性能的對比。

圖 4 顯示了圖 3 中不太明顯的 Rope和 StringBuffer之間的巨大區(qū)別。Rope很少能突破 x 軸。但是真正有趣的是 StringBuffer的圖 —驟然上升后保持穩(wěn)定上升，而不是平滑地上升。（作為練習(xí)，在閱讀下一段之前請?jiān)囍�解釋一下原因。�?/p>

原因與 StringBuffer的空間分配方式有關(guān)。它們在其內(nèi)部數(shù)組的末尾分配額外的空間，以便有效地附加字符。但是在空間用盡之后，必須分配全新的數(shù)組，并將所有數(shù)據(jù)復(fù)制到新數(shù)組。新數(shù)組一般根據(jù)當(dāng)前長度調(diào)整大小。隨著計(jì)劃長度的增加，生成的 StringBuffer的長度也會增加。隨著逐漸到達(dá)重新設(shè)置大小的閾值，花費(fèi)的時間也隨著額外的重新設(shè)置大小和復(fù)制而驟升。然后下幾個計(jì)劃長度的性能穩(wěn)定期（即緩慢提升的時間）也逐漸升高。因?yàn)槊總�計(jì)劃項(xiàng)增加的字符串長度總數(shù)大體相同，所以隨后的穩(wěn)定期比例可以作為重新設(shè)置底層數(shù)組大小的參考指標(biāo)。根據(jù)這些結(jié)果，可以準(zhǔn)確地估算出這個 StringBuffer實(shí)現(xiàn)大約在 1.5 左右。

結(jié)果小結(jié)

迄今為止，已經(jīng)用圖表展示了 Rope、String和 StringBuffer之間的性能差異。表 5 提供了所有字符變換測評的計(jì)時結(jié)果，使用了 480 ?計(jì)劃長度。

正則表達(dá)式的性能優(yōu)化

正則表達(dá)式在 JDK 1.4 版本中引入，是許多應(yīng)用程序中廣泛使用的一個功能。所以，正則表達(dá)式在 rope 中執(zhí)行良好至關(guān)重要。在 Java 語言中，正則表達(dá)式用 Pattern表示。要將 Pattern與 CharSequence的區(qū)域匹配，要使用模式實(shí)例構(gòu)建 Matcher對象，將 CharSequence作為參數(shù)傳遞給 Matcher。

操縱 CharSequence可為 Java 的正則表達(dá)式庫提供的靈活性，但也帶來了一個嚴(yán)重的缺陷。CharSequence只提供了一個方法來訪問它的字符：charAt(x)。像我在概述一節(jié)中提到過的，在擁有許多內(nèi)部節(jié)點(diǎn)的 rope 上隨機(jī)訪問字符的時間大約為 O（log n），所以遍歷時間為 O（nlog n）。為了演示這個缺陷帶來的問題，我測評了在長度為 10，690，488 的字符串中尋找模式 “Crachit*” 的所有實(shí)例所花費(fèi)的時間。所用的 rope 是使用插入測評的同一個變換序列構(gòu)建的，深度為 65。表 6 顯示了測評的結(jié)果。

顯然，Rope的匹配性能很差。（明確地講，對有許多內(nèi)部節(jié)點(diǎn)的 Rope是這樣。對于扁平 rope，性能幾乎與底層字符表示的性能相同。）即使在顯式地均衡過 Rope之后，雖然匹配快了 3.5 倍，Rope的性能還是沒有達(dá)到與 String或 StringBuffer相同的水平。