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

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

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

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

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

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

Исходные данные: одномерный массив [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{ \frac{n}{2} log_2 n }[/math]) вычислений сумм.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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