字符串表示:对绳索的改进？

Question

我想要一个具有快速连接和编辑操作的字符串表示.我读过"绳索:弦乐的替代品"这篇论文,但自1995年以来,这个领域有没有重大改进？

编辑:我之前考虑过的一种可能性是使用带有字符串作为树叶的2-3指树,但我还没有对此进行详细分析; 这给出了在末端的摊销的恒定时间添加/删除和对数(在较小的串的块的数量中)连接,而不是相反的绳索.

Answer 1

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

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

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

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

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