Rope 数据结构是否比字符串生成器更有效？
https://stackoverflow.com/questions/1863440
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解决方案
的文档 SGI C++ 实现 详细介绍了大 O 行为与恒定因素，这是有启发性的。
他们的文档假设 涉及很长的字符串, ，提供的例子供参考谈论 10 MB 字符串. 。很少有程序会编写处理此类事情，并且对于具有此类要求的许多类别的问题，将它们重新设计为 基于流 而不是要求在可能的情况下提供完整的字符串，将会带来显着优异的结果。因为当您能够适当地将绳索视为部分（本身绳索）而不仅仅是字符序列时，此类绳索用于多兆字节字符序列的非流式操作。
显着的优点：
- 连接/插入几乎成为恒定时间操作
- 某些操作可能会重用先前的绳索部分以允许在内存中共享。
- 请注意，与 java 字符串不同，.Net 字符串不共享子字符串上的字符缓冲区 - 这种选择在内存占用方面有利有弊。绳索往往可以避免此类问题。
- 绳索允许延迟加载子串直到需要时
- 请注意，这很难做到正确，由于过度渴望访问，很容易变得毫无意义，并且需要使用代码将其视为绳子，而不是字符序列。
重大缺点：
- 随机读取访问变为 O(log n)
- 顺序读取访问的常数因子似乎在 5 到 10 之间
- 有效使用API 需要 将其视为一根绳子，而不仅仅是将绳子作为“普通”字符串 api 上的支持实现。
这导致了一些“明显”的用途（SGI 明确提到的第一个用途）。
- 编辑大文件的缓冲区，允许轻松撤消/重做
- 请注意，在某些时候，您可能需要将更改写入磁盘，涉及流式传输整个字符串，因此只有当大多数编辑主要驻留在内存中而不需要频繁持久化（例如通过自动保存功能）时，这才有用
- DNA 片段的操作，其中发生了显着的操作，但实际发生的输出很少
- 改变字符串局部部分的多线程算法。理论上，这种情况可以被分割到单独的线程和核心，而不需要获取子部分的本地副本，然后重新组合它们，从而节省大量内存并避免最后昂贵的串行组合操作。
在某些情况下，字符串中的域特定行为可以与 Rope 实现的相对简单的增强相结合，以允许：
- 具有大量公共子字符串的只读字符串可以进行简单的驻留，以显着节省内存。
- 具有稀疏结构或大量局部重复的字符串适合运行长度编码，同时仍然允许合理级别的随机访问。
- 子串边界本身就是可以存储信息的“节点”，尽管这种结构很可能更好地作为 基数特里树 如果它们很少被修改但经常被阅读。
正如您从列出的示例中看到的，所有这些都属于“利基”类别。此外，如果您愿意/能够将算法重写为流处理操作，那么一些很可能有更好的替代方案。
其他提示
这个问题的简短答案是肯定的，这几乎不需要解释。当然，在某些情况下，绳索数据结构比字符串构建器更有效。它们的工作方式不同，因此它们更适合不同的目的。
（从C＃角度来看）
在某些情况下，作为二进制树的绳索数据结构更好。当您查看极大的字符串值（想想来自SQL的100+ MB XML）时，绳索数据结构可以使整个过程远离大对象堆，当字符串对象通过85000字节时，该过程将其命中。
如果您要查看5-1000个字符的字符串，则可能不会提高性能，不足以值得。这是数据结构的另一种情况，该案例是为5％的极端情况而设计的。
这 第10届ICFP编程比赛 靠, ，基本上，使用绳索数据结构进行有效解决的人。这是获得合理时间内VM的最大技巧。
如果有很多前缀（显然“准备”一词是由它组成的，并且不是一个合适的词！），那么绳索是出色的（显然是“准备”一词！），并且有可能更好地插入； StringBuilders使用连续内存，因此仅有效地用于附加。
因此，StringBuilder非常适合通过添加片段 - 非常正常的用例来构建字符串。由于开发人员需要做很多事情，因此StringBuilders是一种非常主流的技术。
绳索非常适合编辑缓冲区，例如企业强度的TextArea背后的数据结构。因此（绳索的放松，例如，链接的线路列表而不是二进制树的链接列表）在UI控制世界中非常普遍，但这并不常见于这些控件的开发人员和用户。
您确实需要大量的数据和流失才能使绳索回报 - 处理器非常擅长流操作，如果您有RAM，则简单地将Realloc用于前缀，可以接受正常用例。顶部提到的比赛是我唯一看到它需要的比赛。
大多数高级文本编辑器代表文本主体是一种“绳索”（尽管在实现中，叶子通常不是单个字符，而是文本运行），主要是为了改善大型文本上的频繁插入和删除。
通常，StringBuilder被优化用于附加，并尝试最小化 重新分配的总数 不整体分配太多。典型的保证是（log2N分配，不到内存的2.5倍）。通常，该字符串是构建一次的，然后可以使用相当长的一段时间而不会被修改。
绳索是针对频繁插入和拆卸的优化的，并尝试最小化 复制数据量 （通过更多的分配）。在线性缓冲区实现中，每个插入和删除变为o（n），通常必须表示单个字符插入。
JavaScript VM通常将绳索用于字符串。
Higgs JavaScript VM的开发商Maxime Chevalier-Boisvert， 说:
在JavaScript中，您可以使用字符串数组，并最终使用array.prototype.join使字符串串联合理快速，o（n），但是JS程序员倾向于构建字符串的“自然”方式就是使用 += oterator，逐步构建它们。 JS字符串是不变的，因此，如果未在内部进行优化，则增量附加为O（n2）。我认为很可能是在JS发动机中实现的绳索，特别是因为具有插入弦附加的Sunspider Benchmarks。 JS Engine实施者使用绳索通过制作以前缓慢缓慢的东西来比其他绳索获得优势。如果不是为这些基准测试，我认为社区对弦乐效果不佳的哭泣可能会遇到“使用array.prototype.join，虚拟！”。
还.
