Список Conc-tree

A conc-tree - это структура данных, которая хранит последовательности элементов и обеспечивает амортизированные O (1) операции добавления и добавления по времени, операции вставки и удаления по времени O (log n) и конкатенацию времени O (log n). Эта структура данных особенно жизнеспособна для функционального программирования с параллельными задачами и данными, и относительно проста в реализации по сравнению с другими структурами данных с аналогичной асимптотической сложностью. Conc-деревья были разработаны для повышения эффективности операций с параллельными данными, которые не требуют последовательной итерации слева направо, и для улучшения постоянных коэффициентов в этих операциях, избегая ненужных копий данных. Ортогонально они используются для эффективного агрегирования данных в функциональных параллельных задачах алгоритмах, как реализация абстракции данных conc-list. Conc-list - это аналог функциональных cons-списков в параллельном программировании, и изначально он был введен в языке Fortress.

Основная операция conc-tree - это конкатенация. Conc-деревья работают со следующими основными типами данных:

trait Conc [T] {def left: Conc [T] def right: Conc [T] def level: Int def size: Int} case class Empty [T] extends Conc [T] {def level = 0 def size = 0} case class Single [T] (elem: T) extends Conc [T] {def level = 0 def size = 1} case class <>[T] ( left: Conc [T], right: Conc [T]) расширяет Conc [T] {val level = 1 + math.max (left.level, right.level) val size = left.size + right.size}

Тип <>представляет внутренние узлы и произносится как conc, вдохновленный :: (тип cons ) в функциональных списках, используемых для последовательного программирования.

Конкатенация за время O (log n) затем работает, гарантируя, что разница в уровнях (то есть высотах) между любыми двумя родственными деревьями равна единице или меньше, аналогично инвариантам, поддерживаемым в деревьях AVL. Этот инвариант гарантирует, что высота дерева (длина самого длинного пути от корня до некоторого листа) всегда будет логарифмической по количеству элементов в дереве. Объединение осуществляется следующим образом:

def concat (xs: Conc [T], ys: Conc [T]) {val diff = ys.level - xs.level if (math.abs (diff) <= 1) new <>(xs, ys) else if (diff < -1) { if (xs.left.level>= xs.right.level) {val nr = concat (xs.right, ys) new <>(xs.left, nr)} else {val nrr = concat (xs. right.right, ys) if (nrr.level == xs.level - 3) {val nr = new <>(xs.right.left, nrr) new <>(xs.left, nr)} else { val nl = new <>(xs.left, xs.right.left) new <>(nl, nrr)}}} else {// симметричный регистр}}

Амортизированный O (1) время добавляется (или prepends) достигаются путем введения нового типа внутреннего узла, называемого Append, и его использования для кодирования списка conc-деревьев логарифмической длины, строго уменьшающегося по высоте. Каждый узел AP Append ap должен удовлетворять следующим инвариантам:

1. Уровень ap.left.right всегда строго больше, чем уровень ap.right.

2. Дерево ap.right никогда не содержит никаких дополнительных узлов (т.е. оно находится в нормализованной форме, состоит только из из <>, Single и Empty).

С этими инвариантами муравьи, добавление изоморфно сложению двоичных чисел - два соседних дерева одинаковой высоты могут быть связаны за постоянное время с максимум логарифмическим числом операций переноса. Это проиллюстрировано на следующем рисунке, где элемент добавляется к conc-tree, который соответствует двоичному числу 11:

Это представление двоичного числа похоже на представление чисто функционального случайного списки доступа Окасаки, с той разницей, что списки произвольного доступа требуют, чтобы все деревья были полными бинарными деревьями, тогда как conc-деревья более расслаблены и требуют только сбалансированных деревьев. Эти более расслабленные инварианты позволяют conc-деревьям сохранять логарифмическую конкатенацию времени, в то время как списки произвольного доступа допускают только конкатенацию O (n).

Ниже представлена ​​реализация метода добавления, который является наихудшим временем O (log n) и амортизированным временем O (1):

case class Append [T] (слева: Conc [T], справа: Conc [T]) расширяет Conc [T] {val level = 1 + math.max (left.level, right.level) val size = left.size + right.size} private def append [T] (xs : Append [T], ys: Conc [T]) = if (xs.right.level>ys.level) new Append (xs, ys) else {val zs = new <>(xs.right, ys) xs.left match {case ws @ Append (_, _) =>append (ws, zs) case ws =>if (ws.level <= xs.level) concat(ws, zs) else new Append(ws, zs) } } }

Conc-tree, построенное таким образом, никогда не имеет более чем O (log n) узлов добавления, и может быть преобразован обратно в нормализованную форму (в которой используются только <>, одиночные и пустые узлы) за время O (log n).

Подробную демонстрацию этих операций можно найти в онлайн-ресурсах, или в исходной статье о конкатенации. Было показано, что эти базовые операции могут быть расширены для поддержки наихудших операций O (1) deque, при сохранении ограничения времени конкатенации O (log n), при стоимость увеличения постоянные коэффициенты всех операций.