Изменения

<tex>\mathrm {mergeSortMT}</tex>(array, left, right):

'''<tex>\mathrm {\bf {spawn''' }}</tex> <tex>\mathrm {mergeSortMT}</tex>(array, left, mid) <tex>\mathrm {mergeSortMT}</tex>(array, mid + 1, right) '''<tex>\mathrm {\bf {sync'''}}</tex>

<tex>\mathrm {merge}</tex>(array, left, mid, right)

В данном алгоритме оператор '''<tex>\mathrm {\bf {spawn''' }}</tex> запускает новый поток, а оператор '''<tex>\mathrm {\bf {sync''' }}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge }</tex> аналогична одноименной функции merge из раздела [[Сортировка слиянием#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2|слияние двух массивов]].<br>Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <texdpi="120">T(n) = T(\frac{n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <texdpi="120">T[left_{1} \dots right_{1}]</tex> и <texdpi="120">T[left_{2} \dots right_{2}]</tex> в массив <texdpi="120">A[left_{3} \dots right_{3}]</tex>:# Убедимся, что размер <texdpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <texdpi="120">T[left_{2} \dots right_{2}]</tex># Возьмем <texdpi="120">x = T[mid_{1}]</tex> - середину первого массива (<texdpi="120">x</tex> также является и медианой этого массива)# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <texdpi="120">mid_{2}</tex> такое, что <texdpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex># <texdpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex># <texdpi="120">A[mid_{3}] = x</tex># Сольем <texdpi="120">T[right_{1} \dots mid_{1} - 1]</tex> и <texdpi="120">T[right_{2} \dots mid_{2}]</tex> в <texdpi="120">A[right_{3} \dots mid_{3} - 1]</tex># Сольем <texdpi="120">T[mid_{1} + 1 \dots right_{1}]</tex> и <texdpi="120">T[mid_{2} \dots right_{2}]</tex> в <texdpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>

// если <texdpi="120">right \leqslant left</tex> возвращает <texdpi="120">left</tex> // если <texdpi="120">x \leqslant T[left]</tex>, возвращает <texdpi="120">left</tex> // иначе возвращает наибольший индекс <texdpi="120">i</tex> из отрезка <texdpi="120">[left; right]</tex> такой, что <texdpi="120">array[i - 1] < x</tex> <tex>\mathrm {binarySearch}</tex>(x, array, left, right)

// слияние <texdpi="120">T[left_{1} \dots right_{1}]</tex> и <texdpi="120">T[left_{2} \dots right_{2}]</tex> в <texdpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex> <tex>\mathrm {mergeMT}</tex>(T, left<texdpi="120">_{1}</tex>, right<texdpi="120">_{1}</tex>, left<texdpi="120">_{2}</tex>, right<texdpi="120">_{2}</tex>, A, left<texdpi="120">_{3}</tex>): n<texdpi="120">_{1}</tex> = right<texdpi="120">_{1}</tex> - left<texdpi="120">_{1}</tex> + 1 n<texdpi="120">_{2}</tex> = right<texdpi="120">_{2}</tex> - left<texdpi="120">_{2}</tex> + 1 '''<tex>\mathrm {\bf {if''' }}</tex> n<texdpi="120">_{1}</tex> < n<texdpi="120">_{2}</tex> <tex>\mathrm {swap}</tex>(left<texdpi="120">_{1}</tex>, left<texdpi="120">_{2}</tex>) <tex>\mathrm {swap}</tex>(right<texdpi="120">_{1}</tex>, right<texdpi="120">_{2}</tex>) <tex>\mathrm {swap}</tex>(n<texdpi="120">_{1}</tex>, n<texdpi="120">_{2}</tex>)

'''<tex>\mathrm {\bf {if''' }}</tex> n<texdpi="120">_{1}</tex> == 0 '''<tex>\mathrm {\bf {return'''}}</tex> '''<tex>\mathrm {\bf {else'''}}</tex> mid<texdpi="120">_{1}</tex> = (left<texdpi="120">_{1}</tex> + right<texdpi="120">_{1}</tex>) / 2 mid<texdpi="120">_{2}</tex> = binarySearch(T[mid<texdpi="120">_{1}</tex>], T, left<texdpi="120">_{2}</tex>, right<texdpi="120">_{2}</tex>) mid<texdpi="120">_{3}</tex> = left<texdpi="120">_{3}</tex> + (mid<texdpi="120">_{1}</tex> - left<texdpi="120">_{1}</tex>) + (mid<texdpi="120">_{2}</tex> - left<texdpi="120">_{2}</tex>) A[mid<texdpi="120">_{3}</tex>] = T[mid<texdpi="120">_{1}</tex>] '''<tex>\mathrm {\bf {spawn''' }}</tex> <tex>\mathrm {mergeMT}</tex>(T, left<texdpi="120">_{1}</tex>, mid<texdpi="120">_{1}</tex> - 1, left<texdpi="120">_{2}</tex>, mid<texdpi="120">_{2}</tex> - 1, A, left<texdpi="120">_{3}</tex>) <tex>\mathrm {mergeMT}</tex>(T, mid<texdpi="120">_{1}</tex> + 1, right<texdpi="120">_{1}</tex>, mid<texdpi="120">_{2}</tex>, right<texdpi="120">_{2}</tex>, A, mid<texdpi="120">_{3}</tex> + 1) '''<tex>\mathrm {\bf {sync'''}}</tex>

Оба массива содержат <texdpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <texdpi="120">n_{2} \leqslant n_{1}</tex>, значит,<br><texdpi="135">n_{2} = 2 \cdot \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}</tex>.<br>В худшем случае один из двух рекурсивных вызовов сольет <texdpi="135">\frac{n_{1}}{2}</tex> элементов <texdpi="120">T[left_{1} \dots right_{1}]</tex> с <texdpi="120">n_{2}</tex> элементами <texdpi="120">T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br><texdpi="135">\frac{n_{1}}{2} + n_{2} \leqslant \frac{n_{1}}{2} + \frac{n_{2}}{2} + \frac{n_{2}}{2} = \frac{(n_{1} + n_{2})}{2} + \frac{n_{2}}{2} \leqslant \frac{n}{2} + \frac{n}{4} = \frac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции - <texdpi="120">\Theta(\log(n))</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <texdpi="120">T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><texdpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log(n)) = \Theta(\log^2(n))</tex>

Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <texdpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <texdpi="120">B[leftB \dots leftB + rightA - leftA]</tex>

<tex>\mathrm {mergeSortMT2}</tex>(A, leftA, rightA, B, leftB):

'''<tex>\mathrm {\bf {if''' }}</tex> n == 1

'''<tex>\mathrm {\bf {else'''}}</tex> создадим новый массив T[1 <texdpi="120">\dots</tex> n]

'''<tex>\mathrm {\bf {spawn''' }}</tex> <tex>\mathrm {mergeSortMT2}</tex>(A, leftA, mid, T, 1) <tex>\mathrm {mergeSortMT2}</tex>(A, mid + 1, rightA, T, newMid + 1) '''<tex>\mathrm {\bf {sync'''}}</tex> <tex>\mathrm {mergeMT}</tex>(T, 1, newMid, newMid + 1, n, B, leftB)

Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <texdpi="130">T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2(n)) = \Theta(\log^3(n))</tex>.

Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <texdpi="120">N_{ind}</tex>. Допустим, <texdpi="120">n</tex> много больше <texdpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <texdpi="135">\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}) + n) = \Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>:::::<texdpi="135">\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex> операций нужно на последовательную сортировку массива длиной <texdpi="135">\frac{n}{N_{ind}}</tex>.::::<texdpi="135">\Theta(n)</tex> необходимо на последовательное слияние.::[[#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D0.BE.D0.B5_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|Многопоточное слияние]] будет работать за <texdpi="135">\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))=\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)})</tex>:::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <texdpi="110">min(N_{ind}, \log(n))</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <texdpi="135">\Theta(\log(n))</tex>

::::<texdpi="135">T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log(n)) = \Theta(n^{(\log_{\frac{4}{3}}2)})</tex>

::::Части массива длиной <texdpi="135">\frac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2 } </tex> от массива длиной <texdpi="135">\frac{n}{N_{ind}}</tex> число потоков, равное <texdpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:::::<texdpi="135">T_{\mathrm {mergeSort}}'(\frac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\frac{n}{2N_{ind}}) + \Theta(\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} = \Theta(\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)}</tex>Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <texdpi="120">\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>.