Нахождение суммы элементов массива сдваиванием: различия между версиями
| [досмотренная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
{{level-a}} | {{level-a}} | ||
{{algorithm | |||
| name = Нахождение суммы элементов массива сдваиванием | |||
| serial_complexity = <math>n-1</math> | |||
| pf_height = <math>log2n</math> | |||
| pf_width = <math>n/2</math> | |||
| input_data = <math>n</math> | |||
| output_data = <math>1</math> | |||
}} | |||
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]. | Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]. | ||
| Строка 31: | Строка 40: | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Для вычисления суммы массива, состоящего из <math> | Для вычисления суммы массива, состоящего из <math>n/math> элементов, при любых разложениях <math>n</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>n - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций. | ||
=== Информационный граф === | === Информационный граф === | ||
| Строка 51: | Строка 60: | ||
Дополнительные ограничения: отсутствуют. | Дополнительные ограничения: отсутствуют. | ||
Объём входных данных: <nowiki/><math> | Объём входных данных: <nowiki/><math>n</math>. | ||
Выходные данные: сумма элементов массива. | Выходные данные: сумма элементов массива. | ||
Текущая версия от 13:26, 19 февраля 2025
| Нахождение суммы элементов массива сдваиванием | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ n-1 }[/math] |
| Объём входных данных | [math]\displaystyle{ n }[/math] |
| Объём выходных данных | [math]\displaystyle{ 1 }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ log2n }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ n/2 }[/math] |
Основные авторы описания: А.В.Фролов.
Свойства и структура алгоритма
Общее описание алгоритма
Метод сдваивания используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.
Математическое описание алгоритма
Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел.
Вычисляемые данные: сумма элементов массива.
Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
Вычислительное ядро алгоритма
Вычислительное ядро метода сдваивания для суммирования можно составить как из элементарных бинарных (всего [math]\displaystyle{ n - 1 }[/math]) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.
Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.
Схема реализации последовательного алгоритма
В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.
Последовательная сложность алгоритма
Для вычисления суммы массива, состоящего из [math]\displaystyle{ n/math\gt элементов, при любых разложениях \lt math\gt n }[/math] на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно [math]\displaystyle{ n - 1 }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
Информационный граф
На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 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 (входных и выходных данных столько же, сколько операций). При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.