Ropes — быстрые строки

Здравствуй, Хабр.
Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксированной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код

string s = "";
for (int i = 0; i < 100000; i++) s += "a";

работает так медленно.

Хочешь выполнять конкатенацию гигантских строк быстро? Не нравится, что строка требует для хранения непрерывную область памяти? Надоело использовать буферы для построения строк?


Структура данных, которая нас спасет, называется Rope string, или «веревочная строка». Принцип ее работы очень прост и до него можно догадаться буквально из интуитивных соображений.

Идея


Пусть нам требуется сложить две строки:

image


Для классических строк мы просто выделим область памяти необходимого размера, в начало её скопируем содержимое первой строки, а в конец — второй:

image


Как уже упоминалось выше, сложность этой операции — O(n).

Но что если мы используем информацию о том что наша результирующая строка — это конкатенация двух исходных? И действительно, создадим объект который предоставляет интерфейс строки и хранит в себе информацию о своих компонентах — исходных строках:

image


Такой способ объединения строк работает за О(1) — нам нужно лишь создать объект-обертку для исходных строк. Так как этот объект — тоже строка, его можно комбинировать с другими строками для получения нужных нам конкатенаций:

image


Уже сейчас очевидно что наша структура — это двоичное дерево поиска, в листьях которого находятся элементарные составляющие нашей строки — группы символов. Так же очевидным становится способ перечисления символов строки — это обход дерева в глубину с последовательным перечислением символов в листьях дерева.

Индексация


Реализуем теперь операцию получения символа строки по его индексу. Для этого введем узлам дерева дополнительную характеристику — вес. Если в узле дерева хранится непосредственно часть символов (узел — лист) то его вес равен количеству этих символов. Иначе, вес узла равен сумме весов его потомков. Иными словами, вес узла — длина строки, которую он представляет.

Нам необходимо получить i-й символ строки, представленной узлом Node. Тогда могут возникнуть два случая:
  • Узел — лист. Тогда он содержит непосредственно данные и нам достаточно вернуть i-й символ «внутренней» строки.
  • Узел — составной. Тогда необходимо узнать в каком потомке узла следует продолжить поиск. Если вес левого потомка больше i — искомый символ является i-м символом левой подстроки, иначе он является (i-w)-м символом правой подстроки, где w — вес левого поддерева.
После этих выкладок рекурсивный вариант алгоритма (как впрочем и итеративный) становится очевидным.

Теперь мы умеем конкатенировать строки за О(1) и индексировать символы в них за О(h) — высоты дерева. Но для полного счастья необходимо научится быстро выполнять операции разбиения на две строки, удаления и вставки подстроки.

Разбиение


Итак, у нас есть строка и нам крайне необходимо разбить её на две подстроки в некоторой её позиции k (числа на схеме — размеры соответствующих деревьев):

image


Место «разрыва» строки всегда находится в одном из листьев дерева. Разобьем этот лист на два новых, содержащих подстроки исходного листа. Причем для этой операции нам не понадобится копировать содержимое листа в новые, просто введем такие характеристики листа как offset и length и сохраним в новых листах указатели на массив символов исходного, изменив лишь смещение и длину:

image


Далее будем расщеплять все узлы на пути от листа к корню, создавая вместо них пары узлов, принадлежащих, соответственно, левой и правой создаваемой подстроке. Причем мы опять же никак не изменяем текущий узел, а лишь создаем вместо него два новых. Это значит операция разделения строки порождает новые подстроки, не затрагивая исходную. После расщепления исходной строки мы получим две новые строки, как на рисунке ниже.

image


Нетрудно заметить что внутренняя структура таких строк не оптимальна — некоторые явно лишние. Однако исправить это досадное упущение легко — достаточно в обоих подстроках пройтись от места разреза к корню, заменяя каждый узел, имеющий ровно одного потомка этим самым потомком. После этого все лишние узлы пропадут и мы получим требуемые подстроки в их конечном виде:

image


Сложность же операции разбиения строк составляет, очевидно, О(h).

Удаление и вставка


Благодаря реализованным уже операциям разбиения и слияния удаление и вставка делаются элементарно — для удаления подстроки достаточно разбить исходную строку в местах начала и окончания удаляемого участка и склеить крайние строки. Для вставки в строки в определенную позицию разобьем в ней исходную строку на две подстроки и склеим их со вставляемой в нужном порядке. Обе операции имеют асимптотику О(h).

Оптимизация


Балансировка

Внимательный читатель, услышав слово «дерево» неизбежно вспомнил бы и два других — «логарифм» и «балансировка». И, как всегда, чтобы достичь заветной логарифмической асимптотики придется все таки балансировать наше дерево. Действительно, при нынешнем способе слияния строк внутренняя структура дерева будет похожа скорее на «лестницу», например такую, как на рисунке ниже:

image


Чтобы этого избежать, будем при каждом объединении строк проверять сбалансированность результата и при необходимости пересобирать все дерево, балансируя его. Хорошее условие сбалансированности — длина строки должна быть не меньше (h+2) — го числа Фибоначчи. Обоснование этого условия а также пара дополнительных модификаций операции склейки были даны Боэмом, Аткинсоном и Плассом в их работе Ropes: an Alternative to Strings

Прямое объединение малых строк

Хранение в памяти узлов дерева вовсе не бесплатно. Если к строке прибавлять по одному символу то мы потратим на хранение информации об узлах дерева на порядок больше памяти, чем на сами символы строки. Во избежание таких ситуаций, а также для уменьшения высоты дерева целесообразно склеивать строки меньше некоторой длины (например, 32) «классическим» способом. Это сильно сэкономит память а также почти не отразится на производительности в целом.

Кэширование последней позиции

В подавляющем числе случаев мы перебираем символы строки последовательно. В нашем случае, если мы запрашиваем символы по индексам i и i+1 очень велика вероятность того что физически они находятся в одном и том же листе дерева. Это значит что при поиске этих символов мы будем повторять один и тот же путь от корня дерева до листа. Очевидное решение этой проблемы — кэширование. Для этого при поиске очередного символа запомним лист в котором он находится и диапазон индексов, которые этот лист в себе содержит. После, при поиске очередного символа сперва будем проверять, лежит ли наш индекс в запомненном диапазоне и, если это так, будем искать его непосредственно в запомненном листе. Можно даже пойти дальше, запоминая не одну последнюю позицию а несколько, например, в циклическом списке.

Вкупе с предыдущей оптимизацией такая техника позволит нам улучшить асимптотику индексации с O(ln(n)) практически до О(1).

Итог


Что же мы в результате получим? Мы получим персистентную реализацию строки, не требующую для своего хранения непрерывной области памяти, с логарифмической асимптотикой вставки, удаления и конкатенации (вместо O(n) у классических строк) и индексацией почти за О(1) — вполне достойный внимания результат.

Ну и напоследок приведу пару полезных ссылок: статья в английской wiki, реализация на Java и описание С++ реализации на сайте SGI.

Use the ropes, Luke!
Поделиться публикацией

Комментарии 36

    0
    Классная штука Rope, да. Только на Хабре уже была, хотя и не так конкретно.
      +3
      И верно. Признаюсь, не нашел этот топик поиском — выдает лишь результаты типа «Cut the rope» и им подобные. В любом случае, подробное рассмотрение структуры думаю не помешает — уж больно мало про неё информации в рунете встечается.
      0
      Ну конечно медленно, если не использовать StringBuilder (в C#, в других яп думаю тоже есть аналоги):

      StringBuilder sb = new StringBuilder(String.empty);
      for (int i = 0; i < 100000; i++) sb.Append("a");
      
        0
        Там как раз в следующем абзаце про такие билдеры написано. Это классический код с объяснением почему нельзя складывать строки именно таким образом.
          +1
          Либо StringBuilder(), либо String.Format()
            –4
            StringBuilder сильно проигрывает Ropes
              0
              У вас и имплементация Rope есть, наверное, для .NET?
                +2
                Даешь бенчмарки!
                Мой прогноз — незначительная разница при построении строки, а при сравнении строк огромный, в несколько порядков отрыв по скорости «обычного порошка» от веревочных строк.
                    0
                    Ожидаемо операции на «результирующей» строке медленнее, в частности и без того медленные регулярные выражения(в 2-10 раз медленннее с#/Java кода habrahabr.ru/post/126954/ — например ) еще в 3-30 раз замедляются.

                    Потестил StringBuilder в С#, Append скейлится линейно, в 10 раз увеличил количество итераций — в 10 раз выросло время, а вот Insert, как и в этих бенчмарках, геометрической прогрессией растет.

                    Возможно имеет смысл конструировать строку этим методом(сделать RopeBuilder какой нибудь), если нужен именно быстрый Insert, а затем так же как и StringBuilder экспортировать в обычную immutable строку, в которой быстрее другие операции.
                  +1
                  А я оставлю пару комментариев Эрика Липперта:
                  1:
                  If you have a scenario where this data structure is more optimal than a string builder, I would be curious to know what it is. It has been my experience that rope data structures are almost never a win over the raw speed of native string or string builder operations in typical cases, so I am very interested to see realistic scenarios where its a win.


                  2:
                  My experience is admittedly limited; I've tried to add rope-style string representations to languages like VBScript and JScript. The number of cases in which we must aggressively reify internal strings into «real» buffer-based strings was so large, and the number of cases where runtime string manipulations actually grew large, complex strings was so small, that the net perf impact was negative. When we built the string logic in JScript.NET we simply used a stringbuilder rather than attempting ropes again.
                  0
                  Интересно, одноимённый класс в Java работает так же, как и в C#?
                    0
                    Ropes выигрывают, если нужно помимо добавления удалять подстроки. Или вставлять в середину/начало. И при этом длины — сотни тысяч символов. Если просто Append, то выигрыша не будет.

                    Тоже встречался с этой структурой данных на ICFPC 2007 и с тех пор больше не видел мест, где её разумно применить. Но знать про неё надо обязательно.
                    +5
                    Мне кажется в этом случае сильно возрастает сложность алгоритма сравнения строк, а соответсвенно и сортировки.
                      +1
                      Да, тоже подумал как такие строки будут в регулярных выражениях обрабатываться. :) Но если такой необходимости нет по задаче — почему нет?
                        0
                        Со сравнением строк все нормально как раз. Сравнение требует последовательного перебора символов который за счет кэширования последнего индекса работает быстро. Порядок сложности не увеличится, увеличится только константа.
                          +2
                          Нет, сложность алгоритма не возрастёт, а останется прежней = o(n), где n — длина строки.
                          0
                          Интересный способ. Возможно, имело-бы смысл использовать nested sets для каких-то операций (веса — похожий прием, но не много не тот). Интуитивно мне кажется что при этом не пострадает скорость операций.
                            0
                            Спасибо за статью (и ссылки), познавательно!

                            ЗЫ: Кмк получаемое дерево все-таки не двоичное дерево поиска, нет?
                              0
                              В строгой формулировке, конечно, нет. Но при индексации символа аналогия с BST наиболее естественная — мы просто ищем другие объекты и правило выбора очередного узла немного модифицировано.
                              0
                              Я в свой проекте на Delphi был вынужден что-то подобное строить. У меня строки доходили до 2 500 000 символов, и беда была не в скорости, а в проблеме сегментации строк. Эта проблема вызывала exception «out of mem».

                              Следует упомянуть, что для Delphi 7 (на других не проверял), такой подход помимо скорости дает и прирост отказоустойчивости.
                                0
                                А есть готовая интерпретация на C++?
                                +1
                                Как тут уже говорили, даешь бенчмарки! :)
                                Ещё интересно, как давно вам приходилось соединять 100 000 строк в цикле?
                                  +2
                                  В 2007 году на ICFP Contest'e, когда спасали Endo
                                  save-endo.cs.uu.nl/
                                  Похожую структуру и применяли.

                                  В практических задачах — вряд ли встретится, но структура хороша, если стоит задача в быстрой генерации больших текстовых данных.
                                  +2
                                  Хотелось бы обозначить область применимости такого хранения.

                                  Первый ваш пример уже вызывает сомнения. Что будет в памяти после
                                  for (int i = 0; i < 100000; i++) s += «a»;
                                  Будет ли это лучше StringBuilder?
                                  +1
                                  Я обычно использую массив строк.

                                  Тем более конкатенация для много-много-много строк требуется как правило один раз (для вывода, например, в поток, в который, кстати можно скормить массив и без конкатенации).
                                    0
                                    Вот такие строки в WebKit используются.
                                    И не всегда это хорошо — ибо эта зараза будет каждый раз при обращении к строке ее собирать.
                                    Иногда крайне не приятно и не понятно получается
                                      –2
                                      А для питона есть адекватная реализация?
                                        0
                                        А минусы то за что?!
                                        +2
                                        Ок, все вроде так офигенно, но… Данный паттерн используется повсеместно и, к сожалению не является серебрянной пулей. Такие решения применяются для более узконаправленных типов данных, что как бы обоснованно (на основе данных профилированния). Но если говорить о строках, ребята настолько разнообразно ими пользуются, что сделать серьезно эффективнее чем strcmp или strcpy (ок, плюсовые варианты) ну нет, чудес не бывает. Либо память, либо такты. Ну либо более специализированные варианты, которые привели выше.
                                          0
                                          Мне понравилось как это реализовано в C# — обе эти операции фактически являются сравнением двух ссылок(strcmp), и присвоением ссылки(strcpy).
                                          С ограничением — сравнение только на предмет равно-не равно, а не для сортировки больше-меньше.
                                          0
                                          если не ошибаюсь, то у libevent буфер-ы так и работают
                                            0
                                            Похожая структура Twine используется в LLVM.

                                            Можно также заметить, что такую структуру данных можно сделать персистентной и использовать для реализации функционала DO-UNDO. Правда, деталей реализации у такого решения довольно много.

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое