Представление строк в виде связок символов: Теория и практика

Когда и почему стоит использовать Ropes for Java для манипуляции строками

Системы, которые должны манипулировать большими объемами строковых данных, обычно используют не очень удачные классы String и StringBuilder, которые по умолчанию присутствуют в языке Java. Лучшей альтернативой может оказаться структура данных, основанная на связках (ropes). Эта статья знакомит читателя с Ropes for Java, реализацией связок для платформы Java. В статье рассматриваются также проблемы, связанные с производительностью, и даются рекомендации по эффективному использованию библиотеки.

Амин Ахмад, независимый консультант, Ahmadsoft, LLC

Амин Ахмад (Amin Ahmad) - независимый консультант и президент компании Ahmadsoft, LLC. Он обладает семилетним опытом консультирования по вопросам, связанным c Java, основное внимание уделяет поставке клиентам корпоративных высокопроизводительных Java-систем.



15.03.2010

Связанная структура данных (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. Два типа представления строк
Рисунок 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.

Таблица 1. Предполагаемое время исполнения базовых строковых операций
ОперацияСвязкаКласс String
КонкатенацияO(1)O(n)
Выделение подстрокиO(1)O(1)
Извлечение символаO(log n)O(1)
Извлечение всех символов последовательно (затраты на один символ)O(1)O(1)

Знакомство с Ropes for Java

Проблемы с памятью

Реализации подстрок с постоянным временем доступа в Java-коде могут вызвать проблемы, связанные с использованием памяти, так как ссылки на подстроку мешают освободить память, занимаемую исходной строкой. От этой проблемы страдают объекты и типа Rope, и типа String.

Библиотека Ropes for Java - это высококачественная реализация структуры данных, основанной на связках, для платформы Java (см. раздел Ресурсы). В ней реализовано большое количество оптимизаций, призванных обеспечить отличную общую производительность и использование памяти. В этом разделе показано, как интегрировать связки в Java-приложение, и сравнивается производительность связок с производительностью классов String и StringBuffer.

Реализация Ropes for Java предоставляет клиенту единственный класс: Rope. Объекты класса Rope создаются из любых объектов типа CharSequence с помощью объекта-фабрики (factory builder) Rope.BUILDER.

В листинге 1 показано, как создать экземпляр структуры данных, использующей связки.

Листинг 1. Создание связки
Rope r = Rope.BUILDER.build("Hello World");

Класс Rope предлагает стандартный набор методов для манипуляции, включая методы для:

  • добавления другой последовательности символов;
  • удаления подпоследовательности;
  • вставки другой последовательности символов в связку.

Стоит уточнить, что так же, как и в случае с классом String, каждое из этих изменений возвращает новую связку, а исходная остается неизменной. В листинге 2 приведены примеры некоторых из указанных операций.

Листинг 2. Изменение связки
Rope r = Rope.BUILDER.build("Hello World");
r = r.append("!");  // r теперь содержит "Hello World!"
r = r.delete(0,6);  // r теперь содержит "World!"

Эффективная итерация по связке

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

Листинг 3. Два способа итерации по связке
//первый способ
final Rope r=определенный код для инициализации;
for (int j=0; j<r.length(); ++j) 
    result+=r.charAt(j);

//второй способ
final Rope r=определенный код для инициализации;
for (final char c: r) 
    result+=c;

Как уже упоминалось, извлечение определенного символа с произвольной позиции в связке - это операция типа O(log n). Поэтому, используя метод charAt для каждого символа, первый фрагмент кода в листинге 3 тратит на поиск O(log n) времени n раз. Второй блок, который вместо этого использует Iterator, должен работать быстрее, чем первый. В таблице 2 приведены данные по производительности итерации, выполненной двумя способами по связке длиной 10,690,488. Для сравнения в таблице 2 приведены значения времени для классов String и StringBuffer.

Таблица 2. Данные о производительности выполнения итерации по сложной связке
СпособВремя (наносекунды)
String69,809,420
StringBuffer251,652,393
Rope.charAt79,441,772,895
Rope.iterator1,910,836,551

Связка, использовавшаяся для получения результатов в таблице 2, которые соответствуют ожиданиям, была получена в результате выполнения серии сложных изменений исходной строки. Однако если структура данных была создана непосредственно из последовательности символов, без всяких последующих изменений, то значения производительности удивительным образом меняются. В таблице 3 сравнивается производительность обоих подходов, в этот раз для итерации по связке, состоящей из 182029 символов, которая была непосредственно инициализирована массивом символов, содержащим повесть Рождественская Песнь Чарльза Диккенса в издании от Project Gutenberg.

Таблица 3. Данные о производительности выполнения итерации по связке
СпособВремя (наносекунды)
String602,162
StringBuffer2,259,917
Rope.charAt462,904
Rope.iterator3,466,047

Как эти противоположные значения производительности могут быть объяснены в свете предыдущих теоретических обсуждений? Ключевой фактор - это процесс составления связки; когда связка создается непосредственно из исходного объекта типа CharacterSequence или массива символов, она имеет простую структуру, состоящую из единственной плоской связки. Так как связка не содержит соединительных узлов или узлов с подстроками, поиск символа состоит из прямого делегирования к методу charAt исходной последовательности (в случае с CharacterSequence) или непосредственного поиска в массиве (в случае с массивом). Производительность Rope.charAt для плоской связки соответствует производительности исходной последовательности, которая чаще всего O(1); отсюда и разница в производительности в этих двух случаях.

Можно удивиться, почему charAt более чем в 7 раз быстрее итератора, хотя оба способа обеспечивают время доступа на уровне O(1). Разница возникает из-за того факта, что в языке Java объекты типа Iterator должны возвращать объекты типа Object. Хотя реализация charAt возвращает непосредственно примитивные значения типа char, реализация итератора должна обернуть каждое char-значение в объект Character. Автопреобразование может смягчить неудобства выполнения преобразования вручную, но оно не может устранить потери в производительности.

Наконец, стоит заметить, что производительность Rope.charAt лучше, чем производительность String.charAt. Причина в том, что Rope представляет lazy-подстроки (которые не требуются для текущей операции) в виде отдельного класса, позволяя реализации charAt оставаться простой для обычных связок. Реализация String в Java SE напротив, использует один и тот же класс для предоставления обычных строк и lazy-подстрок, что отчасти усложняет логику charAt и таким образом немного снижает производительность итерации по обычным строкам.

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

Оптимизация вывода с помощью Rope.write

В определенный момент большинство экземпляров связок должно быть записано куда-нибудь, обычно - в поток вывода. К сожалению, для записи произвольного объекта в поток вывода вызывается метод toString этого объекта. Подобный подход к преобразованию требует, чтобы строковое представление всего объекта было создано в памяти, прежде чем первый символ сможет быть записан, что сильно тормозит производительность для больших объектов. Библиотека Ropes for Java была спроектирована с учетом больших объектов, так что она предлагает лучший способ.

Для улучшения производительности класс Rope предлагает способ записи, который принимает объект Writer и спецификацию диапазона символов, и записывает указанный диапазон символов из связки в объект типа Writer. Это экономит время и память, которые бы потребовались для создания объекта типа String из связки, а для больших структур это могут быть крупные значения. В листинге 4 показаны стандартный и усовершенствованный подходы для печати связанной структуры данных в поток вывода.

Листинг 4. Два подхода для вывода Rope в поток
out.write(rope);
rope.write(out);

В таблице 4 приведены сравнительные результаты записи связки длиной 10,690,488 и глубиной 65 в поток вывода, связанный с буфером памяти. В данной таблице показана только экономия по времени, однако экономия памяти, временно выделяемой в адресном пространстве Java-кучи, еще выше.

Таблица 4. Данные по производительности вывода связанной структуры данных
ПодходВремя (наносекунды)
out.write75,136,884
rope.write13,591,023

Сравнение производительности для операций изменения

Теоретически изменения в связках должны выполняться гораздо быстрее, чем подобные действия в строковых представлениях с последовательными символами. С другой стороны, как было показано, итерация по связке может оказаться более медленной. В этом разделе приведены несколько тестов, сравнивающих производительность операций изменения для Ropes for Java и объектов типа String и StringBuffer.

Все тесты были инициализированы электронной книгой Рождественская песнь от Project Gutenberg (182029 байтов), а затем была выполнена серия последовательных изменений. В большинстве случаев число изменений варьировалось от 20 до 480, чтобы представить картину того, насколько хорошо могут масштабироваться структуры данных. (На рисунках 2, 3 и 4 эта величина обозначается как количество операций). Каждый тест выполнялся 7 раз, а затем использовалось среднее значение.

Сравнение операции вставки подстроки

В тесте, оценивающем производительность операции вставки, из результата прошлой итерации случайным образом выбиралась подстрока, а затем вставлялась в произвольную позицию в строке. На рисунке 2 изображены результаты сравнения.

Рисунок 2. Оценка производительности операции вставки подстроки
Рисунок 2. Оценка производительности операции вставки подстроки

Для объектов типа String и StringBuffer количество времени, требующегося для выполнения теста, росло экспоненциально, по мере увеличения количества операций. Связанные структуры данных, напротив, показали отличные результаты.

Сравнение операции добавления подстроки

Тест для операции добавления состоит из добавления случайного диапазона символов из входной строки к ней самой. Этот тест более интересный, так как класс StringBuffer оптимизирован для быстрого выполнения добавления. На рисунке 3 показаны результаты теста.

Рисунок 3. Оценка производительности операции добавления подстроки
Рисунок 3. Оценка производительности операции добавления подстроки

К сожалению, представление на рисунке 3 искажается из-за крайне низкой производительности класса String. Однако, как и ожидалось, у класса StringBuffer отличная производительность.

На рисунке 4 данные класса String удалены, а график отмасштабирован заново, чтобы была возможность более четко сравнить производительность классов Rope и StringBuffer.

Рисунок 4. Результаты теста для операции добавления подстроки, но без данных класса String
Рисунок 4. Результаты теста для операции добавления подстроки, но без данных класса String

Пояснение по вопросу неизменяемости связанной структуры данных

Класс Rope спроектирован неизменяемым, а это значит, что изменяющие функции никогда не модифицируют исходный экземпляр Rope, а вместо этого возвращают модифицированную копию. Неизменяемость предполагает определенные преимущества, главное из которых то, что объекты Rope могут быть без опаски использованы в многопоточном окружении, тем самым в свою очередь значительно упрощается логика приложения.

Библиотека Ropes for Java создает связки из исходной символьной последовательности. CharSequence - это интерфейс, за счет чего достигается высокая степень гибкости: связанные структуры данных могут быть созданы из гетерогенных источников, включая файлы на диске, буферы в памяти и документы, хранящиеся на удаленных серверах. Однако, в отличие от класса String, который является гарантированно неизменяемым, интерфейс CharSequence не налагает подобного ограничения на свои реализации. Поэтому обязанность разработчика приложения убедиться, что исходная последовательность символов, используемая для создания связки, действительно является неизменяемой на всей протяженности жизненного цикла экземпляра связанной структуры данных.

На рисунке 4 показана значительная разница между классами Rope и StringBuffer, которая не была заметна на рисунке 3. Кривая для Rope едва смогла приподняться над осью Х. Однако, что более интересно - это кривая для StringBuffer, она подскакивает и выравнивается, вместо того чтобы плавно расти. В качестве упражнения можно попробовать догадаться, почему это происходит, прежде чем переходить к следующему разделу.

Причина подобного поведения - это то, как класс StringBuffer занимает пространство в памяти. Стоит напомнить, что этот класс для эффективного добавления распределяет дополнительное пространство в конце своего внутреннего массива. Но после того как это пространство оказывается израсходованным, должен быть выделен новый массив, а все данные скопированы в него. Размер нового массива обычно задается как текущая длина, умноженная на некоторый коэффициент. По мере того как количество операций растет, также растет и длина получившегося экземпляра StringBuffer. И когда достигается пороговое значение для изменения размера массива, то время выполнения операции резко увеличивается, пока происходит изменение размера и копирование данных. Затем на графике производительности следует плоский участок (это значит, что затраты времени растут медленно) до тех пор, пока не происходит очередного увеличения количества операций. Так как каждая операция увеличивает общую длину строки приблизительно на такое же количество символов, то отношение между двумя соседними плоскими участками дает представление о коэффициенте, с которым происходит изменение размера массива. Основываясь на результатах, можно сделать точную оценку, что для конкретной реализации StringBuffer этот коэффициент приблизительно равен 1,5.

Выводы по результатам тестов

К этому моменту для иллюстрации различий в производительности классов Rope, String и StringBuffer использовались графики. В таблице 5 представлены расчеты времени по всем тестам для изменяющих операций, выполненных в количестве 480 измерений.

Таблица 5. Среднее время изменения для графика из 480 измерений (дополнительно добавлены результаты теста для операции удаления)
Изменение/структура данныхВремя (наносекунды)
Вставка 
String18,447,562,195
StringBuffer6,540,357,890
Rope31,571,989
Добавление в начало 
String22,730,410,698
StringBuffer6,251,045,63
Rope57,748,641
Добавление в конец 
String23,984,100,264
StringBuffer169,927,944
Rope1,532,799
Удаление (диапазона в 230 символов из исходного текста) 
String162,563,010
StringBuffer10,422,938
Rope865,154

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


Оптимизация производительности регулярных выражений

Регулярные выражения, добавленные в JDK версии 1.4, широко используются во многих приложениях, поэтому крайне важно, чтобы они обеспечивали хорошую производительность при работе со связками. В языке Java регулярные выражения представляются как объекты класса Pattern (шаблон). Для проверки соответствия объекта Pattern диапазону символов в определенном объекте CharSequence экземпляр шаблона используется для создания объекта типа Matcher, передавая объект CharSequence в качестве параметра.

Способность работать с объектами CharSequence обеспечивает регулярным выражениям в Java необычайную гибкость, но имеет один серьезный побочный эффект. Класс CharSequence предлагает единственный метод для доступа к символам: charAt(x). Как упоминалось во вводном разделе, доступ к произвольному символу в связке со многими внутренними узлами - это операция сложности приблизительно O(log n), так что обход по связке - это уже операция сложности O(n log n). Чтобы проиллюстрировать связанную с этим проблему, было выполнено сравнительное тестирование затрат времени, требующихся на поиск всех вхождений шаблона Crachit* в строку длиной 10,690,488. Связанная структура данных глубиной в 65 уровней была создана с помощью серии операций изменения, такой же, как использовалась при сравнительном тестировании операции добавления. В таблице 6 приведены результаты тестирования.

Таблица 6. Время поиска с использованием регулярных выражений
ПодходВремя (наносекунды)
String75,286,078
StringBuffer86,083,830
Rope12,507,367,218
Сбалансированный объект Rope2,628,889,679

Очевидно, что производительность класса Rope при поиске соответствующих фрагментов крайне низкая. Для ясности стоит заметить, что это верно для объекта Rope с множеством внутренних узлов. Для плоской связки производительность будет довольно близка производительности исходного символьного представления. Даже специальная балансировка объекта Rope, после которой поиск соответствующих фрагментов выполняется в 3,5 раза быстрее, не приближает производительность класса Rope к производительности классов String и StringBuffer.

Для улучшения этой ситуации объекты Matcher могут и должны использовать гораздо более быстрое время доступа O(1) по сравнению с временем, обеспечиваемым итераторами для Rope. Чтобы понять, как это работает, сначала необходимо разобраться, каким способом объект Matcher получает доступ к CharSequence.

Наиболее стандартный сценарий для поиска соответствия регулярным выражениям - это начать с определенной позиции в последовательности символов и двигаться вперед, пока все совпадения не будут найдены и не будет достигнут конец последовательности. В этом подходе обнаружитель совпадений в основном движется вперед, часто на один символ в единицу времени. Иногда, однако, обнаружителю совпадений приходится делать шаг назад.

Можно легко модифицировать итератор для класса Rope, отрегулировав его пропускать символы, чтобы перемещаться более чем на один символ в единицу времени. Но двигаться назад более сложно, так как внутри итератор выполняет прямой обход структуры данных в глубину, посещая каждый из ее концевых узлов. Стек обхода не содержит достаточно информации, чтобы вернуться на предыдущий узел, но если запрашиваемое число шагов назад не требует от итератора покинуть текущий узел, то он может обработать запрос. Для наглядности на рисунке 5 показано состояние гипотетического итератора, который может отойти назад на одну, две, три, четыре позиции, но не больше, так как для этого ему придется перейти на уже посещенный узел.

Рисунок 5. Пример состояния итератора
Рисунок 5. Пример состояния итератора

Для обеспечения этой новой возможности метод charAt класса Rope должен быть изменен так, чтобы при первом вызове на указанной позиции создавался итератор. Последующие вызовы должны перемещать итератор вперед или назад на требуемую дистанцию. Если итератор не может переместиться назад на требуемую дистанцию, то выполняется стандартная функция charAt для получения значения символа; желательно, чтобы подобная ситуация возникала как можно реже.

Так как эта оптимизация не всегда применима и требует введения новых полей в классе, то лучше не добавлять ее непосредственно в класс Rope. Вместо этого можно при необходимости снабдить связанную структуру данных этой оптимизацией. Для достижения подобной цели библиотека Ropes for Java включает в класс Rope метод, который возвращает оптимизированный обнаружитель совпадения для установленного шаблона. В листинге 5 приведен пример подобного подхода.

Листинг 5. Поиск совпадений, оптимизированный для регулярных выражений
Pattern p = ...
Matcher m = rope.matcher(p);

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

В таблице 7 приведены результаты сравнения для данного подхода; для ясности в нее включены и результаты прошлого тестирования (из таблицы 6).

Таблица 7. Время поиска с использованием регулярных выражений с помощью метода rope.matcher()
СпособВремя (наносекунды)
String75,286,078
StringBuffer86,083,830
Rope12,507,367,218
Сбалансированный объект Rope2,628,889,679
Rope.matcher246,633,828

Оптимизированные результаты показывают значительное превышение (в 10,6 раза) по сравнению со сбалансированной связкой и приближаются по производительности к классу String. Теперь этот класс обладает производительностью только в 3,2 раза выше, чем связанная структура данных.


Приложения

Когда не стоит использовать связанные структуры данных

Часто в корпоративных Java-приложениях встречается код, похожий на листинг, приведенный ниже:

String x = "<input type='text' name='name' value='" 
             + escapePcData(bean.getName()) + "'>";

Переменная x впоследствии отправляется как HTML-фрагмент в Web-браузер клиента. Имеет ли смысл использовать связки для вычисления значения x вместо StringBuilder, который используется компилятором по умолчанию при генерации исходного кода?

Не стоит - в силу нескольких причин. Во-первых, количество соединяемых данных, скорее всего, невелико, так что использование связки вряд ли повысит производительность, хотя и может улучшить надежность и масштабируемость. (Можно продумать, как поведут себя оба решения, если метод getName неожиданно вернет строку размером в 50 МБ.)

Но для доказательства, предположим, что конкатенируется большое количество фрагментов данных. С учетом того, что производительность класса Rope при добавлении подстрок в общем лучше, чем производительность класса StringBuffer, имеет ли смысл теперь использовать связанную структуру данных? И снова - нет. Когда входные данные необходимо скомпоновать для получения отформатированных выходных данных, наиболее ясный и эффективный способ - это использовать процессор текстовых шаблонов (template engine), такой как StringTemplate и FreeMarker. Этот подход четко разделяет разметку представления от кода, но, кроме того, шаблоны компилируются один раз (часто в Java-байт-код) и затем могут неоднократно использоваться, что и обеспечивает им отличные характеристики производительности.

Второе преимущество использования шаблонов выявляет фундаментальный недостаток, свойственный всем процедурам, которые готовят выходные данные и похожи на приведенный фрагмент кода, включая и те, где используются связки. Выгода состоит в том, что шаблоны могут вычисляться постепенно, и выходные данные могут записываться в объект Writer по мере своей готовности, без необходимости сначала аккумулироваться в памяти. В Java EE-приложении, где объект Writer на самом деле - это буферизованное соединение с Web-браузером клиента, этот подход позволяет выводить данные с постоянным расходом памяти O(1) против использования памяти на уровне O(n) для других подходов. Это огромное преимущество для масштабируемости и надежности приложения, хотя и не всегда заметное при небольшом объеме входных данных или небольшой нагрузке на приложение. (В разделе Ресурсы представлены ссылки на две статьи, посвященные поточной архитектуре - streaming architecture, где более подробно объясняется и измеряется этот подход.)

Теперь, после подробного знакомства с производительностью связанных структур данных, пришло время рассмотреть несколько стандартных способов использования связок вместе с привлекательным, хотя, скорее всего, неуместным использованием связанных структур данных в Java EE-приложении.

Хотя связанные структуры данных могут служить как стандартная замена представлениям строк на основе непрерывного использования памяти, только приложения, которые интенсивно изменяют сложные строки, могут получить существенную прибавку в производительности. Возможно, не станет открытием, что одним из самых первых способов применения связок было представление документов в текстовом редакторе. Не только вставка и удаление текста могут выполняться за постоянный период времени даже для исключительно больших документов, но и неизменяемость связок делает тривиальной реализацию операции undo (отмена последнего действия) - достаточно при каждом изменении просто сохранять ссылку на прошлую версию связки.

Другой, более экзотичный способ использования связанных структур данных - это представлять состояние в виртуальной машине. Например, на чемпионате программирования ICFP 2007 требовалось реализовать виртуальную машину (автомат), состояние которой менялось на каждом проходе и выполнялся миллион проходов для определенных входных данных (см. раздел Ресурсы). В одной реализации на Java скорость виртуальной машины была улучшена на три порядка, с ~50 проходов/сек до более чем 50,000 проходов/сек за счет изменения представления состояния со специализированного объекта StringBuffer на использование объекта Rope.

Направления для последующего изучения

Хотя Ropes for Java - это новая библиотека, ее исходные принципы давно известны, и библиотека продемонстрировала свою способность обеспечить производительность, которую обещают связанные структуры данных. Однако в планах проекта улучшить некоторые аспекты библиотеки в следующих версиях:

  • Обеспечить высокую производительность для реализации некоторых стандартных строковых операций.
  • Написать адаптеры для прозрачной интеграции связанных структур данных в Scala (см. раздел Ресурсы) и других высокофункциональных языков для платформы Java.
  • Повысить качество с помощью автоматизированного тестирования. Ropes for Java тестируется с помощью написанных вручную автоматизированных тестов JUnit и тестов, автоматически сгенерированных с использованием JUnit Factory. Интеграция аннотаций JML (Java Modeling Language - язык Java-моделирования), проверяемых ESC/Java2 (см. раздел Ресурсы) поможет дополнительно улучшить качество кода библиотеки.

Ресурсы

Научиться

  • Ropes: Theory and practice: оригинал статьи (EN).
  • Ropes for Java: Web-сайт библиотеки Ropes for Java.
  • Ropes: an Alternative to Strings (EN) (Hans-J. Boehm, Russ Atkinson, and Michael Plass, Software Practice & Experience, декабрь 1995 г.): подробная статья, знакомящая со связанными структурами данных.
  • Big-O notation: (EN): теория вычислительной сложности использует нотацию большого-O (big-O) для описания того, как размер входных данных влияет на алгоритмы, используемые вычислительными ресурсами.
  • The 10th ICFP Programming Contest: (EN) статья автора на этом чемпионате, демонстрирующая эффективность Ropes for Java.
  • Streaming Architecture и Streaming Presidents (EN) (Amin Ahmad, Ahmadsoft.org): статьи с подробным объяснением и сравнительным тестированием потоковых архитектур.
  • The Scala programming language: функциональное программирование для JVM с помощью языка Scala.(EN)
  • JUnit и JUnitFactory: библиотека Ropes for Java тестируется с помощью JUnit и JUnitFactory.(EN)
  • JML и ESC/Java2: ESC/Java2 - это программный инструмент, который пытается обнаружить стандартные ошибки времени исполнения в Java-программах, использующих аннотации JML. (EN)
  • Safari bookstore: сайт магазина книг по ИТ.(EN)
  • Раздел Технология Java сайта developerWorks: сотни статей обо всех аспектах Java-программирования.

Получить продукты и технологии

  • Ropes for Java: загрузить последнюю версию библиотеки Ropes for Java.(EN)
  • PerformanceTest.java: инструмент, использовавшийся в этой статье для сравнительного тестирования производительности операций, модифицирующих строку. Этот код можно загрузить и выполнить для получения результатов, относящихся именно к вашей платформе. (EN)
  • Скачайте ознакомительные версии продуктов IBM и опробуйте на практике средства для разработки приложений и связующее программное обеспечение DB2®, Lotus®, Rational®, Tivoli® и WebSphere.(EN)

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=474556
ArticleTitle=Представление строк в виде связок символов: Теория и практика
publish-date=03152010