Нахождение частных сумм элементов массива сдваиванием

Основные авторы описания: А.В.Фролов

Описание свойств и структуры алгоритма

Общее описание алгоритма

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

Математическое описание

Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел.

Вычисляемые данные: частичные суммы первых [math]\displaystyle{ i }[/math] элементов массива, где [math]\displaystyle{ i }[/math] принимает все значения от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math].

Формулы метода: элементы на первом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её соседних элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д. По нахождению тех частных сумм, где [math]\displaystyle{ i }[/math] является степенью двойки, формулы повторяют Нахождение суммы элементов массива сдваиванием. Однако, кроме этого, для каждой пары (например, для нахождения суммы [math]\displaystyle{ x_i+...+x_{i+k} }[/math] и [math]\displaystyle{ x_{i+k+1} +...+ x_{i+2k} }[/math])дополнительно вычисляются все частные суммы от [math]\displaystyle{ x_i+...+x_{i+k+1} }[/math] до [math]\displaystyle{ x_i+...+x_{i+2k-1} }[/math].

Вычислительное ядро алгоритма

Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего [math]\displaystyle{ n - 1 }[/math]) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

Макроструктура алгоритма

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

Описание схемы реализации последовательного алгоритма

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

Последовательная сложность алгоритма

Для вычисления суммы массива, состоящего из [math]\displaystyle{ N }[/math] элементов, при любых разложениях [math]\displaystyle{ N }[/math] на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно [math]\displaystyle{ N - 1 }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

Информационный граф

Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 16 элементов массива. Вершины , соответствующие входным данным - даны синим цветом , выходным данным - красным цветом.

Описание ресурса параллелизма алгоритма

Для суммирования массива порядка [math]\displaystyle{ n }[/math] методом сдваивания в параллельном варианте требуется последовательно выполнить [math]\displaystyle{ \lceil \log_2 n \rceil }[/math] ярусов с убывающим (от [math]\displaystyle{ \frac{n}{2} }[/math] до [math]\displaystyle{ 1 }[/math]) количеством операций суммирования. При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с логарифмической сложностью. При классификации по ширине ЯПФ его сложность будет линейной.

Описание входных и выходных данных

Входные данные: массив [math]\displaystyle{ x }[/math] (элементы [math]\displaystyle{ x_i }[/math]).

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]\displaystyle{ N }[/math].

Выходные данные: сумма элементов массива.

Объём выходных данных: один скаляр.

Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является [math]\displaystyle{ \frac{n}{\log_2 n} }[/math] (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных столько же, сколько операций). При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.