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

Question

与此问题相关,基于用户Eric Lippert的评论.

是否有任何情况下Rope数据结构比字符串生成器更有效？有些人认为绳索数据结构在速度方面几乎从不比典型情况下的本地字符串或字符串构建器操作更好,所以我很想看到确实绳索更好的真实场景.

Answer 1

SGI C++实现的文档详细介绍了大O行为和常量因素,这些因素具有指导意义.

他们的文档假定涉及很长的字符串,参考的例子谈论10 MB字符串.很少有程序会编写处理这些问题的程序,并且对于许多类别的问题,需要将它们重新设计为基于流的,而不是要求在可能的情况下提供完整的字符串将导致显着优异的结果.因为这样的绳索用于非流式操作多兆字节字符序列,当您能够将绳索适当地视为部分(自身绳索)而不仅仅是一系列字符时.

重要优点:

• 连接/插入变成几乎恒定的时间操作
• 某些操作可以重复使用先前的绳索部分以允许在存储器中共享.
  • 请注意.Net字符串与java字符串不同,它们不共享子字符串上的字符缓冲区 - 在内存占用方面有利有弊.绳索倾向于避免这种问题.
• 绳索允许延迟加载子串直到需要
  • 请注意,这很难正确,很容易因为过于急切的访问而呈现无意义,并且需要使用代码将其视为一根绳子,而不是一系列字符.

重要缺点:

• 随机读取访问变为O(log n)
• 顺序读取访问的常数因素似乎在5到10之间
• 有效使用API 需要将其视为绳索,而不仅仅是作为"普通"字符串api上的后备实现插入绳索.

这导致一些"明显的"用途(SGI明确提到的).

• 在大文件上编辑缓冲区,允许轻松撤消/重做
  • 请注意,在某些时候,您可能需要将更改写入磁盘,涉及整个字符串的流式传输,因此这仅在大多数编辑主要驻留在内存中而非需要频繁持久性(例如通过自动保存功能)时才有用.
• 对发生重大操作的DNA片段进行操作,但实际上输出很少
• 多线程算法,用于改变字符串的局部子部分.理论上,这些情况可以分离到单独的线程和核心,而无需获取子部分的本地副本,然后重新组合它们,从而节省大量内存并避免最后进行昂贵的串行组合操作.

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

• 具有大量公共子串的只读字符串适合于简单实习以节省大量内存.
• 具有稀疏结构或显着局部重复的字符串适合于运行长度编码,同时仍允许合理级别的随机访问.
• 其中子字符串边界本身就是"节点",其中可以存储信息,尽管这些结构很可能作为Radix Trie更好地完成,如果它们很少被修改但经常被读取.

从列出的例子中可以看出,所有这些都属于"利基"类别.此外,如果您愿意/能够将算法重写为流处理操作,则有几个可能具有更好的替代方案.

Answer 2

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

(从C#的角度来看)

作为二叉树的绳索数据结构在某些情况下更好.当您查看非常大的字符串值(想想来自SQL的100多MB的xml)时,绳索数据结构可以使整个过程保持在大对象堆上,当字符串对象超过85000字节时,它会在其中命中.

如果你正在查看5-1000个字符的字符串,它可能不会提高性能足以值得.这是另一个数据结构的案例,该数据结构是为5%的极端情况的人设计的.

Answer 3

第10届ICFP编程竞赛 基本上依赖于使用绳索数据结构进行有效求解的人.这是让VM在合理的时间内运行的重要技巧.

如果有很多前缀(显然"提前"这个词由IT人员组成并且不是一个正确的词!)绳索是优秀的,并且可能更适合插入; StringBuilders使用连续内存,因此只能有效地进行追加.

因此,StringBuilder非常适合通过附加片段来构建字符串 - 这是一个非常正常的用例.由于开发人员需要做很多事情,StringBuilders是一种非常主流的技术.

绳索非常适合编辑缓冲区,例如,企业级TextArea背后的数据结构.因此(放松Ropes,例如链接列表而不是二叉树)在UI控件世界中非常常见,但这并不经常暴露给这些控件的开发人员和用户.

你需要非常大量的数据和流失才能使绳索得到回报 - 处理器非常擅长流操作,如果你有RAM,那么简单地重新分配前缀对于正常的用例来说是可以接受的.在顶部提到的那场比赛是我见过它所需要的唯一一次.