Параллельное построение двоичного дерева на основе сортировки

Бесплатный доступ

Введение. Разработаны алгоритмы параллельного построения двоичного дерева. Алгоритмы выполнены на основе сортировки и описаны в конструктивной форме. Для множества из N элементов временная сложность имеет оценки T(R) = O(1) и T(R) = O(log2 N), где число процессоров R = (N2-N)/2. Дерево строится со свойством единственности. Алгоритмы инвариантны относительно вида входной последовательности. Целью работы являлась разработка и исследование способов ускорения процесса организации и преобразований древовидных структур данных на основе алгоритмов устойчивой максимально параллельной сортировки для их применения к базовым операциям информационного поиска в базах данных.Материалы и методы. Взаимно однозначное соответствие множества входных элементов и построенного для него двоичного дерева устанавливается при помощи устойчивой адресной сортировки. Сортировка обладает максимальным параллелизмом, в операторной форме устанавливает взаимно однозначное соответствие входных и выходных индексов...

Еще

Структуры данных, алгоритмы обработки данных, двоичное дерево, алгоритмы параллельной сортировки

Короткий адрес: https://sciup.org/142217059

IDR: 142217059   |   DOI: 10.23947/1992-5980-2018-18-4-449-454

Текст научной статьи Параллельное построение двоичного дерева на основе сортировки

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

Метод параллельного построения двоичного дерева. Для массива A = ( a0, a 1, ..., a n _1 ) матрица сравнений строится в соответствии с [1, 2]. Элемент aij этой матрицы определяется как

+,

a ij

a j a i a j = a i a j < a i

где i , j = 1, 2, ..., n .

Элемент a j в отсортированном массиве C = ( с 0,

n c1, ..., cn_1) получает номер k = ^aij , где aij >0

i = 1

при i j , a ij 0 при i j . Все сравнения взаимно независимы, сортировка устойчива и максимально парал-

( N2 — N лельна с оценкой временной сложности TI------

= O ( 1 ) . На этой основе можно выполнить параллельное

построение двоичного дерева [3, 4]. Пусть дано множество из N элементов Xi , все элементы которого представлены в виде одномерного массива. На множестве предполагается заданным отношение порядка <. Требуется преобразовать массив в двоичное дерево. Для этого выполняется описанная сортировка массива. Середин-

ный элемент массива C имеет индекс j ср

и принимается за корень дерева [3]. Все элементы массива C

слева от C образуют левое поддерево (левый подмассив). Элементы справа от C образуют правое поддере-ср                                                                                                                                                                          ср во (правый подмассив). Левый подмассив интерпретируется как новый массив. В нем аналогично находится

. При этом Cj    — ближайший слева потомок корня дерева

индекс корня j ср. Лев. 1/2 =

N

1

C . Все элементы подмассива слева от C      не превосходят C     , все элементы подмассива справа не jср                                                                                                       jср. лев. 1/2                                                  jср. лев. 1/2

меньше      Cj    .    Одновременно    определяется    индекс    корня    правого    подмассива

j ср. прав. 1/2

. При этом C jср. прав. 1/2

— ближайший справа потомок корня дерева

C . Процесс рекуррентно возобновляется в каждой паре прилегающих подмассивов: ср

ср. лев. 1/2 i , 1

j                   1

J ср. лев. 1/2

J ср. лев. 1/2 i ,2      сер. лев. 1/2 i 1 ""*""

^ер. прав.1/2 i ,1     ^ер. прав. 1/2 i 1

ер.прав.1/2 i ,2     ^ер. прав. 1/2 i 1 "*"

j          — 1

ер. лев. 1/2 1

ер. прав. 1/2 i 1        ер. прав. 1/2 i 2

ер.прав. 1/2 i 1        ер. прав. 1/2 i 2

i = 1, 2

, log2 N .

В результате за время O ( 1 ) формируютея вее элементы нижеетоящего уровня двоичного дерева. Процесс можно продолжать до исчерпания log2 N уровней двоичного дерева.

Число шагов алгоритма построения двоичного дерева в параллельной форме складывается из шага сортировки и последовательности шагов при расчете индексов корней поддеревьев. Отсюда T ( R ) = log2 N Т + т = O ( log2 N ) , где R — чиело процеееорных элементов, т — время бинарного еравнения, Т — время вычисления одного индекса корня. Число процессоров R определяется максимально параллельной сортировкой N входных элементов, а затем вычислением индексов с удвоением по числу уровней дерева. При вычиелении индекеов это чиело не превзойдет 2log 2 N 1 = N /2, поэтому чиела процеееоров, задейетвованных

N2 — N сортировкой, достаточно. В итоге R не превзойдет         [3]. Окончательно, временная сложность парал лельного алгоритма построения двоичного дерева составит

T ( N 2 N ] = O ( log 2 N ) .

Пример      [3].     Двоичное     дерево     для     массива     из     15      элементов

X = ( 14, 9, 24, 7,11, 20, 28, 3, 8,10,13, 17, 21, 25, 30 ) етроитея еледующим образом.

Результатом сортировки является массив

С = ( 3, 7, 8, 9,10,11,13,14,17, 20, 21, 24, 25, 28, 30 ) .

Корнем двоичного дерева является серединный элемент массива C : j

= 8,

С 8 = 14. Левый

подмассив имеет корень

j ср. лев. 1/2

= 4, элемент С 4 = 9 — корень левого поддерева, который являетея

ближайшим слева  потомком  серединного элемента C . Правый подмассив имеет корень ср

j ер. прав. 1/2    8 +

8 1

= 12 , элемент С 12 = 24 являетея корнем правого поддерева и ближайшим еправа потом-

ком корня C j ср . Далее, j ср.лев.1/4,1

= 2 , элемент С2 = 7 — корень поддерева елева и являетея ближай-

шим слева  потомком  корня поддерева   Cj    . В правом поддереве корень имеет номер

j ер. лев. 1/4,2    4 +

4 1

= 6, элемент С 6 = 11 — корень правого поддерева и ближайший еправа потомок

Информатика, вычислительная техника и управление

C,    . Аналогично, слева от C,     определяется корень j         = 12 - jср. лев.1/2                                                   jср. прав.1/2                                               ср. прав. 1/4,1

12 - 8 - 1

= 10, элемент C 10 = 20

— корень левого от него поддерева и ближайший слева потомок корня поддерева Cj     . Для смежного с рас- смотренным правым подмассивом корень имеет номер

j ср. прав. 1/4,2    12 +

12 - 8 - 1

= 14, элемент

C 14 = 28 —

ближайший справа потомок Cj     и корень правого поддерева. Нижний уровень дерева сформируют потом ки, оставшиеся слева и справа от каждого из 4 идентифицированных корней (рис. 1):

0 уровень

C 8

j ср

= 8

= 14

i        = 4

ср. лев. 1/2

1 уровень jср. лев. 1/4,1

2 уровень      C 2

C 4 = 9

j ср. прав. 1/2

C 12 = 24

= 12

= 2

C 3 = 8

C 5 = 10

j ср. лев. 1/8,2     3

j ср. лев. 1/4,2     6

j ср. прав. 1/4,1

= 10

i          = 14

ср. прав. 1/4, 2

C 6 =11

C 7 = 13

C 10 =

C 9 = 17

C 14 = 28

j ср. лев. 1/8,3     5

j ср. лев. 1/8, 4

= 7

i „ = 9 j ср. прав. 1/8,1

C 11 j ср. прав

=21        C 13 = 25       C 15 = 30

.1/8,2    33      j ср. прав. 1/8,3    ^3 j ср. прав. 1/8,4

Рис. 1. Пример построения двоичного дерева на основе сортировки

Имеет место

Теорема 1 [3]. Для одномерного массива из N элементов двоичное дерево может быть построено па-

( N 2 )

раллельно при помощи сортировки с временной сложностью T I -^- I = O ( log 2 N ) .

Использованная сортировка устойчива, как следствие двоичное дерево строится с единственностью. Индексы всех серединных элементов (всех корней поддеревьев) можно идентифицировать [3]. С учетом этой модификации все индексы из предыдущего примера для N значений поддеревьев можно вычислить синхронно и взаимно независимо. Это приводит к единичной оценке времени построения двоичного дерева. Для каждого конкретного N все значения индексов узлов дерева можно вычислить априори и хранить в памяти компьютера. С их помощью отсортированные элементы можно синхронно и взаимно независимо адресовать по всем узлам дерева. Формулы вычисления индексов узлов зависят только от общего количества N входных элементов и никак не зависят от их взаимного расположения после устойчивой сортировки. Для упрощения адресации памяти вычисленные индексы можно упорядочить на каждом уровне и расположить по возрастанию уровней. Тогда по ключу N считывается вся совокупность упорядоченных индексов узлов. Остается только по счита-ным адресам расположить отсортированные элементы дерева. На основании изложенного имеет место

Теорема 2. Для одномерного массива из N элементов двоичное дерево может быть построено парал-

( N 2 )

лельно при помощи сортировки и априорного вычисления индексов с временной сложностью T I -^- I = O ( 1 ) .

Ниже представлена единая таблица, содержащая формальные оценки временной сложности последовательных и параллельных алгоритмов построения двоичного дерева в сопоставлении с предложенными алгоритмами.

Сравнительные оценки временной сложности последовательных и параллельных алгоритмов построения двоичного дерева в сопоставлении с предложенными алгоритмами

Таблица 1

Алгоритм построения двоичного дерева

Временная сложность алгоритма

Ускорение при использовании алгоритма с единичной временной сложностью

Ускорение при использовании алгоритма с логарифмической временной сложностью

Algorithm of Lagana A., Kumar V. (2004) [5]

T = O f N k + 1 ) [5]

(   k + 1

T = O - I T *           1

V     J

T=O

(     k + 1

N-k— = O ( N ln2 ) log2 N      V      ’

V       J

Algorithm of Chalermsook P.

(2015) [6]

T = O ( N 2 ) [6]

T = O ( N 1)

T - o :

—— ) = O ( N 2ln2 ) log2 N J    v       ’

Полиномиальный алгоритм (2016) [7]

T = O ( N 3) [7]

T = o ( N ’)

T - -i:

——1 = On 3ln2) log2 N J    v       7

Алгоритм «left child – right sibling» (2014) [8]

T = O ( N 2 ) [8]

- = ° ( N 1 )

T - - I:

—N 1 = O2ln2) log2N J    v       7

Pattern-based algorithm (1991) [9]

T = O (| D log2 D )

[9]

OD f 1 D log 2 D )

T *      V      1      7

L = O f 1 D log 2 D ) T    V log 2 N J

Представленный алгоритм с логарифмической оценкой временной сложности (2015) [3]

T = O ( log 2 N ) [3]

Представленный алгоритм с единичной оценкой временной сложности (2015) [3]

T * = O ( 1 )

В таблице 1 D — мощность словаря шаблонов, N — число входных элементов двоичного дерева, k — размерность пространства, в котором выполняется сортировка.

Из таблицы видно, что предложенный алгоритм с логарифмической оценкой временной сложности абстрактно улучшает оценки известных алгоритмов. Минимальное ускорение достигается по отношению к алгоритму из [5]: ^ = O(N2 ln2), или, ^ = O(N), а максимальное ускорение достигается относительно полиноми-T J N3 1 T ального алгоритма из [7]: — = O         или — = O (N3). В случае с предложенным алгоритмом с единичной

T    Vlog2 NJ T оценкой временной сложности также улучшаются оценки известных алгоритмов. В данном случае минималь-T ное ускорение достигается относительно алгоритма из [5]: — = O(N), максимальное ускорение достигается относительно полиномиального алгоритма из [7]: ^* = O (N3).

Заключение. Разработанные алгоритмы отличаются от известных способов [5–7, 10, 11] построения двоичного дерева тем, что используется максимально параллельная сортировка для вычисления индексов узлов. При этом для построения дерева либо затрачивается логарифмическое число шагов, либо вообще не затрачивается дополнительное время, если значения индексов априори рассчитаны для всех значений N в некоторых реальных границах и хранятся в памяти компьютера. Предложенный параллельный алгоритм построения двоичного дерева может использоваться с целью организации эффективных способов динамической обработки баз данных.

Информатика, вычислительная техника и управление

Список литературы Параллельное построение двоичного дерева на основе сортировки

  • Ромм, Я. Е. Сравнение слов с единичной временной сложностью/Я. Е. Ромм, Д. А. Чабанюк//Известия Южного федер. ун-та. Технические науки. -2014. -№7 (156). -С. 230-238.
  • Ромм, Я. Е. Параллельная сортировка слиянием по матрицам сравнений. II/Я. Е. Ромм//Кибернетика и системный анализ. -1995. -№ 4. -С. 13-37.
  • Ромм, Я. Е. Построение двоичного дерева на основе параллельной сортировки/Я. Е. Ромм, Д. А. Чабанюк//Фундаментальные исследования. -2015. -Т. 8., № 3. -С. 509-513.
  • Ромм, Я. Е. Параллельное построение двоичного дерева на основе сортировки/Я. Е. Ромм, Д. А. Чабанюк//Аспекты развития науки, образования и модернизации промышленности: матер. Всеросс. научно-практ. конф. -Таганрог, 2017. -Т. 1. -С. 77-84.
  • Laganà A. Computational Science and Its Applications: Lecture Notes in Computer Science/A. Laganà, V. Kumar, C. Tan. -Assisi: Springer Science & Business Media, 2004. -1044 p. -https://doi.org/10.1007/b98048
  • Chalermsook P. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)/P. Chalermsook, M. Goswami; eds. -Piscataway, NJ: IEEE, 2015. -410-423 p. - DOI: 10.1109/FOCS.2015.98
  • Гавриков, А. В. Т-неприводимые расширения для ориентированных бинарных деревьев/А. В. Гавриков//Компьютерные науки и информационные технологии. -2016. -№ 6. -С. 123-125. -https://doi.org/10.17223/20710410/34/6
  • Гриценко, Н. С. Построение двоичного дерева на основе модифицированной схемы хранения деревьев общего вида «left child»-«right sibling» (LCRS)/Н. С. Гриценко, Ю. С. Белов//Инженерный журнал: наука и инновации. -2014. -№ 3. -С. 75-84. -https://doi.org/10.18698/2308-6033-2014-3-1281.
  • Amir A. Adaptive dictionary matching/A. Amir, M. Farach//Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on. -IEEE, 1991. -P. 760-766. -https://doi.org/10.1109/SFCS.1991.185445
  • Fischer J. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE/J. Fischer, V. Heun//Combinatorial Pattern Matching -Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. -Vol. 4009. -P. 36-48.
  • Institute of Electrical and Electronics Engineers. Pattern-Avoiding Access in Binary Search Trees/Computer Society//2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015). -2015. -№ 56. -P. 410-423. https://doi.org/10.1109/FOCS.2015.32
Еще
Статья научная