rope 數(shù)據(jù)結(jié)構(gòu) 表示不能修改的字符序列，與 Java 的 String 非常像。但是 ropes 效率奇高的字符串變換操作使得它與 String 及其同一體系的可修改的 StringBuffer 和 StringBuilder 大不相同，非常適合那些執(zhí)行繁重字符串操縱的應(yīng)用程序，尤其在多線程環(huán)境下更是如此。

簡(jiǎn)要概括過(guò) rope 數(shù)據(jù)結(jié)構(gòu)之后，本文將介紹 rope 在 Java 平臺(tái)上的實(shí)現(xiàn) —— Ropes for Java。然后將在 Java 平臺(tái)上對(duì) String、StringBuffer 和 Ropes for Java Rope 類進(jìn)行測(cè)評(píng)；考察一些特殊的性能問(wèn)題；并討論什么時(shí)候應(yīng)該以及什么時(shí)候不應(yīng)該在應(yīng)用程序中使用 rope。

Rope：概述

一個(gè) rope 代表一個(gè)不能修改的字符序列。rope 的長(zhǎng)度 是序列中字符的個(gè)數(shù)。多數(shù)字符串表示都將字符串連續(xù)地保存在內(nèi)存中。rope 的關(guān)鍵特點(diǎn)是它突破了這個(gè)限制，允許一個(gè) rope 的各個(gè)片斷離散地存放，并通過(guò)連接節(jié)點(diǎn)（concatenation node）連接它們。這種設(shè)計(jì)使得 rope 節(jié)點(diǎn)的連接操作比 Java String 的連接操作更快。String 版本的連接操作要求將需要連接的兩個(gè)字符串復(fù)制到新位置，這是一種 O（n）操作。rope 版本的連接操作則只是創(chuàng)建一個(gè)新的連接節(jié)點(diǎn)，這是個(gè) O（1）操作。（如果不熟悉 “大 O” 符號(hào)，請(qǐng)參閱 參考資料 獲得相關(guān)說(shuō)明的鏈接。）

圖 1 演示了兩種字符串的表示方法。在左側(cè)的表示方法中，字符放在連續(xù)的內(nèi)存位置內(nèi)。Java 的字符串使用這種表示方式。在右側(cè)的表示方式中，離散的字符串通過(guò)連接節(jié)點(diǎn)組合在一起。

圖 1. 字符串的兩種表示方式

Rope 實(shí)現(xiàn)通常也將延遲對(duì)大型子串操作的求值，它的作法是引入子串節(jié)點(diǎn)。使用子串節(jié)點(diǎn)能夠?qū)�獲取長(zhǎng)度為 n 的子串的時(shí)間從 O（n）降低到 O（log n），通常會(huì)減到 O（1）。需要指出的是，Java 的 String 由于是不可修改的，所以子串操作的時(shí)間是恒定的，但 StringBuilder 并不是這樣。

扁平 rope（flat rope） — 沒(méi)有連接節(jié)點(diǎn)或子串節(jié)點(diǎn) — 的深度（depth）為 1。有連接和子串的 rope 的深度比它們所擁有的深節(jié)點(diǎn)的深度大 1。

Rope 有兩項(xiàng)開銷是使用連續(xù)字符的字符串表達(dá)方式所沒(méi)有的。第一個(gè)開銷是必須遍歷子串和連接節(jié)點(diǎn)的上層結(jié)構(gòu)（superstructure）才能到達(dá)指定的字符。而且，這個(gè)樹形上層結(jié)構(gòu)必須盡可能保持均衡，以便將遍歷的次數(shù)降到少，這意味著 rope 需要偶而進(jìn)行重新均衡的操作，以保持良好的讀取性能。即使 rope 的均衡很好，獲取指定位置的字符也是個(gè) O（log n）操作，其中 n 是 rope 包含的連接和子串節(jié)點(diǎn)的個(gè)數(shù)。（為了方便，可以用 rope 的長(zhǎng)度代替 n，因?yàn)殚L(zhǎng)度總是比 rope 中的子串和連接節(jié)點(diǎn)的個(gè)數(shù)大。）

幸運(yùn)的是，rope 的重新均衡操作非常迅速，至于應(yīng)該何時(shí)進(jìn)行重新均衡的決策也能夠自動(dòng)制定，例如通過(guò)比較 rope 的長(zhǎng)度和深度來(lái)決定。而且，在多數(shù)數(shù)據(jù)處理例程中，都需要對(duì) rope 字符進(jìn)行順序訪問(wèn)，在這種情況下，rope 的迭代器能夠提供分?jǐn)偟?O(1) 訪問(wèn)速度。

表 1 比較了一些常見的字符串操作在 rope 和 Java String 上預(yù)計(jì)的運(yùn)行時(shí)間。

Ropes for Java 簡(jiǎn)介

內(nèi)存問(wèn)題Java 代碼中耗時(shí)恒定的子串實(shí)現(xiàn)會(huì)引起內(nèi)存問(wèn)題，因?yàn)樽哟�引用�?huì)阻止初始字符串被進(jìn)行垃圾搜集。Rope和 String都為此問(wèn)題所困擾。
.Ropes for Java 是 rope 數(shù)據(jù)結(jié)構(gòu)在 java 平臺(tái)上的高質(zhì)量實(shí)現(xiàn)（請(qǐng)參閱 參考資料）。它進(jìn)行了廣泛的優(yōu)化，有助于提供全面的性能和內(nèi)存使用。這一節(jié)將解釋如何將 rope 集成進(jìn) Java 應(yīng)用程序，并比較 rope 與 String和 StringBuffer的性能。

Ropes for Java 實(shí)現(xiàn)只向客戶機(jī)公開了一個(gè)類：Rope。Rope實(shí)例可以用 Rope.BUILDER工廠構(gòu)建器從任意 CharSequence上創(chuàng)建。

清單 1 顯示了如何創(chuàng)建 rope。

清單 1. 創(chuàng)建 rope
    
 Rope r = Rope.BUILDER.build("Hello World");
 
Rope公開了一組操作方法，包括執(zhí)行以下操作的方法：

•附加另一個(gè)字符序列
•刪除子序列
•將另一個(gè)字符序列插入 rope
請(qǐng)記住，同 String一樣，上面的每種變換都返回一個(gè)新 rope；原來(lái)的 rope 保持不變。清單 2 演示了其中一些操作。

清單 2. Rope 變換
    
 Rope r = Rope.BUILDER.build("Hello World");
 r = r.append("!");  // r is now "Hello World!"
 r = r.delete(0，6);  // r is now "World!"
 
有效的 rope

rope 上的迭代需要稍加注意。在查看了清單 3 的兩個(gè)代碼塊之后，可以看出哪塊代碼執(zhí)行得更好。

清單 3. 在 rope 上迭代的兩種技術(shù)
    
 //Technique 1
 final Rope r=some initialization code;
 for (int j=0; j<r.length(); ++j)
    result+=r.charAt(j);

 //Technique 2
 final Rope r=some initialization code;
 for (final char c: r)
    result+=c;
 
返回 rope 內(nèi)任意位置字符的操作是個(gè) O（log n）操作。但是，由于每個(gè)字符上都使用 charAt，清單 3 中第一個(gè)代碼塊花了 n倍的 O（log n）查詢時(shí)間。第二個(gè)代碼塊使用的是 Iterator，應(yīng)該比第一塊執(zhí)行得快一些。表 2 歸納了使用這兩種方法在長(zhǎng)度為 10，690，488 的 rope 上迭代的性能。為了比較，表 2 還包含了 String和 StringBuffer的時(shí)間。