В компьютерном программировании , в канате , или шнур , это структура данных , состоящая из небольших строк , которые используются для эффективного хранения и управления очень длинную строку. Например, программа редактирования текста может использовать веревку для представления редактируемого текста, чтобы можно было эффективно выполнять такие операции, как вставка, удаление и произвольный доступ. [1]
Описание
Веревка - это двоичное дерево, в котором каждый лист (конечный узел) содержит строку и длину (также известную как «вес»), а каждый узел, расположенный выше по дереву, содержит сумму длин всех листьев в своем левом поддереве. . Таким образом, узел с двумя дочерними элементами делит всю строку на две части: левое поддерево хранит первую часть строки, правое поддерево хранит вторую часть строки, а вес узла - это длина первой части.
Для операций с веревкой предполагается, что строки, хранящиеся в узлах, являются постоянными неизменяемыми объектами в типичном неразрушающем случае, что допускает некоторое поведение копирования при записи . Конечные узлы обычно реализуются как базовые строки фиксированной длины с прикрепленным счетчиком ссылок для освобождения, когда они больше не нужны, хотя могут использоваться и другие методы сборки мусора .
Операции
В следующих определениях N - длина веревки.
Вставлять
- Определение:
Insert(i, S’)
вставить строку S ', начиная с позиции i в строке s , чтобы сформировать новую строку C 1 ,…, C i , S' , C i + 1 ,…, C m . - Временная сложность:.
Эту операцию можно выполнить с помощью a Split()
и двух Concat()
операций. Стоимость - это сумма трех.
Индекс
- Определение:
Index(i)
вернуть символ в позиции i - Временная сложность:
Чтобы получить i-й символ, мы начинаем рекурсивный поиск с корневого узла:
индекс функции ( узел RopeNode , целое число i ), если узел . вес <= i и существует ( узел . справа ), затем вернуть индекс ( узел . справа , i - узел . вес ) end если существует ( узел . слева ), то вернуть индекс ( узел . слева , i ) конец возвратный узел . строка [ i ] конец
Например, чтобы найти символ на i=10
рис. 2.1, показанный справа, начните с корневого узла (A), найдите, что 22 больше 10 и есть левый дочерний элемент, поэтому перейдите к левому дочернему элементу (B). 9 меньше 10, поэтому вычтите 9 из 10 (оставив i=1
) и перейдите к правому дочернему элементу (D). Затем, поскольку 6 больше 1 и есть левый ребенок, перейдите к левому дочернему элементу (G). 2 больше 1, и есть левый ребенок, поэтому снова перейдите к левому ребенку (J). Наконец, 2 больше 1, но нет левого дочернего элемента, поэтому ответом является символ с индексом 1 в короткой строке «na» (т.е. «a»).
Concat
- Определение:
Concat(S1, S2)
соединить две веревки S 1 и S 2 в одну веревку. - Временная сложность: (или же время для вычисления веса корня)
Объединение может быть выполнено просто путем создания нового корневого узла с left = S1 и right = S2 , что является постоянным временем. Вес родительского узла устанавливается равным длине левого дочернего S 1 , что займет время, если дерево сбалансировано.
Поскольку для большинства операций с канатами требуются сбалансированные деревья, может потребоваться повторная балансировка дерева после объединения.
Расколоть
- Определение:
Split (i, S)
разделить строку S на две новые строки S 1 и S 2 , S 1 = C 1 ,…, C i и S 2 = C i + 1 ,…, C m . - Временная сложность:
Необходимо рассмотреть два случая:
- Точка разделения находится в конце строки (то есть после последнего символа листового узла)
- Точка разделения находится в середине строки.
Второй случай сводится к первому путем разделения строки в точке разделения для создания двух новых листовых узлов, а затем создания нового узла, который является родительским для двух компонентных строк.
Например, чтобы разделить веревку из 22 символов, изображенную на рисунке 2.3, на две равные составные веревки длиной 11, запросите 12-й символ, чтобы найти узел K на нижнем уровне. Удалить связь между K и G . Перейти к родителю G и вычесть вес K от веса D . Переместитесь вверх по дереву и удалите все правые ссылки на поддеревья, покрывающие символы после позиции 11, вычитая вес K из их родительских узлов ( в данном случае только узлов D и A ). И, наконец, создать вновь осиротевших узлы K и H путем конкатенации их вместе и создать новый родительский P с весом , равным длине левого узла K .
Поскольку для большинства операций с канатом требуются сбалансированные деревья, может потребоваться повторная балансировка дерева после разделения.
Удалить
- Определение:
Delete(i, j)
удалить подстроку C i ,…, C i + j - 1 из s, чтобы сформировать новую строку C 1 ,…, C i - 1 , C i + j ,…, C m . - Временная сложность:.
Эту операцию можно выполнить двумя Split()
и одной Concat()
операцией. Сначала разделите веревку на три части, разделив ее на i-й и i + j -й символ соответственно, что позволит выделить строку для удаления в отдельный узел. Затем соедините два других узла.
Отчет
- Определение::
Report(i, j)
вывести строку C i ,…, C i + j - 1 . - Временная сложность:
Чтобы сообщить строку C i ,…, C i + j - 1 , найдите узел u, который содержит C i и weight(u) >= j
, а затем пройдитесь по T, начиная с узла u . Выход С я , ..., С я + J - 1 , выполнив в-порядке обхода из T , начиная с узла ¯u .
Сравнение с монолитными массивами
Операция | Веревка | Нить |
---|---|---|
Индекс [1] | O (журнал n) | О (1) |
Сплит [1] | O (журнал n) | О (1) |
Concatenate (деструктивный) | O (log n) без перебалансировки / O (n) худший случай | На) |
Concatenate (неразрушающий) | На) | На) |
Перебрать каждый символ [1] | На) | На) |
Вставить [2] | O (log n) без перебалансировки / O (n) худший случай | На) |
Добавить [2] | O (log n) без перебалансировки / O (n) худший случай | O (1) амортизировано, O (n) худший случай |
Удалить | O (журнал n) | На) |
Отчет | O (j + журнал n) | O (j) |
Строить | На) | На) |
Преимущества:
- Веревки позволяют намного быстрее вставлять и удалять текст, чем монолитные строковые массивы, операции над которыми имеют временную сложность O (n).
- При работе с веревками не требуется O (n) дополнительной памяти (массивы нуждаются в ней для операций копирования).
- Веревки не требуют больших непрерывных пространств памяти.
- Если используются только неразрушающие версии операций, веревка - это постоянная структура данных . Для примера программы редактирования текста это приводит к простой поддержке нескольких уровней отмены .
Недостатки:
- Большее общее использование пространства, когда он не используется, в основном для хранения родительских узлов. Существует компромисс между тем, какая часть общей памяти является такими накладными расходами, и продолжительностью обработки фрагментов данных в виде строк. Строки на приведенных выше примерах нереально короткие для современных архитектур. Накладные расходы всегда равны O (n), но константу можно сделать сколь угодно малой.
- Увеличение времени для управления дополнительным хранилищем
- Повышенная сложность исходного кода; больший риск ошибок
В этой таблице сравниваются алгоритмические характеристики реализаций струн и веревок, а не их исходная скорость . Строки на основе массивов имеют меньшие накладные расходы, поэтому (например) операции конкатенации и разделения выполняются быстрее для небольших наборов данных. Однако, когда строки на основе массивов используются для более длинных строк, временная сложность и использование памяти для вставки и удаления символов становится неприемлемо большим. Напротив, веревочная структура данных имеет стабильную производительность независимо от размера данных. Кроме того, сложность пространства для веревок и массивов равна O (n). Таким образом, связки предпочтительнее, когда данные большие и часто модифицируются.
Смотрите также
- Среда программирования Cedar , в которой канаты использовались «почти с самого начала» [1]
- Model T анфилады , аналогичную структуру данных с начала 1970 - х годов.
- Промежуточный буфер , структура данных, обычно используемая в текстовых редакторах, которая позволяет выполнять эффективные операции вставки и удаления, сгруппированные в одном месте.
- Таблица частей , другая структура данных, обычно используемая в текстовых редакторах
Рекомендации
- ^ a b c d e Бём, Ганс-Дж; Аткинсон, Расс; Пласс, Майкл (декабрь 1995). «Канаты: альтернатива струнам» ( PDF ) . Программное обеспечение - практика и опыт . Нью-Йорк, штат Нью-Йорк, США: John Wiley & Sons, Inc. 25 (12): 1315–1330. DOI : 10.1002 / spe.4380251203 . Архивировано 8 марта 2020 года.
- ^ а б «Обзор реализации каната» . www.sgi.com . Проверено 1 марта 2017 .
Внешние ссылки
- Реализация веревок "C cords" в библиотеке Boehm Garbage Collector.
- Спецификация SGI C ++ для веревок (поддерживается STLPort и libstdc ++ )
- Веревки для C #
- веревки для Common Lisp
- Веревки для Явы
- Веревки для JavaScript
- Веревки для лимбо
- веревки для Нима
- Веревки для OCaml
- пиропы для Python
- Веревки для Smalltalk
- SwiftRope для Swift
- "Ropey" для Rust