rope 數據結構 表示不能修改的字符序列，與 Java 的 String 非常像。但是 ropes 效率奇高的字符串變換操作使得它與 String 及其同一體系的可修改的 StringBuffer 和 StringBuilder 大不相同，非常適合那些執行繁重字符串操縱的應用程序，尤其在多線程環境下更是如此。
簡要概括過 rope 數據結構之后，本文將介紹 rope 在 Java 平臺上的實現 —— Ropes for Java。然后將在 Java 平臺上對 String、StringBuffer 和 Ropes for Java Rope 類進行測評；考察一些特殊的性能問題；并討論什么時候應該以及什么時候不應該在應用程序中使用 rope。
Rope：概述
一個 rope 代表一個不能修改的字符序列。rope 的長度 就是序列中字符的個數。多數字符串表示都將字符串連續地保存在內存中。rope 的關鍵特點就是它突破了這個限制，允許一個 rope 的各個片斷離散地存放，并通過連接節點（concatenation node）連接它們。這種設計使得 rope 節點的連接操作比 Java String 的連接操作更快。String 版本的連接操作要求將需要連接的兩個字符串復制到新位置，這是一種 O（n）操作。rope 版本的連接操作則只是創建一個新的連接節點，這是個 O（1）操作。（如果不熟悉 “大 O” 符號，請參閱 參考資料 獲得相關說明的鏈接。）
圖 1 演示了兩種字符串的表示方法。在左側的表示方法中，字符放在連續的內存位置內。Java 的字符串使用這種表示方式。在右側的表示方式中，離散的字符串通過連接節點組合在一起。
圖 1. 字符串的兩種表示方式
Rope 實現通常也將延遲對大型子串操作的求值，它的作法是引入子串節點。使用子串節點能夠將獲取長度為 n 的子串的時間從 O（n）降低到 O（log n），通常會減到 O（1）。需要指出的是，Java 的 String 由于是不可修改的，所以子串操作的時間是恒定的，但 StringBuilder 并不是這樣。
扁平 rope（flat rope） — 沒有連接節點或子串節點 — 的深度（depth）為 1。有連接和子串的 rope 的深度比它們所擁有的最深節點的深度大 1。
Rope 有兩項開銷是使用連續字符的字符串表達方式所沒有的。第一個開銷就是必須遍歷子串和連接節點的上層結構（superstructure）才能到達指定的字符。而且，這個樹形上層結構必須盡可能保持均衡，以便將遍歷的次數降到最少，這意味著 rope 需要偶而進行重新均衡的操作，以保持良好的讀取性能。即使 rope 的均衡很好，獲取指定位置的字符也是個 O（log n）操作，其中 n 是 rope 包含的連接和子串節點的個數。（為了方便，可以用 rope 的長度代替 n，因為長度總是比 rope 中的子串和連接節點的個數大。）
幸運的是，rope 的重新均衡操作非常迅速，至于應該何時進行重新均衡的決策也能夠自動制定，例如通過比較 rope 的長度和深度來決定。而且，在多數數據處理例程中，都需要對 rope 字符進行順序訪問，在這種情況下，rope 的迭代器能夠提供分攤的 O(1) 訪問速度。
表 1 比較了一些常見的字符串操作在 rope 和 Java String 上預計的運行時間。
文章來源于領測軟件測試網 http://www.kjueaiud.com/