问题标签 [ropes]

来自维基百科：

主要缺点是更大的整体空间使用和更慢的索引，随着树结构变得更大和更深，这两者都变得更加严重。然而，索引的许多实际应用只涉及对字符串的迭代，只要叶节点足够大以受益于缓存效应，它就会保持快速。

我正在实现绳索和字符串之间的某种妥协。基本上它只是绳索，除了当连接的字符串很短时我将连接对象扁平化为字符串。这有几个原因：

1. 当连接的字符串很短时，连接对象的好处是最小的（以正常形式连接两个字符串不需要太长时间）。
2. 这样做会减少树的大小/深度（减少绳索的缺点）。
3. 这样做会增加叶节点的大小（以更好地利用缓存）。

但是，随着长度变长，绳索的优势也会降低，所以我想找到一些折衷方案。从逻辑上讲，“最佳位置”似乎在“叶节点大到足以从缓存效应中受益”的地方。问题是，我不知道它有多大。

编辑：当我写这篇文章时，我想到理想的大小应该是缓存页面的大小，因为绳索只会导致缓存未命中，因为它们无论如何都会在字符串中发生。所以我的第二个问题是，这个推理是否正确？是否有一种跨平台的方法来检测缓存页面的大小？

我的目标语言是 C++。

如果 Ruby 正则表达式匹配非字符串，to_str则在该对象上调用该方法以获取要匹配的实际字符串。我想避免这种行为；我想将正则表达式与不是字符串的对象进行匹配，但在逻辑上可以被认为是随机可访问的字节序列，并且对它们的所有访问都是通过一种byte_at()方法进行调解的（在精神上类似于 Java 的CharSequence.char_at()方法）。

例如，假设我想在任意正则表达式的任意文件中查找字节偏移量；该表达式可能是多行的，因此我不能一次只读取一行并在每一行中查找匹配项。如果文件很大，我不能把它全部放在内存中，所以我不能把它作为一个大字符串读入。但是，定义一个获取文件第 n 个字节的方法（根据速度需要进行缓冲和缓存）就足够简单了。

最终，我想构建一个功能齐全的绳索类，就像在Ruby Quiz #137中一样，并且我希望能够在它们上使用正则表达式，而不会因为将它们转换为字符串而造成性能损失。

我不想在 Ruby 的正则表达式实现的内部陷入困境，所以任何见解都将不胜感激。

C# 中是否有绳索数据结构的公共实现？

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

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

我想知道在什么情况下你会在另一个 STL 容器上使用绳子？

我想要一个具有快速连接和编辑操作的字符串表示。我已经阅读了论文“绳索：弦乐的替代品”，但自 1995 年以来，该领域是否有任何重大改进？

编辑：我之前考虑过的一种可能性是使用带有字符串作为叶子的2-3 指树，但我没有对此进行详细分析；这会在末端和对数（以较小字符串的块数）连接上提供摊销的恒定时间添加/删除，而对于绳索则相反。

我正在阅读有关绳索的论文“绳索：字符串的替代方案”

[来自同一篇论文的图]

我想知道这是否是当今浏览器用于实现文本框的数据结构。我们是否为此使用绳索或其他一些数据结构？

除了文本框之外，还有其他地方使用绳索吗？

我问题的前一个标题不知何故也意味着我想知道字符串“记住”是如何发生的——当我输入时，我会得到建议。我现在已经改变了。

我想知道的是当我键入它时使用什么数据结构来存储字符串。它是像 char 数组这样简单的东西还是像绳子这样复杂的东西？

我查看了不同的论文，以下是我收集的信息：

• SGI 实现和C 绳既不能保证长绳索的 O(1) 时间连接，也不能保证较短绳索的 ~log N 深度。
• 不同的来源相互矛盾。维基百科声称 O(1) 级联。该页面说，仅当一个操作数较小时，连接才为 O(1)，否则为 O(log N)。

那么，串联的时间复杂度是多少？何时执行重新平衡以确保这种连接复杂性同时保持树平衡？在谈论这种复杂性时，是否假设了一些特定的使用模式？

早上好，

我正在编写一个语言解析器，并且正在寻找用于当前执行以下操作的回滚缓存的最佳结构：

• 当从流中请求一个新字符时，该字符被添加到缓存中，以防请求回滚。
• 当请求回滚时，返回到缓存中的某个点，这样当请求另一个字符时，它会从那里获取它。
• 找到令牌后，将回滚缓存中的所有内容删除到当前位置。

简而言之，我很想知道您认为哪种数据结构最适合：

• 优先级 1：附加字符（codePoints 将是一个受欢迎的补充）
• 优先级2：对数据结构做一个子字符串（如StringBuilder.delete(...)）（或完全清除）
• 优先级 3：能够创建缓存的字符串（例如 StringBuilder.toString()）

我希望尽快获得你的消息！

/usr/include/c++/4.5.1/ext/rope我的（和ropeimpl.h）中似乎有绳索的实现。我将它与 SGI STL 进行了比较，代码似乎几乎是相同的代码库。

我不知道它的状态或它的功能是否正常。我也不知道这是超级陈旧的代码，还是正在进行中的代码

无论如何，我还没有找到任何关于如何使用它的参考资料（如果可以的话）。你知道我错过了什么吗？有我可以使用的用法示例吗？

编辑如果你在这里看到 cvs 历史，你会看到最后一次活动是 4 个月前，这看起来不太活跃，但看起来也没有被遗弃。