Сокращение дерева

В информатике , сжатие параллельного дерева является широко применимым методом параллельного решения большого количества задач, связанных с деревьями и используется в качестве метода разработки алгоритмов для разработки большого количества алгоритмов на параллельных графах . Параллельное сокращение дерева было предложено Гэри Л. Миллером и Джоном Х. Рейфом . и впоследствии был модифицирован для повышения эффективности X. He и Y. Yesha, Гиллель Газит, Гэри Л. Миллер и Шан-Хуа Тэн и многие другие.

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

На основе исследований и работ по сокращению параллельных деревьев были предложены различные алгоритмы, направленные на повышение эффективности или простоты этой темы. В данной статье основное внимание уделяется конкретному решению, которое является вариантом алгоритма Миллера и Рейфа, и его применению.

Введение

За последние несколько десятилетий были проведены значительные исследования по созданию новых параллельных алгоритмов для различных задач с целью разработки высокопараллельных ( полилогарифмическая глубина ) и эффективных с точки зрения работы (линейных во времени последовательного выполнения) алгоритмов. Для некоторых проблем дерево оказывается хорошим решением. Решая эти проблемы, мы иногда можем добиться большего параллелизма, просто представляя нашу проблему в виде дерева.

Учитывая общее определение дерева, существует корневая вершина и несколько дочерних вершин, прикрепленных к корню. А дочерние вершины сами могут иметь дочерних вершин и т. д. и т. п. В конце концов пути сводятся к листьям, которые определяются как конечные точки дерева. Затем, основываясь на этом общем дереве, мы можем далее придумать некоторые особые случаи: (1) сбалансированное двоичное дерево ; (2) связанный список . Сбалансированное бинарное дерево имеет ровно две ветви для каждой вершины, за исключением листьев. Это дает оценку O(log n) глубины дерева. Связанный список также является деревом, в котором каждая вершина имеет только одного дочернего элемента. Мы также можем достичь глубины O(log n), используя нарушение симметрии .

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

Немного подумав, мы можем найти некоторые исключительные случаи, когда сумма префиксов становится неэффективной или неэффективной. Рассмотрим пример умножения, когда набор значений включает 0. Или есть некоторые часто используемые операции max() и min(), которые не имеют обратных значений . Цель состоит в том, чтобы найти алгоритм, который работает на всех деревьях с ожидаемой работой O(n) и глубиной O(log n). В следующих разделах для достижения этой цели будет предложен алгоритм Rake/Compress.

Определения

Рис. 1: Работа граблей

Рис. 2: Операция сжатия

Прежде чем перейти к самому алгоритму, мы сначала рассмотрим несколько терминов, которые будут использоваться позже.

• Грабли – Шаг Rake соединяет каждый левый лист двоичных узлов с родительским. Под объединением мы подразумеваем, что он подвергается функциональному процессу, который выполняет операцию, которую мы хотим выполнить. Пример рейка приведен на рисунке 1.
• Компресс – Шаг сжатия на самом деле представляет собой последовательность нескольких событий: (1) Найти независимый набор унарных узлов. (Независимость здесь определяется таким образом, что никакие два узла не являются соседями, что означает отсутствие отношения родитель-потомок) (2) Соедините каждый узел в независимом наборе с его дочерним элементом (обратите внимание, что независимый набор не уникален). Пример сжатия приведен на рисунке 2.

А для решения актуальных задач с использованием сжатия дерева алгоритм имеет структуру:

Repeat until tree becomes a unary node{    Rake;    Compress;}

Анализ

На данный момент предположим, что все узлы имеют менее трех дочерних узлов, а именно двоичных. Вообще говоря, пока степень ограничена, границы будут сохраняться. Но мы для простоты разберем бинарный случай. В двух «вырожденных» случаях, перечисленных выше, грабли — лучший инструмент для работы со сбалансированными двоичными деревьями, а сжатие — лучший инструмент для связанных списков. Однако для произвольных деревьев потребуется комбинация этих операций. Используя эту комбинацию, мы утверждаем теорему о том, что

• Теорема : После ожидаемых шагов очистки и сжатия O(log n) дерево сводится к одному узлу.

Теперь перефразируем алгоритм сжатия дерева следующим образом:

• Входные данные: бинарное дерево с корнем в r.
• Выход: один узел
• Операция: последовательность этапов сжатия, каждый из которых состоит из операции наклона и операции сжатия (в любом порядке). Операция rake удаляет все листовые узлы параллельно. Операция сжатия находит независимый набор унарных узлов и объединяет выбранные узлы.

Чтобы приблизиться к теореме, мы сначала взглянем на свойство двоичного дерева. Учитывая двоичное дерево T, мы можем разделить узлы T на 3 группы: ⁠ $T_{0}$⁠ содержит все листовые узлы, ⁠ $T_{1}$⁠ содержит все узлы с 1 дочерним элементом, а ⁠ $T_{2}$⁠ содержит все узлы с двумя дочерними узлами. Это легко увидеть: $V(T)=T_{0}\cup T_{1}\cup T_{2}$. Теперь мы предлагаем:

• Требовать: $|T_{0}|=|T_{2}|+1$

Это утверждение можно доказать сильной индукцией по числу узлов. Легко видеть, что базовый случай n=1 тривиально выполняется. Далее мы предполагаем, что это утверждение также справедливо для любого дерева с не более чем n узлами. Тогда для дерева с n+1 узлами с корнем в r возможны два случая:

1. Если r имеет только одно поддерево, рассмотрим поддерево r. Мы знаем, что поддерево имеет такое же количество двоичных узлов и такое же количество листовых узлов, как и все дерево. Это верно, поскольку корень является унарным узлом. А исходя из предыдущего предположения, унарный узел тоже не меняется ⁠ $T_{0}$⁠ или ⁠ $T_{2}$⁠ .
2. Если r имеет два поддерева, мы определяем ⁠ $T_{0}^{L},T_{2}^{L}$⁠ быть листовыми узлами и двоичными узлами в левом поддереве соответственно. Аналогично определяем тот же ⁠ $T_{0}^{R},T_{2}^{R}$⁠ для правого поддерева. Из предыдущего есть $|T_{0}^{L}|=|T_{2}^{L}|+1$ и $|T_{0}^{R}|=|T_{2}^{R}|+1$. Также мы знаем, что T имеет $|T_{0}^{L}|+|T_{0}^{R}|$ листовые узлы и $|T_{2}^{L}|+|T_{2}^{R}|+1$ бинарные узлы. Таким образом, мы можем вывести:

$|T_{0}^{L}|+|T_{0}^{R}|=|T_{2}^{L}|+1+|T_{2}^{R}|+1=(|T_{2}^{L}|+|T_{2}^{R}|+1)+1$

что доказывает утверждение.

Следуя утверждению, мы затем доказываем лемму, которая приводит нас к теореме.

• Лемма: количество узлов после шага сокращения уменьшается на постоянный коэффициент ожидания.

Предположим, что количество узлов до сжатия равно m, а после сжатия m'. По определению, операция rake удаляет все ⁠ $T_{0}$⁠ и операция сжатия удаляет не менее 1/4 ⁠ $T_{1}$⁠ в ожидании. Все ⁠ $T_{2}$⁠ остается. Таким образом, мы можем увидеть:

$E[m']\leq |T_{2}|+{\tfrac {3}{4}}*|T_{1}|\leq {\tfrac {3}{4}}+{\tfrac {3}{4}}*|T_{1}|+{\tfrac {3}{2}}*|T_{2}|={\tfrac {3}{4}}(1+|T_{1}|+2*|T_{2}|)={\tfrac {3}{4}}(|T_{0}|+|T_{1}|+|T_{2}|)={\tfrac {3}{4}}m$

Наконец, на основе этой леммы можно заключить, что если узлы уменьшаются в постоянном коэффициенте на каждой итерации, то после ⁠ $O(\log n)$⁠ , останется только один узел.

Приложения

Оценка выражения

Чтобы вычислить выражение, заданное в виде двоичного дерева (эта проблема также известна как дерево двоичных выражений ), считай, что:Арифметическое выражение — это дерево, листья которого содержат значения из некоторого домена, а каждая внутренняя вершина имеет двух дочерних элементов и метку из {+, x, %}. И далее предположим, что эти бинарные операции можно выполнять за постоянное время.

Теперь мы покажем, что оценку можно выполнить с помощью параллельного сжатия дерева.

• Шаг 1. Назначьте выражения каждому узлу. Выражение листа — это просто значение, которое он содержит. Обозначьте операторы L + R, L − R или L × R, где L и R — значения выражений в левом и правом поддеревьях соответственно.
• Шаг 2. Когда левый (правый) дочерний элемент с 0 дочерними элементами объединяется в оператор, замените L (R) значением дочернего элемента.
• Шаг 3. Когда у узла есть 1 дочерний элемент, у него есть выражение, которое является функцией одной переменной. Когда левый (правый) дочерний элемент с 1 дочерним элементом объединяется с оператором, замените L (R) выражением и при необходимости измените переменную в выражении на L (R).

В узле с 2 дочерними операндами выражения являются f(L) и g(R), где f и g — линейные функции, а в узле с 1 дочерним элементом выражение — h(x), где h — линейная функция и x — это либо L, либо R. Мы докажем этот инвариант по индукции. Вначале инвариант явно выполняется. Существует три типа слияний, которые приводят к не полностью вычисленному выражению. (1) Узел с 1 дочерним элементом объединяется с узлом с 2 дочерними элементами. (2) Лист объединяется в узел с двумя дочерними элементами. (3) Узел с 1 дочерним элементом объединяется с узлом с 1 дочерним элементом. Все три типа слияний не меняют инвариант. Следовательно, каждое слияние просто оценивает или составляет линейные функции, что занимает постоянное время.

Внешние ссылки

• 6.851: Расширенные структуры данных , профессор Эрик Демейн