是否有任何情况下，Rope数据结构比字符串生成器更有效

 

与此问题相关，基于用户Eric Lippert的评论。

有什么情况下，Rope数据结构比字符串生成器更有效吗？ 有些人认为，在典型情况下，绳索数据结构在速度方面几乎从来没有比本地字符串或字符串构建器操作更好，所以我很好奇看到实际情况下绳索更好。

有关SGI C ++实现的文档详细介绍了大O行为与恒定因素之间的关系，这些都很有启发性。

他们的文档假设涉及很长的字符串，举例说明了有关10 MB字符串的示例。 只有很少的程序会被写出来处理这些事情，对于这类需求的许多类别的问题，重新设计它们是基于流的，而不是要求在可能的情况下提供完整的字符串将导致显着优越的结果。 因为这样的绳子是用于非流式处理多兆字节的字符序列的，所以当你能够将绳索适当地当作段（自己绳索）而不仅仅是一系列字符时。

重要优点：

  • 连接/插入变为几乎恒定的时间操作
  • 某些操作可能会重复使用先前的绳索段以允许在内存中共享。
  • 请注意，.Net字符串，与java字符串不同，它不会在子字符串上共享字符缓冲区 - 在内存占用方面具有优点和缺点。 绳索倾向于避免这种问题。
  • 绳索允许延迟加载子字符串直到需要
  • 请注意，由于过度渴望访问，这很难变得正确，非常容易渲染毫无意义，并且需要消耗代码将其视为绳索，而不是作为一系列字符。

    • 重大缺点：

  • 随机读访问成为O（log n）
  • 顺序读取访问的常数因子似乎在5到10之间
  • API的高效使用要求将其视为一根绳子，而不是仅仅将绳子放在“常规”字符串API上作为后备实现。

    • 这导致了一些“显而易见的”用途（SGI明确提到了这一点）。

  • 在大文件上编辑缓冲区可以轻松撤销/重做
  • 请注意，在某些时候，您可能需要将更改写入磁盘，涉及流式传输整个字符串，所以这只在大多数编辑主要驻留在内存中时才有用，而不需要频繁持久化（比如通过自动保存功能）
  • 操纵发生重大操纵的DNA片段，但实际上只发生很少的输出
  • 多线程算法，它改变了字符串的局部分段。 从理论上讲，这种情况下可以分开线程和核心，而不需要采取子部分的本地副本，然后重新组合它们，从而节省了大量内存，并避免了最后的昂贵的串行组合操作。

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

  • 只读字符串具有大量的常见子字符串，可以简单实施，节省大量内存。
  • 具有稀疏结构或重要本地重复的字符串可以运行长度编码，同时仍然允许合理的随机访问级别。
  • 在子字符串边界本身就是可以存储信息的“节点”的地方，尽管这样的结构如果很少被修改但经常被读取，它们可能更好地作为基数来完成。

    • 从上面列出的例子中可以看出，所有这些都属于“利基”范畴。 此外，如果您愿意/能够将算法重写为流处理操作，几个可能会有更好的选择。

    这个问题的简短答案是肯定的，而且这需要很少的解释。 当然，在某些情况下，Rope数据结构比字符串生成器更有效。 他们的工作方式不同，所以他们更适合不同的目的。

    （从C＃的角度来看）

    绳索数据结构作为二叉树在某些情况下更好。 当你在查看非常大的字符串值时（想象从SQL中得到100MB以上的xml），绳索数据结构可以保持整个进程离开大对象堆，字符串对象在传递85000字节时击中它。

    如果您正在查看5-1000个字符的字符串，则可能不会提高性能，足以胜任。 这是另一种针对5％有极端情况的人设计的数据结构。

    第十届ICFP编程大赛基本上依靠人们使用绳索数据结构进行有效解决。 这是让合理时间内运行虚拟机的大伎俩。

    如果有很多前缀（很明显，“prepending”由IT人员组成并且不是一个合适的词），则绳是非常好的，并且可能更适合插入; StringBuilders使用连续内存，因此只能有效地追加。

    因此，StringBuilder非常适合通过追加片段来构建字符串 - 这是非常正常的用例。 由于开发人员需要这么做，所以StringBuilders是一项非常主流的技术。

    编辑缓冲区的绳索非常棒，例如后面的​​数据结构，比如企业级TextArea。 因此（放松绳索，例如链接列表而不是二叉树）在UI控件世界中是非常普遍的，但这并不常见于这些控件的开发人员和用户。

    你需要非常大量的数据和流失来完成流程 - 处理器非常擅长流操作，如果你有RAM，那么只需重新分配前缀就可以正常使用。 上面提到的那场比赛是我见过的唯一一次。

    链接地址: http://www.djcxy.com/p/6775.html

    上一篇: Is there any scenario where the Rope data structure is more efficient than a string builder

    下一篇: What is the best Battleship AI?