Related to this question, based on a comment of user Eric Lippert.
是否有任何情况下 Rope数据结构比字符串生成器更有效？有些人认为，在典型情况下，rope 数据结构在速度方面几乎从来没有比原生字符串或字符串生成器操作好，所以我很想知道 rope 确实更好的现实场景。
最佳答案
SGI C++ implementation 的文档详细介绍了大 O 行为与具有指导意义的常量因素。
他们的文档假设涉及非常长的字符串，为引用而提出的示例讨论了 10 MB 的字符串。很少有人会编写处理此类事情的程序，并且对于具有此类需求的许多类问题，将它们重新设计为基于流，而不是要求尽可能提供完整的字符串，这将导致显着优越结果。当您能够将绳索适本地视为部分(它们本身是绳索)而不仅仅是字符序列时，此类绳索用于多兆字节字符序列的非流式处理。
显着优点:
- 连接/插入成为几乎恒定时间的操作
- 某些操作可能会重复使用之前的绳索部分以允许共享内存。
- 请注意，与 java 字符串不同，.Net 字符串不共享子字符串上的字符缓冲区 - 在内存占用方面有利有弊的选择。绳索往往会避免此类问题。
- Ropes 允许延迟加载子字符串直到需要
- 请注意，这很难做到正确，并且由于过度渴望访问而很容易变得毫无意义，并且需要使用代码将其视为绳索，而不是字符序列。
显着缺点:
- 随机读访问变为 O(log n)
- 顺序读取访问的常数因子似乎在 5 到 10 之间
- API 的高效使用需要将其视为绳索，而不仅仅是将绳索作为“普通”字符串 API 的支持实现。
这导致了一些“明显”的用途(SGI 明确提到的第一个)。
- 编辑大文件的缓冲区，允许轻松撤消/重做
- 请注意，在某些时候您可能需要将更改写入磁盘，涉及流式传输整个字符串，因此这仅在大多数编辑主要驻留在内存中而不是需要频繁持久化(例如通过自动保存功能)时才有用)
- 对 DNA 片段进行操作，其中发生了重大操作，但实际上发生的输出很少
- 多线程算法改变字符串的局部部分。从理论上讲，这种情况可以被分配到单独的线程和核心，而无需获取子部分的本地副本然后重新组合它们，从而节省大量内存并避免最后进行代价高昂的串行组合操作。
在某些情况下，字符串中的域特定行为可以与相对简单的 Rope 实现相结合，以允许:
- 具有大量公共(public)子字符串的只读字符串可以进行简单的驻留以节省大量内存。
- 具有稀疏结构或大量局部重复的字符串适合运行长度编码，同时仍允许合理级别的随机访问。
- 子字符串边界本身就是可以存储信息的“节点”，尽管这样的结构很可能做得更好 Radix Trie如果它们很少修改但经常阅读。
正如您从列出的示例中看到的那样，所有这些都属于“利基”类别。此外，如果您愿意/能够将算法重写为流处理操作，那么几个可能会有更好的选择。
关于c# - 是否存在 Rope 数据结构比字符串生成器更高效的场景，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1863440/