字符串表示法：對繩索的改進？

Question

我想要一個具有快速拼接和編輯操作的字符串表示。我已閱讀"Ropes: an Alternative to Strings"這篇論文，但自1995年以來，這方面有什麼重大改進？

編輯：我以前考慮過的一種可能性是使用字符串作爲葉子的2-3 finger tree，但我沒有對此做過詳細分析;這會在末端和對數（在較小字符串的塊的數量上）級聯中給出分期付款的恆定時間添加/刪除，而繩索反之亦然。

Answer 1

這是一個老問題！我想知道有沒有人讀這個。但它仍然很吸引人。 在你的意見，你說你看：

更快的漸進性，或恆定 因素，或更少的內存使用

好，繩子有O（1）插入，以及O（N）迭代。你做不到比這更好。子串和索引顯然會更昂貴。但大多數大型文檔的使用情況不需要編輯或隨機訪問。如果只在最後連接，則一維矢量/字符串列表可以改善插入時間常數。我曾經在JavaScript中使用它，因爲它具有如此慢的字符串聯合。

據說內存表示比使用字符串效率低。 我懷疑：如果你使用垃圾收集的語言工作，繩索允許你在多個地方使用相同的字符串片段實例。在代表HTML文檔的繩索中，將會有許多DIV，SPAN和LINK元素。這可能會自動發生，假設這些標籤是編譯時間常量，並將它們直接添加到繩索中。即使對於這樣短的短語，繩索文檔的尺寸也會顯着減小，達到與原始字符串相同的數量級。更長的琴絃會產生淨收益。

如果您還讓樹元素只讀，您可以創建多次出現的子句（用繩索表示的較長的短語），或者在基於繩索的字符串之間共享。這種共享的缺點是這些碎片繩段不能改變：編輯它們，或平衡你需要複製對象圖形的樹。但是，如果你主要連接並迭代，那並不重要。在Web服務器中，您可以保留一個子表格，該表格重複了在該服務器提供的所有HTML文檔之間共享的CSS樣式表聲明。