Строковые представления: улучшения над канатами?

Question

Я хочу представление для строк с быстрым конкатенационным и редактированием операций. Я прочитал статью "Ropes: an Alternative to Strings", но были ли какие-либо существенные улучшения в этой области с 1995 года?

EDIT: Одна из возможностей, которую я рассмотрел ранее, использует 2-3 finger tree со строками в виде листьев, но я не сделал подробного анализа этого; это дает амортизированное добавление/удаление константы по концам и логарифмическое (в количестве кусков меньшей струны) конкатенацию, в отличие от наоборот для веревок.

Answer 1

Это старый вопрос! Интересно, читает ли кто-нибудь это. Но все же это интригует. В комментариях, вы говорите, вы ищете:

Faster асимптотика или постоянные факторы или меньшее использование памяти

Ну, канаты O (1) вставка, и O (п) итерация. Вы не можете сделать лучше. Подстроки и индексирование, очевидно, будут более дорогостоящими. Но большинство случаев использования для больших документов не требуют редактирования или произвольного доступа. Если вы только конкатенируете в конце, 1D вектор/список строк может улучшить постоянную времени вставки. Я использовал это в JavaScript, потому что у него была такая медленная конкатенация строк.

Говорят, что представление памяти менее эффективно, чем использование строк. Я сомневаюсь, что: если вы работаете на языке с сборкой мусора, веревка позволяет использовать один и тот же экземпляр фрагмента строки в нескольких местах. В канате, представляющем HTML-документ, будет много элементов DIV, SPAN и LINK. Это может произойти автоматически, предполагая, что эти теги являются константами времени компиляции, и вы добавляете их непосредственно к веревке. Даже для таких коротких фраз документ веревки значительно уменьшится в размерах до того же порядка величины, что и исходная строка. Более длинные строки будут давать чистый выигрыш.

Если вы также делаете дерево elemenst только для чтения, вы можете создавать субтропы (более длинные фразы, выраженные в виде веревок), которые встречаются несколько раз или совместно используются в строках на основе веревки. Недостатком этого совместного использования является то, что такие участки гардинной веревки не могут быть изменены: редактировать их или балансировать дерево, необходимое для копирования графа объектов. Но это не имеет значения, если вы в основном конкатенируете и повторяете. На веб-сервере вы можете сохранить подпрограмму, которая отображает объявление стилей CSS, которое будет использоваться во всех HTML-документах, обслуживаемых этим сервером.