有没有任何情况比字符串生成器更有效地使用Rope数据结构？

Question

与这个问题相关，基于用户埃里克·利珀特的评论。

有比字符串生成器更有效的绳数据结构的场景吗？有些人认为，在典型情况下，在速度方面，绳子数据结构几乎从来没有比本机字符串或字符串生成器操作更好，所以我很好奇地看到一些实际的场景，那里的绳子确实更好。

Answer 1

SGI C++实现的文档详细介绍了大O行为，并对常量因素进行了分析，这是有指导意义的。

他们的文档假设涉及很长的字符串，这些示例可供参考--大约10 MB的字符串。很少会编写程序来处理这类事情，对于许多类型的问题，这些需求的重新处理都是基于流的，而不是在可能的情况下要求完整的字符串可用，这将导致显着的优越结果。因此，当您能够适当地将绳子作为段(它们本身是绳子)，而不仅仅是字符序列时，绳子就可以用于不流操作多兆字符序列。

具有重要意义的项目：

• 级联/插入成为几乎恒定的时间操作。
• 某些操作可以重用以前的绳子部分，以允许共享内存。
  • 请注意，与java字符串不同，.Net字符串不共享子字符串上的字符缓冲区--在内存占用方面，这是一个有优缺点的选择。绳索往往能避免这种问题。

​

• 允许延迟加载子字符串直到所需的
  • 请注意，这是很难得到正确的，非常容易变得毫无意义，因为过分渴望访问，并需要消费代码来处理它作为绳子，而不是一个字符序列。

​

重大会议：

• 随机读取访问变为O(log )
• 顺序读取访问的常量因素似乎介于5到10之间。
• 要有效地使用api，就需要把它当作绳子来处理，而不仅仅是将其作为“普通”字符串API上的支持实现。

这导致了一些“明显”的使用(SGI明确提到的第一个)。

• 允许轻松撤消/重做的大型文件上的编辑缓冲区
  • 请注意，在某个时候，您可能需要将更改写入磁盘，包括通过整个字符串进行流处理，因此，只有当大多数编辑将主要驻留在内存中而不需要频繁的持久性(例如通过autosave函数)时，这才会有用。

​

• 对发生重大操作的DNA片段的操作，但实际上很少发生输出。
• 变异字符串局部子段的多线程算法。理论上，这样的情况可以被分割成不同的线程和内核，而不需要获取子段的本地副本，然后重新组合它们，从而节省了相当大的内存，并且避免了代价高昂的串行合并操作。

在有些情况下，字符串中特定域的行为可以与对Rope实现的相对简单的增强相结合，从而允许：

• 具有大量普通子字符串的只读字符串可以进行简单的实习，以节省大量内存。
• 具有稀疏结构或大量本地重复的字符串可以运行长度编码，同时仍然允许合理的随机访问级别。
• 其中，子字符串边界本身就是可以存储信息的“节点”，但是，如果很少修改但经常读取这些结构，这些结构作为三棱做得更好。

正如你可以从所列的例子中看到的那样，所有这些都属于“利基”类别。此外，如果您愿意/能够将算法重写为流处理操作，那么其中几个很可能有更好的选择。

Answer 2

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

(从C#的角度来看)

在某些情况下，作为二叉树的绳子数据结构更好。当您查看非常大的字符串值(假设来自100+的xml )时，绳子数据结构可以使整个进程远离大型对象堆，当字符串对象传递85000字节时，该进程就会命中它。

如果您查看的字符串为5-1000个字符，它可能无法提高性能足够值得它。这是另一个为5%极端情况下的人设计的数据结构的例子。

Answer 3

第十届ICFP编程竞赛基本上依赖于人们使用绳子数据结构来进行有效的解决。这是获得一个在合理时间内运行的VM的大窍门。

如果有大量的前缀(显然“前缀”一词是由IT人员组成的，并不是一个恰当的词！)而且可能更适合插入；StringBuilders使用连续内存，因此只能高效地用于附加。

因此，StringBuilder很适合通过附加片段(一种非常正常的用例)来构建字符串。由于开发人员需要大量这样做，StringBuilders是一种非常主流的技术。

对于编辑缓冲区来说，绳索是很好的，例如，企业强度TextArea背后的数据结构。因此(松开绳索，例如链接的行列表而不是二叉树)在UI控件世界中非常常见，但这些控件的开发人员和用户并不经常公开这种情况。

你需要非常大量的数据和搅动才能让绳子得到回报--处理器非常擅长流操作，如果你有RAM，那么简单的用于前缀的realloc对于正常的用例来说是可以接受的。上面提到的比赛是我唯一一次看到它的需要。