Алговики - Вклад [ru]

https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/api.php?action=feedcontributions&feedformat=atom&user=KulikovM Алговики - Вклад [ru] 2026-10-22T22:58:27Z Вклад MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30067 Участник:KulikovM 2025-11-23T23:34:26Z

<p>KulikovM: /* Параллельная реализация */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> # Независимая локальная сортировка в каждом процессе<br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> <br /> == MPI код на Си с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> == Обоснование выбора MPI ==<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны, является кластером с распределенной памятью.<br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30066 Участник:KulikovM 2025-11-23T23:34:01Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> <br /> == MPI код на Си с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> == Обоснование выбора MPI ==<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны, является кластером с распределенной памятью.<br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30065 Участник:KulikovM 2025-11-23T23:33:30Z

<p>KulikovM: /* Параллельная реализация на С с помощью технологии MPI */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> <br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> == Обоснование выбора MPI ==<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны, является кластером с распределенной памятью.<br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30064 Участник:KulikovM 2025-11-23T23:17:33Z

<p>KulikovM: </p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> == Обоснование выбора MPI ==<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны, является кластером с распределенной памятью.<br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30063 Участник:KulikovM 2025-11-23T22:55:58Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30062 Участник:KulikovM 2025-11-23T22:50:59Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны(результаты приведены ниже) является кластером с распределенной памятью.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30061 Участник:KulikovM 2025-11-23T22:50:02Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слиянии.<br /> MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны(приведены ниже) является кластером с распределенной памятью.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30060 Участник:KulikovM 2025-11-23T22:45:50Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI.<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам.<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слияни.<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30059 Участник:KulikovM 2025-11-23T22:45:02Z

<p>KulikovM: </p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> </pre><br /> Основные MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слияни<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30058 Участник:KulikovM 2025-11-23T22:41:39Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> <pre><br /> <br /> <br /> = Основные MPI операции =<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слияни<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30057 Участник:KulikovM 2025-11-23T22:41:04Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> <pre><br /> <br /> <br /> MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слияни<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30056 Участник:KulikovM 2025-11-23T22:40:17Z

<p>KulikovM: /* MPI код с замерами времени и генерацией данных */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> <pre><br /> MPI операции:<br /> * MPI_Init/MPI_Finalize - инициализация/завершение MPI<br /> <br /> * MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов<br /> <br /> * MPI_Scatter - распределение данных от процесса 0 ко всем процессам<br /> <br /> * MPI_Send/MPI_Recv - передача данных между процессами при слияни<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30055 Участник:KulikovM 2025-11-23T22:38:21Z

<p>KulikovM: /* MPI код с замерами времени генерацией данных, использовавшийся в прогонах */</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени и генерацией данных ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> <pre><br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30054 Участник:KulikovM 2025-11-23T22:36:00Z

<p>KulikovM: </p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> == Параллельная реализация на С с помощью технологии MPI ==<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == MPI код с замерами времени генерацией данных, использовавшийся в прогонах ==<br /> <pre><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <mpi.h><br /> <br /> // Функция слияния двух отсортированных массивов<br /> int* merge(int *a, int na, int *b, int nb) {<br /> int *c = malloc((na + nb) * sizeof(int));<br /> int i = 0, j = 0, k = 0;<br /> <br /> // Слияние двух массивов в один отсортированный<br /> while (i < na && j < nb) {<br /> if (a[i] < b[j]) c[k++] = a[i++];<br /> else c[k++] = b[j++];<br /> }<br /> <br /> // Добиваем остатки из первого массива<br /> while (i < na) c[k++] = a[i++];<br /> // Добиваем остатки из второго массива<br /> while (j < nb) c[k++] = b[j++];<br /> <br /> return c;<br /> }<br /> <br /> // Рекурсивная сортировка слиянием<br /> int* msort(int *arr, int n) {<br /> if (n <= 1) {<br /> int *r = malloc(n * sizeof(int));<br /> if (n == 1) r[0] = arr[0];<br /> return r;<br /> }<br /> <br /> // Делим массив пополам<br /> int mid = n / 2;<br /> // Сортируем левую часть рекурсивно<br /> int *left = msort(arr, mid);<br /> // Сортируем правую часть рекурсивно<br /> int *right = msort(arr + mid, n - mid);<br /> // Сливаем отсортированные части<br /> int *result = merge(left, mid, right, n - mid);<br /> <br /> // Освобождаем временные массивы<br /> free(left);<br /> free(right);<br /> return result;<br /> }<br /> <br /> int main(int argc, char *argv[]) {<br /> MPI_Init(&argc, &argv);<br /> <br /> int rank, size;<br /> MPI_Comm_rank(MPI_COMM_WORLD, &rank); // Получаем номер процесса<br /> MPI_Comm_size(MPI_COMM_WORLD, &size); // Получаем общее количество процессов<br /> <br /> // Проверка аргументов командной строки<br /> if (argc < 2 && rank == 0) {<br /> printf("Usage: %s <array_size>\n", argv[0]);<br /> MPI_Finalize();<br /> return 1;<br /> }<br /> <br /> int n = atoi(argv[1]); // Общий размер массива<br /> int local_n = n / size; // Размер части на процесс<br /> int *data = NULL; // Буфер для всего массива (только в процессе 0)<br /> int *local = malloc(local_n * sizeof(int)); // Локальная часть массива<br /> <br /> int i;<br /> int step;<br /> <br /> // Генерация данных в процессе 0<br /> if (rank == 0) {<br /> data = malloc(n * sizeof(int));<br /> for (i = 0; i < n; i++) {<br /> data[i] = rand() % 1000000; // Заполнение случайными числами<br /> }<br /> }<br /> <br /> double start = MPI_Wtime(); // Замер времени начала<br /> <br /> // Распределение данных между процессами (Scatter)<br /> MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);<br /> <br /> if (rank == 0) free(data); // Освобождаем исходный массив в процессе 0<br /> <br /> // Локальная сортировка - каждый процесс сортирует свою часть<br /> int *sorted_local = msort(local, local_n);<br /> free(local);<br /> <br /> int *result = sorted_local; // Результирующий массив процесса<br /> int result_size = local_n; // Размер результата<br /> <br /> // Иерархическое слияние - кооперативная операция между процессами<br /> for (step = 1; step < size; step *= 2) {<br /> if (rank % (2 * step) == 0) {<br /> // Процесс-получатель: получает данные от партнера и сливает<br /> if (rank + step < size) {<br /> int partner_size;<br /> // Получаем размер данных от партнера<br /> MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> int *partner_data = malloc(partner_size * sizeof(int));<br /> // Получаем сами данные от партнера<br /> MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);<br /> <br /> // Сливаем свой результат с данными партнера<br /> int *merged = merge(result, result_size, partner_data, partner_size);<br /> free(result);<br /> free(partner_data);<br /> <br /> result = merged;<br /> result_size += partner_size;<br /> }<br /> } else if (rank % step == 0) {<br /> // Процесс-отправитель: отправляет свои данные и завершает работу<br /> MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);<br /> MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);<br /> free(result);<br /> break; // Завершаем цикл для этого процесса<br /> }<br /> }<br /> <br /> double end = MPI_Wtime(); // Замер времени окончания<br /> <br /> // Вывод результата в процессе 0<br /> if (rank == 0) {<br /> printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);<br /> free(result);<br /> }<br /> <br /> MPI_Finalize();<br /> return 0;<br /> }<br /> <pre><br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30053 Участник:KulikovM 2025-11-23T22:31:32Z

<p>KulikovM: </p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> = Параллельная реализация на С с помощью технологии MPI =<br /> Иерархия параллелизма:<br /> # Распределение данных между MPI-процессами<br /> <br /> # Независимая локальная сортировка в каждом процессе<br /> <br /> # Рекурсивное слияние внутри локальной сортировки<br /> Оценка сложности:<br /> * Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния<br /> <br /> * Коммуникации: O(log p) шагов, O(n) общий объем пересылок<br /> <br /> * Память: O(n/p) на процесс + временные буферы<br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=30052 Участник:KulikovM 2025-11-23T22:29:51Z

<p>KulikovM: </p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> = Параллельная реализация на С с помощью технологии MPI =<br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:KulikovM&diff=29800 Участник:KulikovM 2025-10-28T00:36:49Z

<p>KulikovM: Новая страница: « = Свойства и структура алгоритма = == Общее описание == Сортировка слиянием упорядочивает...»</p> <hr /> <div><br /> = Свойства и структура алгоритма =<br /> <br /> == Общее описание ==<br /> Сортировка слиянием упорядочивает набор элементов вида '''Aᵢ''' ('''1 ≤ i ≤ n''') путём рекурсивного деления набора на две части и последующего слияния отсортированных половин.<br /> В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция '''merge''' в каждом узле выполняется последовательно.<br /> <br /> == Математическое описание ==<br /> Пусть n ≥ 2. Набор элементов '''Aᵢ''' делится на две части:<br /> * левая часть: элементы '''Aᵢ''', где '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * правая часть: элементы '''Aⱼ''', где '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> <br /> Затем рекурсивно сортируются обе части и выполняется операция слияния.<br /> <br /> Базовый случай:<br /> * если n = 1, набор считается уже отсортированным.<br /> <br /> === Операция слияния (merge) ===<br /> Операция '''merge''' объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.<br /> <br /> В процессе слияния используются три индекса:<br /> * '''i''' — пробегает левую часть, '''1 ≤ i ≤ ⌊n/2⌋'''<br /> * '''j''' — пробегает правую часть, '''⌊n/2⌋ + 1 ≤ j ≤ n'''<br /> * '''k''' — позиция результирующего набора, '''1 ≤ k ≤ n'''<br /> <br /> Алгоритм слияния (по умолчанию — '''неубывание'''):<br /> # сравниваются элементы '''Aᵢ''' и '''Aⱼ''';<br /> # меньший из них записывается в '''Aₖ''';<br /> # затем увеличивается индекс (''i'' или ''j'') и индекс ''k'';<br /> # когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.<br /> <br /> *'''Невозрастание:''' в шагах сравнения выше используйте знак '''≥''' вместо '''≤''' (то есть выбирайте больший элемент). <br /> *'''Стабильность:''' при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.<br /> <br /> == Вычислительное ядро ==<br /> Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы '''Aᵢ''' и '''Aⱼ''' и формируется результирующая упорядоченная последовательность в позиции '''Aₖ'''.<br /> Для невозрастания меняется только знак в сравнении ('''≥''' вместо '''≤''').<br /> <br /> == Макроструктура ==<br /> Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:<br /> * на каждом уровне дерево делит исходный набор элементов на две части,<br /> * каждая ветвь обрабатывается независимо (возможен параллелизм),<br /> * на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.<br /> <br /> Таким образом:<br /> * последовательность вычислений на нисходящем этапе — разбиение набора по индексам,<br /> * последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.<br /> <br /> == Схема последовательной реализации ==<br /> В последовательной реализации рекурсивная сортировка левой части выполняется полностью,<br /> затем сортируется правая часть, и лишь после этого вызывается операция merge.<br /> Для невозрастания меняется только знак сравнения в merge ('''≥''' вместо '''≤''').<br /> <br /> == Последовательная сложность ==<br /> Общая сложность определяется затратами на:<br /> * разбиение на две части (O(1)),<br /> * сортировку левой части O((n/2) log(n/2)),<br /> * сортировку правой части O((n/2) log(n/2)),<br /> * слияние (линейный проход: k от 1 до n ⇒ O(n)).<br /> <br /> Итого:<br /> '''T(n) = O(n log n)''' по времени и '''O(n)''' дополнительная память под результирующую перестановку.<br /> <br /> == Информационный граф ==<br /> Информационный граф представляет собой дерево:<br /> [[Файл:Граф сортировки слиянием.png|мини|центр|Информационный граф сортировки слиянием (n=8)]]<br /> <br /> == Ресурс параллелизма ==<br /> Параллелизм достигается за счёт независимой обработки двух половин набора.<br /> На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ).<br /> Высота параллельной части определяется глубиной рекурсии: O(log n).<br /> <br /> == Вход/выход ==<br /> # Вход: массив '''A''' из '''n''' сравнимых элементов. <br /> # Выход: тот же массив, отсортированный по '''неубыванию''' (по умолчанию) либо по '''невозрастанию''' (если в merge поменять '''≤''' на '''≥''').<br /> <br /> == Свойства ==<br /> * Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).<br /> * Хорошо подходит для больших массивов.<br /> * Естественно поддерживает распараллеливание рекурсивной части.<br /> = Программная реализация алгоритма =<br /> <br /> <br /> == Последовательная реализация (псевдокод) ==<br /> <pre><br /> procedure MergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> MergeSort(A, l, m)<br /> MergeSort(A, m+1, r)<br /> Merge(A, l, m, r) // слияние двух отсортированных фрагментов<br /> <br /> // Слияние по неубыванию (для невозрастания заменить ≤ на ≥)<br /> procedure Merge(A, l, m, r):<br /> i := l // индекс в левой части<br /> j := m + 1 // индекс в правой части<br /> k := 0 // индекс во временном буфере B[0 .. r-l]<br /> B := new array of size (r - l + 1)<br /> <br /> while i ≤ m and j ≤ r:<br /> if A[i] ≤ A[j]: // <-- для невозрастания здесь использовать A[i] ≥ A[j]<br /> B[k] := A[i]; i := i + 1<br /> else<br /> B[k] := A[j]; j := j + 1<br /> k := k + 1<br /> <br /> while i ≤ m: B[k] := A[i]; i := i + 1; k := k + 1<br /> while j ≤ r: B[k] := A[j]; j := j + 1; k := k + 1<br /> <br /> // копирование результата назад<br /> for t := 0 .. (r - l):<br /> A[l + t] := B[t]<br /> </pre><br /> <br /> == Параллельная реализация (последовательно-параллельная) ==<br /> Псевдокод:<br /> <pre><br /> procedure PMergeSort(A, l, r):<br /> if r - l + 1 <= 1: return<br /> m := (l + r) // 2<br /> <br /> parallel:<br /> PMergeSort(A, l, m) // ветвь 1<br /> PMergeSort(A, m+1, r) // ветвь 2<br /> join<br /> <br /> Merge(A, l, m, r) // слияние — последовательное<br /> </pre><br /> <br /> == Результаты прогонов (типичное поведение) ==<br /> <br /> = Литература и источники =<br /> * Н. Вирт. ''Алгоритмы и структуры данных''. § 2.4 «Сортировка последовательностей» (с. 97). [[:File:Wirth_2010_Алгоритмы_и_структуры_данных.pdf#page=97|PDF (стр. 97)]]</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%93%D1%80%D0%B0%D1%84_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC.png&diff=29799 Файл:Граф сортировки слиянием.png 2025-10-27T22:29:12Z

<p>KulikovM: </p> <hr /> <div>Это граф</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%93%D1%80%D0%B0%D1%84.jpg&diff=29798 Файл:Граф.jpg 2025-10-27T22:11:21Z

<p>KulikovM: </p> <hr /> <div>Граф</div>

KulikovM https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC_(n%3D8).png&diff=29797 Файл:Информационный граф сортировки слиянием (n=8).png 2025-10-27T22:05:57Z

<p>KulikovM: </p> <hr /> <div>Информационный граф сортировки слиянием (n=8)</div>

KulikovM