Многопоточная сортировка слиянием — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Многопоточное слияние)
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
== Многопоточная сортировка слиянием ==
 
== Многопоточная сортировка слиянием ==
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
+
Благодаря тому, что [[Сортировка слиянием | сортировка слиянием]] построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
 +
 
 
==Сортировка с однопоточным слиянием==
 
==Сортировка с однопоточным слиянием==
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
Строка 13: Строка 14:
  
 
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#Слияние двух массивов|слияние двух массивов]].<br>
 
В данном алгоритме оператор <tex>\mathrm {spawn}</tex> запускает новый поток, а оператор <tex>\mathrm {sync}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#Слияние двух массивов|слияние двух массивов]].<br>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <tex dpi="120">T(n) = T(\frac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
+
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <tex>T(n) = T(\dfrac {n}{2}) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
  
 
==Многопоточное слияние==
 
==Многопоточное слияние==
Строка 19: Строка 20:
  
 
# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex>
 
# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex>
# Возьмем <tex dpi="120">x = T[mid_{1}]</tex> - середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)
+
# Возьмем <tex dpi="120">x = T[mid_{1}]</tex> середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)
 
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такое, что <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
 
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такое, что <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
 
# <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
 
# <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
Строка 31: Строка 32:
  
 
===Реализация===
 
===Реализация===
     // если <tex dpi="120">right \leqslant left</tex> возвращает <tex dpi="120">left</tex>
+
     <font color=green>// если <tex dpi="120" color=green>right \leqslant left</tex> возвращает <tex dpi="120">left</tex>
 
     // если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
 
     // если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
     // иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex>
+
     // иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex></font>
 
     '''integer''' binarySearch(x, array, left, right)
 
     '''integer''' binarySearch(x, array, left, right)
 
      
 
      
     // слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex>
+
     <font color=green>// слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex></font>
 
     '''function''' mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
 
     '''function''' mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
 
         n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
 
         n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
Строка 57: Строка 58:
  
 
Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpi="120">n_{2} \leqslant n_{1}</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 \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}</tex>.<br>
+
<tex>n_{2} = 2 \cdot \dfrac{n_{2}}{2} \leqslant \dfrac{(n_{1} + n_{2})}{2} = \dfrac{n}{2}</tex>.<br>
В худшем случае один из двух рекурсивных вызовов сольет <tex dpi="135">\frac{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>\dfrac{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">\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>Асимптотика каждого вызова функции - <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex dpi="120">T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
+
<tex>\dfrac{n_{1}}{2} + n_{2} \leqslant \dfrac{n_{1}}{2} + \dfrac{n_{2}}{2} + \dfrac{n_{2}}{2} = \dfrac{(n_{1} + n_{2})}{2} + \dfrac{n_{2}}{2} \leqslant \dfrac{n}{2} + \dfrac{n}{4} = \dfrac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(\dfrac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex>T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\dfrac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
  
 
==Сортировка с многопоточным слиянием==
 
==Сортировка с многопоточным слиянием==
Строка 77: Строка 78:
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
  
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex dpi="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>.
+
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex>T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\dfrac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\dfrac{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="120">N_{ind}</tex>. Допустим, <tex dpi="120">n</tex> много больше <tex dpi="120">N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>
::[[#Сортировка с однопоточным слиянием|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}} + n) = \Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>:
+
::[[#Сортировка с однопоточным слиянием|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}} + n) = \Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex>:
::::<tex dpi="135">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex>.
+
::::<tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex> операций нужно на последовательную сортировку массива длиной <tex>\dfrac{n}{N_{ind}}</tex>.
 
::::<tex dpi="135">\Theta(n)</tex> необходимо на последовательное слияние.
 
::::<tex dpi="135">\Theta(n)</tex> необходимо на последовательное слияние.
::[[#Многопоточное слияние|Многопоточное слияние]] будет работать за <tex dpi="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>:
+
::[[#Многопоточное слияние|Многопоточное слияние]] будет работать за <tex>\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\dfrac{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="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>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">\frac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex dpi="135">\frac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:
+
::::Части массива длиной <tex>\dfrac{n}{N_{ind}}</tex> гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова <tex>\mathrm {mergeSortMT2} </tex> от массива длиной <tex>\dfrac{n}{N_{ind}}</tex> число потоков, равное <tex dpi="135">N_{ind}</tex>. Тогда по основной теореме рекуррентных соотношений:
::::<tex dpi="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>
+
::::<tex>T_{\mathrm {mergeSort}}'(\dfrac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\dfrac{n}{2N_{ind}}) + \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}</tex>
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>.
+
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex>\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})</tex>.
  
 +
==См. также==
 +
*[[Сортировка слиянием]]
 +
*[[PSRS-сортировка]]
 
==Источники информации==
 
==Источники информации==
 
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
 
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]
+
[[Категория: Сортировки]]
 +
[[Категория: Многопоточные сортировки]]

Текущая версия на 19:27, 4 сентября 2022

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

Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.

Сортировка с однопоточным слиянием

Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.

   function mergeSortMT(array, left, right):
       mid = (left + right) / 2
   
       spawn mergeSortMT(array, left, mid)
       mergeSortMT(array, mid + 1, right)
       sync
   
       merge(array, left, mid, right)

В данном алгоритме оператор [math]\mathrm {spawn}[/math] запускает новый поток, а оператор [math]\mathrm {sync}[/math] ожидает завершения этого потока. Функция [math]\mathrm {merge}[/math] аналогична одноименной функции из раздела слияние двух массивов.
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: [math]T(n) = T(\dfrac {n}{2}) + \Theta(n) = \Theta(n)[/math]. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.

Многопоточное слияние

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в массив [math]A[left_{3} \dots right_{3}][/math]:

  1. Убедимся, что размер [math]T[left_{1} \dots right_{1}][/math] больше либо равен размеру [math]T[left_{2} \dots right_{2}][/math]
  2. Возьмем [math]x = T[mid_{1}][/math] — середину первого массива ([math]x[/math] также является и медианой этого массива)
  3. При помощи бинарного поиска найдем [math]mid_{2}[/math] такое, что [math]\forall y \in T[left_{2} \dots mid_{2} - 1]: y \lt x[/math]
  4. [math]mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})[/math]
  5. [math]A[mid_{3}] = x[/math]
  6. Сольем [math]T[right_{1} \dots mid_{1} - 1][/math] и [math]T[right_{2} \dots mid_{2}][/math] в [math]A[right_{3} \dots mid_{3} - 1][/math]
  7. Сольем [math]T[mid_{1} + 1 \dots right_{1}][/math] и [math]T[mid_{2} \dots right_{2}][/math] в [math]A[mid_{3} + 1 \dots right_{3}][/math]

Алгоритм показан на рисунке:

Слияние массивов

Реализация

   // если [math]right \leqslant left[/math] возвращает [math]left[/math]
   // если [math]x \leqslant T[left][/math], возвращает [math]left[/math]
   // иначе возвращает наибольший индекс [math]i[/math] из отрезка [math][left, right][/math] такой, что [math]array[i - 1] \lt  x[/math]
   integer binarySearch(x, array, left, right)
   
   // слияние [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в [math]A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}][/math]
   function mergeMT(T, left[math]_{1}[/math], right[math]_{1}[/math], left[math]_{2}[/math], right[math]_{2}[/math], A, left[math]_{3}[/math]):
       n[math]_{1}[/math] = right[math]_{1}[/math] - left[math]_{1}[/math] + 1
       n[math]_{2}[/math] = right[math]_{2}[/math] - left[math]_{2}[/math] + 1
       if n[math]_{1}[/math] < n[math]_{2}[/math]
           swap(left[math]_{1}[/math], left[math]_{2}[/math])
           swap(right[math]_{1}[/math], right[math]_{2}[/math])
           swap(n[math]_{1}[/math], n[math]_{2}[/math])
   
       if n[math]_{1}[/math] == 0
           return
       else
           mid[math]_{1}[/math] = (left[math]_{1}[/math] + right[math]_{1}[/math]) / 2
           mid[math]_{2}[/math] = binarySearch(T[mid[math]_{1}[/math]], T, left[math]_{2}[/math], right[math]_{2}[/math])
           mid[math]_{3}[/math] = left[math]_{3}[/math] + (mid[math]_{1}[/math] - left[math]_{1}[/math]) + (mid[math]_{2}[/math] - left[math]_{2}[/math])
           A[mid[math]_{3}[/math]] = T[mid[math]_{1}[/math]]
           spawn mergeMT(T, left[math]_{1}[/math], mid[math]_{1}[/math] - 1, left[math]_{2}[/math], mid[math]_{2}[/math] - 1, A, left[math]_{3}[/math])
           mergeMT(T, mid[math]_{1}[/math] + 1, right[math]_{1}[/math], mid[math]_{2}[/math], right[math]_{2}[/math], A, mid[math]_{3}[/math] + 1)
           sync

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

Сортировка с многопоточным слиянием

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

   function mergeSortMT2(A, leftA, rightA, B, leftB):
       n = r - p + 1
       if n == 1
           B[leftB] = A[leftA]
       else
           создадим новый массив T[1 [math]\dots[/math] n]
           mid = (leftA + rightA) / 2
           newMid = mid - leftA + 1
           spawn mergeSortMT2(A, leftA, mid, T, 1)
           mergeSortMT2(A, mid + 1, rightA, T, newMid + 1)
           sync
           mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)

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

Оценка при фиксированном числе потоков

Понятно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как [math]N_{ind}[/math]. Допустим, [math]n[/math] много больше [math]N_{ind}[/math], что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:

Сортировка с однопоточным слиянием будет иметь асимптотику [math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}} + n) = \Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math]:
[math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math] операций нужно на последовательную сортировку массива длиной [math]\dfrac{n}{N_{ind}}[/math].
[math]\Theta(n)[/math] необходимо на последовательное слияние.
Многопоточное слияние будет работать за [math]\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} + \log n \cdot min(N_{ind}, \log n)=\Theta((\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2})[/math]:
Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на [math]min(N_{ind}, \log n)[/math] уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за [math]\Theta(\log n)[/math]
Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
[math]T_{\mathrm {merge}}'(n) = 2T_{\mathrm {merge}}'(\frac {3}{4}n) + \Theta(\log n) = \Theta(n^{\log_{\frac{4}{3}}2})[/math]
Оценим сортировку с многопоточным слиянием снизу:
Части массива длиной [math]\dfrac{n}{N_{ind}}[/math] гарантированно будут сортироваться последовательно, т.к. только алгоритм сортировки запустит к моменту вызова [math]\mathrm {mergeSortMT2} [/math] от массива длиной [math]\dfrac{n}{N_{ind}}[/math] число потоков, равное [math]N_{ind}[/math]. Тогда по основной теореме рекуррентных соотношений:
[math]T_{\mathrm {mergeSort}}'(\dfrac{n}{N_{ind}}) = 2T_{\mathrm {mergeSort}}'(\dfrac{n}{2N_{ind}}) + \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2} = \Theta(\dfrac{n}{N_{ind}})^{\log_{\frac{4}{3}}2}[/math]

Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет [math]\Theta(\dfrac{n}{N_{ind}}\log \dfrac{n}{N_{ind}})[/math].

См. также

Источники информации

  • Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. — Introduction to Algorithms, Third Edition