Связанная структура данных (rope data structure) представляет собой неизменяемую последовательность символов, во многом похожую на String в Java. Но эффективная реализация изменений в связках делает их, в отличие от объектов типа String и их изменяемых собратьев, объектов типа StringBuffer и StringBuilder, идеально подходящими для приложений, которые выполняют большой объем работы по манипуляции строками, особенно в многопоточных средах.
После краткого знакомства со структурами данных, основанных на связках, эта статья знакомит читателя с библиотекой Ropes for Java, реализацией связок для платформы Java. Затем выполняется сравнение классов String, StringBuffer и класса Rope из библиотеки Ropes for Java для Java-платформы; исследуются отдельные проблемы, связанные с производительностью, а завершается статья обсуждением, когда стоит использовать связки в приложении, а когда от них лучше отказаться.
Краткий обзор связанных структур данных
Связка (rope) представляет неизменяемую последовательность символов. Длина (length) — это просто количество символов в последовательности. Большинство реализаций строк хранят все свои символы в памяти последовательно — друг за другом. Главное свойство связки — отсутствие этого ограничения, что позволяет фрагментам связки храниться независимо и дает возможность соединять их при помощи соединительных узлов (concatenation nodes). Подобная архитектура позволяет выполнять соединение строк гораздо быстрее, чем это делается для Java-объектов типа String. Реализация соединения для объектов String требует, чтобы строки, которые нужно объединить, были скопированы в новое место, что является операцией сложности O(n). Связка, с другой стороны, просто создает новый соединительный узел, а это операция сложности O(1). (В разделе Ресурсы приведены ссылки на материалы, объясняющие O-нотацию для определения сложности операций.)
На рисунке 1 приведены два типа реализации строк. Слева символы расположены в последовательных участках памяти. Реализация строк в Java основана на этом принципе. В реализации, изображенной справа, расчлененные строки объединяются с помощью соединительных узлов.
Рисунок 1. Два типа представления строк
Реализации связанных структур данных часто откладывают вычисление сложных операций с подстроками, вводя такой элемент как узел для подстроки (substring node). Использование узлов для подстрок снижает время, затрачиваемое на извлечение подстроки длиной в n символов, с O(n) до O(log n) и часто даже до O(1). Стоит заметить, что Java-объекты типа String, будучи неизменяемыми, также тратят неизменное количество времени на операции с подстроками, а вот объекты типа StringBuilder часто не обладают такими стабильными временными характеристиками.
Плоская связанная структура (flat rope) — связка без конкатенаций или узлов для подстрок — имеет глубину 1. Глубина связки с конкатенациями или подстроками на единицу больше уровня глубины самого отдаленного узла, который в ней содержится.
У связанных структур данных есть два побочных эффекта, которые отсутствуют у реализаций строк, использующих последовательное расположение символов. Первое — это мета-структура из соединительных узлов и узлов для подстрок, по которой необходимо пройти, чтобы найти определенный символ. Более того, эта древовидная мета-структура должна сохраняться как можно более сбалансированной, чтобы минимизировать время обхода, а значит, связанные структуры данных периодически требуют балансировки, чтобы сохранить хорошую производительность считывания. Даже когда связка хорошо сбалансирована, получение символа, стоящего на определенной позиции — это операция сложности O(log n), где n — число соединительных узлов и узлов для подстрок, составляющих структуру данных. (Для удобства длина связки может быть заменена на n, так как длина всегда больше, чем количество соединительных узлов и узлов для подстрок.)
К счастью, балансировка связки выполняется быстро, а определить, когда необходимо выполнить балансировку, можно автоматически, например, сравнив длину связки с ее глубиной. Также в большинстве задач по обработке данных, требуется именно последовательный доступ к символам, хранящимся в связке, а в этом случае итератор по связанной структуре данных может обеспечить совокупную скорость доступа, близкую к O(1).
В таблице 1 сравнивается время выполнения некоторых стандартных строковых операций для связанных структур данных и для объектов типа String.
