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 上预计的运行时间。

Ropes for Java 简介

内存问题Java 代码中耗时恒定的子串实现会引起内存问题，因为子串引用会阻止初始字符串被进行垃圾搜集。Rope和 String都为此问题所困扰。
.Ropes for Java 是 rope 数据结构在 java 平台上的高质量实现（请参阅 参考资料）。它进行了广泛的优化，有助于提供全面的性能和内存使用。这一节将解释如何将 rope 集成进 Java 应用程序，并比较 rope 与 String和 StringBuffer的性能。

Ropes for Java 实现只向客户机公开了一个类：Rope。Rope实例可以用 Rope.BUILDER工厂构建器从任意 CharSequence上创建。

清单 1 显示了如何创建 rope。

清单 1. 创建 rope
    
 Rope r = Rope.BUILDER.build("Hello World");
 
Rope公开了一组操作方法，包括执行以下操作的方法：

•附加另一个字符序列
•删除子序列
•将另一个字符序列插入 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 的两个代码块之后，可以看出哪块代码执行得更好。

清单 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，应该比第一块执行得快一些。表 2 归纳了使用这两种方法在长度为 10，690，488 的 rope 上迭代的性能。为了比较，表 2 还包含了 String和 StringBuffer的时间。