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

. Posted in Fox populi - Защита

Связанная структура данных (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.

 

Добавить комментарий


Защитный код
Обновить

Команды

Релиз Firefox 8, Thunderbird 8 и сопутствующих проектов Mozilla
Проект Mozilla официально представил релиз web-браузера Firefox 8.0, первый выпуск в рамках нового сокращенного цикла разработки, которому будет присвоен статус релиза с пр...14-11-2011

Хороший ход

События объекта Database Container
События объекта Database Container (DBC) предоставляют связь между событиями, написанными разработчиком, и активностью базы данных во время работы пользователя, такой как от...14-11-2011

Руководства

О правилах хорошего тона программирования на Лисе
1. Рекомендуется использовать на каждой рабочей станции копию Лисы. 2. Для ускорения необходимо разделить общедоступные базы и библиотеки. 3. Разделить функции для к...12-11-2011