Строковые представления: улучшения по сравнению с веревками?
Я хочу представление для строк с быстрой конкатенацией и операциями редактирования. Я читал статью "Веревки: альтернатива струнам", но были ли какие-либо существенные улучшения в этой области с 1995 года?
РЕДАКТИРОВАТЬ: Одна возможность, которую я рассмотрел ранее, это использовать 2-3 пальца дерева со строками в виде листьев, но я не сделал подробный анализ этого; это дает амортизированное добавление / удаление в постоянное время на концах и логарифмическую (по количеству кусков меньшей строки) конкатенацию, в отличие от канатов.
1 ответ
Это старый вопрос! Интересно, кто-нибудь читает это? Но все же это интригует. В ваших комментариях вы говорите, что ищете:
Более быстрая асимптотика, или постоянные факторы, или меньшее использование памяти
Ну, веревки имеют O(1) вставку и O(n) итерацию. Вы не можете сделать лучше, чем это. Подстроки и индексация, очевидно, будут более дорогостоящими. Но большинство случаев использования для больших документов не требуют редактирования или произвольного доступа. Если вы объединяете только в конце, одномерный вектор / список строк может улучшить постоянную времени вставки. Я использовал это в JavaScript, потому что у него была такая медленная конкатенация строк.
Говорят, что представление памяти менее эффективно, чем использование строк. Я сомневаюсь, что: если вы работаете на языке, который имеет сборщик мусора, веревка позволяет вам использовать один и тот же экземпляр фрагмента строки в нескольких местах. В веревке, которая представляет документ HTML, будет много DIV"S, SPANи LINK элементы. Это может даже произойти автоматически, если предположить, что эти теги являются константами времени компиляции, и вы добавляете их непосредственно в веревку. Даже для таких коротких фраз размер документа на веревке значительно уменьшится до того же порядка, что и исходная строка. Более длинные строки приведут к чистой прибыли.
Если вы также сделаете элемент дерева доступным только для чтения, вы можете создать подполосы (более длинные фразы, выраженные в виде веревок), которые встречаются несколько раз или совместно используются в строках на основе веревки. Недостатком этого совместного использования является то, что такие сегменты осколка веревки нельзя изменить: чтобы отредактировать их или сбалансировать дерево, вам необходимо скопировать граф объектов. Но это не имеет значения, если вы в основном объединяете и повторяете. На веб-сервере вы можете хранить подпункт, который соответствует объявлению таблицы стилей CSS, который используется всеми документами HTML, обслуживаемыми этим сервером.