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

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

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

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

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

1.2 Математическое описание алгоритма

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

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

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

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

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

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют элементарные бинарные (всего [math]\frac{n}{2} log_2 n[/math]) вычисления сумм.

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

В описанном виде суммирование сдваиванием не используют при последовательной реализации, поскольку кроме усложнения общей схемы алгоритма и резкого роста потребности в памяти, нужной для хранения промежуточных данных, сам по себе алгоритм содержит подавляющее большинство избыточных вычислений: по сравнению с последовательным алгоритмом нахождения частных сумм количество операций больше в [math]\frac{1}{2} log_2 n[/math] раз.

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

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

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

Рисунок 1. Граф алгоритма при n=16 c отображением входных данных. Чёрными обозначены операции, результаты которых нужны на выходе алгоритма. Все вершины соответствуют операции сложения

1.8 Ресурс параллелизма алгоритма

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

1.9 Входные и выходные данные алгоритма

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

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

Объём входных данных: [math]n[/math].

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

Объём выходных данных: [math]n[/math].

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

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