是否有任何情况下Rope数据结构比字符串生成器更有效
与此问题相关,基于用户Eric Lippert的评论。
是否有任何情况下Rope数据结构比字符串生成器更有效? 有些人认为绳索数据结构在速度方面几乎从不比典型情况下的本地字符串或字符串构建器操作更好,所以我很想看到真实的情况,确实绳索更好。
SGI C ++实现的文档详细介绍了大O行为和常量因素,这些因素具有指导意义。
他们的文档假定涉及很长的字符串 ,参考的例子谈论10 MB字符串 。 很少有程序会编写处理这些问题的程序,并且对于许多类别的问题,需要将它们重新编写为基于流的,而不是要求尽可能使用完整的字符串将导致显着优异的结果。 当你能够将绳索适当地视为部分(自身绳索)而不仅仅是一系列字符时,这种绳索用于非兆字节序列的非流式操作。
重要优点:
- 连接/插入变成几乎恒定的时间操作
- 某些操作可以重复使用先前的绳索部分以允许在存储器中共享。
- 请注意.Net字符串与java字符串不同,它们不共享子字符串上的字符缓冲区 – 在内存占用方面有利有弊。 绳索倾向于避免这种问题。
- 绳索允许延迟加载子串直到需要
- 请注意,这很难做到,很容易因为过度的访问热情而呈现无意义,并且需要使用代码将其视为一根绳子而不是一系列字符。
重要缺点:
- 随机读取访问变为O(log n)
- 顺序读取访问的常数因素似乎在5到10之间
- 有效使用API 需要将其作为绳索处理,而不仅仅是作为“正常”字符串api上的后备实现插入绳索。
这导致一些“明显的”用途(SGI明确提到的)。
- 编辑大文件上的缓冲区,可以轻松撤消/重做
- 请注意,在某些时候,您可能需要将更改写入磁盘,涉及整个字符串的流式传输,因此这仅在大多数编辑主要驻留在内存中而非需要频繁持久性(例如通过自动保存function)时才有用。
- 对发生重大操作的DNA片段进行操作,但实际上输出很少
- multithreading算法,用于改变字符串的局部子部分。 理论上,这些情况可以分离为单独的线程和核心,而无需获取子部分的本地副本,然后重新组合它们,从而节省大量内存并避免最后进行昂贵的串行组合操作。
在某些情况下,字符串中的域特定行为可以与Rope实现相对简单的扩充相结合,以允许:
- 具有大量公共子串的只读字符串适合于简单实习以节省大量内存。
- 具有稀疏结构或显着局部重复的字符串适合于运行长度编码,同时仍允许合理级别的随机访问。
- 其中子字符串边界本身就是“节点”,其中可以存储信息,尽管如果它们很少被修改但经常被读取,这样的结构很可能作为Radix Trie完成。
从列出的例子中可以看出,所有这些都属于“利基”类别。 此外,如果您愿意/能够将算法重写为流处理操作,则有几个可能具有更好的替代方案。
对这个问题的简短回答是肯定的,这几乎不需要解释。 当然,在某些情况下,Rope数据结构比字符串构建器更有效。 它们的工作方式不同,因此它们更适合不同的用途。
(从C#的角度来看)
作为二叉树的绳索数据结构在某些情况下更好。 当您查看非常大的字符串值(想想来自SQL的100多MB的xml)时,绳索数据结构可以使整个过程远离大对象堆,其中字符串对象在通过85000字节时命中它。
如果你正在查看5-1000个字符的字符串,它可能不会提高性能足以值得。 这是另一个数据结构的案例,专为5%的极端情况的人设计。
第10届ICFP编程竞赛基本上依赖于使用绳索数据结构进行有效求解的人。 这是让VM在合理时间内运行的重要技巧。
如果有很多前缀(显然单词“prepending”由IT人员组成并且不是一个正确的词!)绳索是优秀的,并且可能更好地插入; StringBuilders使用连续内存,因此只能有效地进行追加。
因此,StringBuilder非常适合通过附加片段来构建字符串 – 这是一个非常正常的用例。 由于开发人员需要做很多事情,StringBuilders是一种非常主流的技术。
绳索非常适合编辑缓冲区,例如,企业级TextArea背后的数据结构。 因此(放松Ropes,例如链接列表而不是二叉树)在UI控件世界中非常常见,但这并不经常暴露给这些控件的开发人员和用户。
你需要非常大量的数据和流失来使绳索得到回报 – 处理器非常擅长流操作,如果你有RAM,那么简单地重新分配前缀对于正常的用例来说是可以接受的。 在顶部提到的那场比赛是我见过它所需要的唯一一次。
大多数高级文本编辑器将文本主体表示为“一种绳索”(虽然在实现中,叶子通常不是单个字符,但是文本运行),主要是为了改进大文本上的频繁插入和删除。
通常,StringBuilder针对追加进行了优化,并尝试最小化重新分配的总数,而不会过多地分配。 典型的保证是(log2 N分配,小于内存的2.5倍)。 通常,字符串构建一次,然后可以使用很长一段时间而不进行修改。
绳索针对频繁插入和删除进行了优化,并尝试最小化复制的数据量 (通过大量分配)。 在线性缓冲区实现中,每个插入和删除都变为O(N),并且通常必须表示单个字符插入。
Javascript VM经常使用绳索来表示字符串。
Higgs Javascript VM的开发人员Maxime Chevalier-Boisvert 说 :
在JavaScript中,您可以使用字符串数组,最终使用Array.prototype.join来快速地使字符串连接起来,O(n),但JS程序员倾向于构建字符串的“自然”方式是使用+ =运算符追加逐步建立它们。 JS字符串是不可变的,因此如果内部没有优化,则增量附加是O(n2)。 我认为绳索很可能是在JS引擎中实现的,特别是因为SunSpider基准测试会附加字符串。 JS引擎实现者使用绳索通过制作之前速度较慢的东西来获得优势。 如果不是那些基准测试,我认为来自社区的关于字符串附加表现不佳的呼声可能已经被“使用Array.prototype.join,dummy!”所满足。
还有 。