146
правок
Изменения
Нет описания правки
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#Слияние двух массивов|слияние двух массивов]].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <tex dpi="150">T(n) = T(\frac dfrac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
==Многопоточное слияние==
Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpi="120">n_{2} \leqslant n_{1}</tex>, значит,<br>
<tex dpi="135">n_{2} = 2 \cdot \fracdfrac{n_{2}}{2} \leqslant \fracdfrac{(n_{1} + n_{2})}{2} = \fracdfrac{n}{2}</tex>.<br>В худшем случае один из двух рекурсивных вызовов сольет <tex dpi="135">\fracdfrac{n_{1}}{2}</tex> элементов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> с <tex dpi="120">n_{2}</tex> элементами <tex dpi="120">T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br><tex dpi="135">\fracdfrac{n_{1}}{2} + n_{2} \leqslant \fracdfrac{n_{1}}{2} + \fracdfrac{n_{2}}{2} + \fracdfrac{n_{2}}{2} = \fracdfrac{(n_{1} + n_{2})}{2} + \fracdfrac{n_{2}}{2} \leqslant \fracdfrac{n}{2} + \fracdfrac{n}{4} = \fracdfrac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции — <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex dpi="120">T(\fracdfrac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\fracdfrac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
==Сортировка с многопоточным слиянием==
mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex dpi="130">T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\fracdfrac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\fracdfrac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)</tex>.
==Оценка при фиксированном числе потоков==
Понятно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex dpi="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
::[[#Сортировка с однопоточным слиянием|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi="135">\Theta(\fracdfrac{n}{N_{ind}}\log \fracdfrac{n}{N_{ind}} + n) = \Theta(\fracdfrac{n}{N_{ind}}\log \fracdfrac{n}{N_{ind}})</tex>:::::<tex dpi="135">\Theta(\fracdfrac{n}{N_{ind}}\log \fracdfrac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex dpi="135">\fracdfrac{n}{N_{ind}}</tex>.
::::<tex dpi="135">\Theta(n)</tex> необходимо на последовательное слияние.
::[[#Многопоточное слияние|Многопоточное слияние]] будет работать за <tex dpi="135">\Theta((\fracdfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\fracdfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2})</tex>:
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex dpi="110">min(N_{ind}, \log n)</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex dpi="135">\Theta(\log n)</tex>
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
::::<tex dpi="135">T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log n) = \Theta(n^{\log_{\frac{4}{3}}2})</tex>
::Оценим [[#Сортировка с многопоточным слиянием|сортировку с многопоточным слиянием]] снизу:
::::Части массива длиной <tex dpi="135">\fracdfrac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex dpi="135">\fracdfrac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:::::<tex dpi="135">T_{\mathrm {mergeSort}}'(\fracdfrac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\fracdfrac{n}{2N_{ind}}) + \Theta(\fracdfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\fracdfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\fracdfrac{n}{N_{ind}}\log \fracdfrac{n}{N_{ind}})</tex>.
==См. также==
