data-structures - 字符串表示：对绳索的改进？

Question

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

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

Answer 1

这是一个老问题！我想知道是否有人读过这个。但它仍然很耐人寻味。在您的评论中，您说您正在寻找：

更快的渐近线，或常数因子，或更少的内存使用

好吧，绳索有 O(1) 次插入和 O(n) 次迭代。你不能做得比这更好。子字符串和索引显然会更加昂贵。但大多数大型文档的用例不需要编辑或随机访问。如果您只在最后连接，则一维向量/字符串列表可以改善插入时间常数。我曾经在 JavaScript 中使用它，因为它的字符串连接速度很慢。

据说内存表示比使用字符串效率低。我对此表示怀疑：如果您使用具有垃圾收集功能的语言，则绳索允许您在多个地方使用相同的字符串片段实例。在代表 HTML 文档的绳索中，会有许多DIV's、SPAN's 和LINK元素。假设这些标签是编译时常量，这甚至可能会自动发生，并且您直接将它们添加到绳索中。即使对于这么短的短语，rope 文档的大小也会显着减小，与原始字符串的数量级相同。更长的字符串将产生净增益。

如果您还使树元素只读，您可以创建子绳索（表示为绳索的较长短语），它会多次出现或在基于绳索的字符串之间共享。这种共享的缺点是这样的分片绳部分不能改变：编辑它们，或者平衡你需要复制对象图的树。但是，如果您主要连接和迭代，这并不重要。在 Web 服务器中，您可以保留一个子绳索，该子绳索表示 CSS 样式表声明，该声明在该服务器提供的所有 HTML 文档中共享。