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

簡要概括過 rope 數(shù)據(jù)結構之后，本文將介紹 rope 在 Java 平臺上的實現(xiàn) —— Ropes for Java。然后將在 Java 平臺上對 String、StringBuffer 和 Ropes for Java Rope 類進行測評；考察一些特殊的性能問題；并討論什么時候應該以及什么時候不應該在應用程序中使用 rope。

Rope：概述

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

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

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

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

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

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

幸運的是，rope 的重新均衡操作非常迅速，至于應該何時進行重新均衡的決策也能夠自動制定，例如通過比較 rope 的長度和深度來決定。而且，在多數(shù)數(shù)據(jù)處理例程中，都需要對 rope 字符進行順序訪問，在這種情況下，rope 的迭代器能夠提供分攤的 O(1) 訪問速度。

表 1 比較了一些常見的字符串操作在 rope 和 Java String 上預計的運行時間。

Ropes for Java 簡介

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

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

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

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

•附加另一個字符序列
•刪除子序列
•將另一個字符序列插入 rope
請記住，同 String一樣，上面的每種變換都返回一個新 rope；原來的 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 的兩個代碼塊之后，可以看出哪塊代碼執(zhí)行得更好。

清單 3. 在 rope 上迭代的兩種技術
    
 //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 內任意位置字符的操作是個 O（log n）操作。但是，由于每個字符上都使用 charAt，清單 3 中第一個代碼塊花了 n倍的 O（log n）查詢時間。第二個代碼塊使用的是 Iterator，應該比第一塊執(zhí)行得快一些。表 2 歸納了使用這兩種方法在長度為 10，690，488 的 rope 上迭代的性能。為了比較，表 2 還包含了 String和 StringBuffer的時間。