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 上预计的运行时间。
文章来源于领测软件测试网 https://www.ltesting.net/