WikiDer > Список Conc-tree

Conc-tree list
Не путать с минусы.

А конц-дерево [1][2] это структура данных, которая хранит последовательности элементов и обеспечивает амортизированную О(1) операции добавления и добавления времени, операции вставки и удаления времени O (log n) и объединение времени O (log n). Эта структура данных особенно жизнеспособна для функционального программирования с параллельными задачами и данными и относительно проста в реализации по сравнению с другими структурами данных с аналогичной асимптотической сложностью.[1] Conc-деревья были разработаны для повышения эффективности операций с параллельными данными, которые не требуют последовательного порядка итераций слева направо,[3] и улучшить постоянные коэффициенты в этих операциях, избегая ненужных копий данных.[2] Ортогонально они используются для эффективного агрегирования данных в функциональном стиле. параллельные задачи алгоритмы, как реализация абстракции данных conc-list.[4] Conc-list - это аналог параллельного программирования функциональные минусы, и изначально был введен Язык крепости.

Операции

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

черта Конц[Т] {  def оставили: Конц[Т]  def верно: Конц[Т]  def уровень: Int  def размер: Int}дело учебный класс Пустой[Т] расширяет Конц[Т] {  def уровень = 0  def размер = 0}дело учебный класс Одинокий[Т](элем: Т) расширяет Конц[Т] {  def уровень = 0  def размер = 1}дело учебный класс <>[Т](оставили: Конц[Т], верно: Конц[Т]) расширяет Конц[Т] {  вал уровень = 1 + математика.Максимум(оставили.уровень, верно.уровень)  вал размер = оставили.размер + верно.размер}

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

Затем конкатенация за время O (log n) работает, гарантируя, что разница в уровнях (т. Деревья АВЛ. Этот инвариант гарантирует, что высота дерева (длина самого длинного пути от корня до некоторого листа) всегда будет логарифмической по количеству элементов в дереве. Конкатенация реализована следующим образом:

def concat(хз: Конц[Т], ys: Конц[Т]) {  вал разница = ys.уровень - хз.уровень  если (математика.пресс(разница) <= 1) новый <>(хз, ys)  еще если (разница < -1) {    если (хз.оставили.уровень >= хз.верно.уровень) {      вал номер = concat(хз.верно, ys)      новый <>(хз.оставили, номер)    } еще {      вал нрр = concat(хз.верно.верно, ys)      если (нрр.уровень == хз.уровень - 3) {        вал номер = новый <>(хз.верно.оставили, нрр)        новый <>(хз.оставили, номер)      } еще {        вал нл = новый <>(хз.оставили, хз.верно.оставили)        новый <>(нл, нрр)      }    }  } еще {    // симметричный случай  }}

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

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

2. Дерево ap.right никогда не содержит Добавить узлов (т.е. в нормализованной форме, составленной только из <>, Одинокий и Пустой).

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

Операция добавления конк-дерева

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

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

дело учебный класс Добавить[Т](оставили: Конц[Т], верно: Конц[Т]) расширяет Конц[Т] {  вал уровень = 1 + математика.Максимум(оставили.уровень, верно.уровень)  вал размер = оставили.размер + верно.размер}частный def добавить[Т](хз: Добавить[Т], ys: Конц[Т]) =  если (хз.верно.уровень > ys.уровень) новый Добавить(хз, ys)  еще {    вал zs = новый <>(хз.верно, ys)    хз.оставили матч {      дело WS @ Добавить(_, _) => добавить(WS, zs)      дело WS => если (WS.уровень <= хз.уровень) concat(WS, zs) еще новый Добавить(WS, zs)    }  }}

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

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

Рекомендации

  1. ^ а б c Prokopec, A. et al. (2015) Conc-Trees для функционального и параллельного программирования. Исследовательская статья, 2015 г.
  2. ^ а б c Прокопец А. (2014) Структуры данных и алгоритмы для параллельных вычислений в управляемой среде выполнения. Докторская диссертация, 2014 г.
  3. ^ Стил, Г. (2009) [1] Организация функционального кода для параллельного выполнения; или, foldl and foldr Считается слегка вредным
  4. ^ Сталь, Г. (2011) [2] Как думать о параллельном программировании: нет!
  5. ^ Окасаки, К. (1995)[3] Чисто функциональные списки произвольного доступа
  6. ^ Презентация Conc-Tree
  7. ^ Лекция по параллельному программированию на Conc-Trees на EPFL