Список дерева соглашений
Конк -дерево [1] [2] представляет собой структуру данных , которая хранит последовательности элементов и обеспечивает амортизированные операции добавления и добавления в начало за время O (1), операции вставки и удаления за время O (log n) и конкатенацию за время O (log n). Эта структура данных особенно пригодна для функционального программирования, параллельного задачам и параллельным данным, и ее относительно просто реализовать по сравнению с другими структурами данных с аналогичной асимптотической сложностью. [1] Conc-деревья были разработаны для повышения эффективности операций с параллельными данными, которые не требуют последовательного порядка итераций слева направо. [3] и улучшить постоянные факторы в этих операциях, избегая ненужных копий данных. [2] Ортогонально они используются для эффективного агрегирования данных в функциональных алгоритмах параллельного выполнения задач в качестве реализации абстракции данных conc-list. [4] Conc-list — это аналог функциональных cons-списков параллельного программирования , который изначально был представлен в языке Fortress .
Операции
[ редактировать ]Основная операция с деревом конкатенации — конкатенация. 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]) extends 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 {
// symmetric case
}
}
Добавление (или добавление) с амортизированным временем O(1) достигается за счет введения нового типа внутреннего узла, называемого Append , и использования его для кодирования списка логарифмических деревьев conc-деревьев, строго уменьшающихся по высоте. Каждый Append узел ap должен удовлетворять следующим инвариантам:
1. Уровень ap.left.right всегда строго больше уровня ap.right .
2. Дерево ap.right никогда не содержит узлов Append (т.е. оно находится в нормализованной форме, состоящей только из <> , Single и Empty ).
С этими инвариантами добавление изоморфно сложению двоичных чисел - два соседних дерева одинаковой высоты могут быть связаны за постоянное время с не более чем логарифмическим количеством операций переноса. Это показано на следующем рисунке, где к концентрическому дереву добавляется элемент, соответствующий двоичному числу 11:
Это представление двоичных чисел похоже на представление чисто функциональных списков произвольного доступа Окасаки: [5] с той разницей, что списки произвольного доступа требуют, чтобы все деревья были полными двоичными деревьями , тогда как conc-деревья более расслаблены и требуют только сбалансированных деревьев. Эти более расслабленные инварианты позволяют conc-деревьям сохранять логарифмическую конкатенацию времени, в то время как списки произвольного доступа допускают только конкатенацию O(n).
Ниже приведена реализация метода добавления , который имеет время O(log n) в худшем случае и амортизированное время O(1):
case class Append[T](left: Conc[T], right: Conc[T]) extends 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 никогда не имеет более O(log n) узлов Append и может быть преобразовано обратно в нормализованную форму (использующую только <> , одиночные и пустые узлы) за время O(log n).
Подробную демонстрацию этих операций можно найти на интернет-ресурсах. [6] [7] или в оригинальной бумаге conc-tree. [1] Было показано, что эти базовые операции могут быть расширены для поддержки дека O(1) в наихудшем случае: операций [2] сохраняя при этом ограничение времени конкатенации O(log n) за счет увеличения постоянных коэффициентов всех операций.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Прокопец А. и др. (2015) Conc-деревья для функционального и параллельного программирования . Исследовательская статья, 2015 г.
- ^ Перейти обратно: а б с Прокопец А. (2014) Структуры данных и алгоритмы для параллельных вычислений в управляемой среде выполнения . Докторская диссертация, 2014 г.
- ^ Стил, Г. (2009) [1] Организация функционального кода для параллельного выполнения; или Foldl и Foldr считаются слегка вредными
- ^ Стил, Г. (2011) [2] Как думать о параллельном программировании: нет!
- ^ Окасаки, К. (1995) [3] Чисто функциональные списки произвольного доступа
- ^ Презентация Conc-Tree
- ^ Лекция по параллельному программированию по Conc-Tree в EPFL