是否存在Rope数据结构比字符串生成器更高效的场景

文件 SGI C++ implementation 详细介绍了大O行为与恒定因素,这是很有启发性的。

涉及很长的字符串 ,为供参考而提出的例子 10 MB字符串 . 很少有程序会被编写来处理这样的事情,而且对于许多类这样的问题,需要对它们进行修改 基于流的 而不是要求在可能的情况下提供完整的字符串,这将导致显著优越的结果。因此,当您能够适当地将rope视为部分(本身就是rope)而不仅仅是一个字符序列时,rope用于对多兆字节字符序列进行非流操作。

重要优点:

• 某些操作可能会重用以前的rope部分,以允许在内存中共享。
  • 请注意,与java字符串不同的是,.Net字符串不共享子字符串上的字符缓冲区-就内存占用而言,这是一个有优缺点的选择。绳索倾向于避免此类问题。
• 绳索允许延迟加载子串,直到需要
  • 请注意,这很难做到正确,由于访问的过度渴望,很容易变得毫无意义,并且需要使用代码将其视为一条绳索,而不是一个字符序列。

重要缺点:

• 顺序读取访问的常数因子似乎在5到10之间
• API的有效使用 将其视为一个rope,而不仅仅是将rope作为“普通”字符串api上的支持实现。

• • 请注意,在某些情况下,您可能需要将更改写入磁盘,涉及整个字符串的流式处理,因此只有当大多数编辑主要驻留在内存中而不需要频繁的持久性(例如通过autosave函数)时,这才有用
• DNA片段的操纵,其中发生了显著的操纵,但实际上很少发生输出

在某些情况下,字符串中特定于域的行为可以与对Rope实现的相对简单的增强相结合,以允许:

• 具有稀疏结构或显著局部重复的字符串可以进行游程编码,同时仍然允许合理的随机访问级别。
• 其中子串边界本身是“节点”,可以存储信息,尽管这样的结构作为一个整体可能更好 Radix Trie

这个问题的简短答案是肯定的,这不需要什么解释。当然,在某些情况下,Rope数据结构比字符串生成器更有效。它们的工作方式不同,因此更适合不同的用途。

(从C#的角度)

如果您查看的是5-1000个字符的字符串,那么它的性能可能不会得到足够的提高。这是数据结构的另一个例子,它是为5%的处于极端情况的人设计的。

10th ICFP Programming Contest 依靠

因此,StringBuilder非常适合通过添加片段来构建字符串——这是一个非常正常的用例。由于开发人员经常需要这样做,StringBuilder是一种非常主流的技术。

你需要大量的数据和搅动才能让绳子得到回报——处理器非常擅长流操作,如果你有RAM,那么简单的realloc前缀就可以在正常的用例中工作。上面提到的那场比赛是我唯一一次看到它需要的。

通常,StringBuilder针对附加进行了优化,并尝试最小化 重新分配的总数 没有过多的分配。典型的保证是(log2n分配,小于内存的2.5x)。通常,字符串只构建一次,然后可以在不修改的情况下使用很长一段时间。

Rope针对频繁插入和移除进行了优化,并尝试将

Javascript虚拟机通常使用绳子来表示字符串。

Higgs Javascript虚拟机开发人员Maxime Chevalier Boisvert, says :

在JavaScript中,您可以使用字符串数组并最终 O(n),但JS程序员构建字符串的“自然”方式是 字符串是不可变的,因此如果没有对其进行内部优化, 增量追加是O(n2)。我想很可能是绳子 进行字符串追加的基准测试。使用JS引擎实现程序 通过做一些有价值的东西来获得优势 以前慢得更快。如果不是因为这些基准,我想 这是来自社区的关于字符串附加性能不佳的呼声 可能遇到“使用Array.prototype.join,dummy!”。

Also