data-structures - 字符串表示 : improvements over ropes?

Question

我想要一个具有快速连接和编辑操作的字符串表示。我已阅读论文 "Ropes: an Alternative to Strings" ，但自 1995 年以来，这方面是否有任何重大改进？

编辑:我之前考虑过的一种可能性是使用 2-3 finger tree以字符串为叶子，但我没有对此进行详分割析；这在末端和对数(以较小字符串的块数)连接上提供了摊销的恒定时间添加/删除，而对于绳索，反之亦然。

Answer 1

这是一个老问题!我想知道有没有人读到这个。但它仍然很有趣。
在您的评论中，您说您在寻找:

Faster asymptotics, or constant factors, or less memory use

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

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

如果您也将树元素设为只读，您可以创建子绳(表示为绳的较长短语)，它会多次出现或在基于绳的字符串之间共享。这种共享的缺点是无法更改此类碎片绳部分:要对其进行编辑，或者要平衡需要复制对象图的树。但是，如果您主要是连接和迭代，那并不重要。在 Web 服务器中，您可以保留一个子绳索来表示 CSS 样式表声明，该声明在该服务器提供的所有 HTML 文档之间共享。