25

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

是否存在绳索数据结构比字符串生成器更有效的情况？有些人认为，rope 数据结构在速度方面几乎永远不会比典型情况下的本地字符串或字符串构建器操作更好，所以我很想看到绳索确实更好的现实场景。

4

5 回答 5

27

SGI C++ 实现的文档详细介绍了大 O 行为与具有启发性的常量因素。

他们的文档假设涉及非常长的字符串，作为参考的示例讨论了10 MB 的字符串。很少会编写处理此类事情的程序，并且对于具有此类要求的许多类别的问题，将它们重新设计为基于流而不是要求在可能的情况下提供完整的字符串将导致显着优越的结果。因此，当您能够适当地将绳索视为部分（它们本身是绳索）而不仅仅是字符序列时，此类绳索用于多兆字节字符序列的非流式处理。

显着优点：

  • 连接/插入成为几乎恒定的时间操作
  • 某些操作可能会重用之前的绳索部分以允许在内存中共享。
    • 请注意，.Net 字符串与 java 字符串不同，它不共享子字符串上的字符缓冲区 - 在内存占用方面有利有弊的选择。绳索往往会避免此类问题。
  • 绳索允许延迟加载子字符串，直到需要
    • 请注意，这很难做到正确，由于过度渴望访问而很容易变得毫无意义，并且需要使用代码将其视为绳索，而不是字符序列。

显着缺点：

  • 随机读取访问变为 O(log n)
  • 顺序读取访问的常数因子似乎在 5 到 10 之间
  • 有效使用 API需要将其视为绳索，而不仅仅是将绳索作为“普通”字符串 api 的支持实现。

这导致了一些“明显”的用途（SGI 明确提到的第一个用途）。

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

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

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

正如您从列出的示例中看到的那样，所有这些都属于“利基”类别。此外，如果您愿意/能够将算法重写为流处理操作，那么一些可能会有更好的选择。

于 2009-12-14T15:43:51.447 回答
12

这个问题的简短回答是肯定的，这几乎不需要解释。当然，在某些情况下，绳索数据结构比字符串生成器更有效。它们的工作方式不同，因此它们更适合不同的目的。

（从 C# 的角度来看）

作为二叉树的绳索数据结构在某些情况下更好。当您查看非常大的字符串值时（想想 100+ MB 来自 SQL 的 xml），绳索数据结构可以使整个过程远离大对象堆，当字符串对象通过 85000 字节时，它会在其中命中它。

如果您正在查看 5-1000 个字符的字符串，它可能不会提高性能，以至于值得。这是另一种数据结构的例子，它是为 5% 处于极端情况的人设计的。

于 2009-12-08T03:01:33.757 回答
12

第10 届 ICFP 编程竞赛基本上 依靠人们使用绳索数据结构进行有效解决。这是获得在合理时间内运行的 VM 的大技巧。

如果有很多前缀（显然“前缀”这个词是由 IT 人员编造的，不是一个合适的词！），绳子就非常好，并且可能更适合插入；StringBuilders 使用连续内存，因此只能有效地进行追加。

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

绳索非常适合编辑缓冲区，例如，企业级 TextArea 背后的数据结构。所以（绳索的放松，例如线的链表而不是二叉树）在 UI 控件世界中很常见，但这些控件的开发人员和用户并不经常公开。

您需要非常大量的数据和流失才能获得回报 - 处理器非常擅长流操作，如果您有 RAM，那么简单地重新分配前缀对于正常用例来说确实可以接受。顶部提到的那场比赛是我唯一一次看到它需要。

于 2009-12-10T09:19:49.567 回答
1

大多数高级文本编辑器将文本主体表示为“一种绳索”（尽管在实现中，叶子通常不是单个字符，而是文本运行），主要是为了改善对大文本的频繁插入和删除。

通常，StringBuilder 针对追加进行了优化，并尝试在不过度分配的情况下尽量减少重新分配的总数。典型的保证是（log2 N 分配，小于 2.5 倍的内存）。通常字符串会被构建一次，然后可以使用很长一段时间而不被修改。

Rope 针对频繁的插入和删除进行了优化，并尝试最小化复制的数据量（通过大量分配）。在线性缓冲区实现中，每次插入和删除都变成 O(N)，并且您通常必须表示单个字符的插入。

于 2009-12-14T17:30:29.553 回答
1

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！”。

也。

于 2014-11-15T08:42:55.357 回答