77
правок
Изменения
Новая страница: «== Сортировка PSRS == === Описание === Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разраб...»
== Сортировка PSRS ==
=== Описание ===
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:
* сохраняет размер списка более сбалансированным на протяжении всего процесса
* избегает повторных перестановок ключей
=== Алгоритм ===
На вход подаётся <tex>n</tex> элементов. Для начала надо разделить входные данные на <tex>p</tex> равных частей, где <tex>p</tex> {{---}} количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex dpi=145>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>. Теперь нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex dpi=145> p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>. После чего разделим данные в процессорах согласно полученному массиву разделителей. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Разделение происходит следующим образом, данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>. Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
=== Пример ===
Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
Исходный набор данных:
<tex>[15, 46, 48, 93, 39, 6, 72, 91, 14, 36, 69, 40, 89, 61, 97, 12, 21, 54, 53, 97, 84, 58, 32, 27, 33, 72, 20]</tex>:
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"| 1 процессор
!style="background-color:#EEE"| 2 процессор
!style="background-color:#EEE"| 3 процессор
|-
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
|style="background-color:#FFF;padding:2px 10px"| 15 46 48 93 39 6 72 91 14
|style="background-color:#FFF;padding:2px 10px"| 36 69 40 89 61 97 12 21 54
|style="background-color:#FFF;padding:2px 10px"| 53 97 84 58 32 27 33 72 20
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 6 14 15 39 46 48 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 12 21 36 40 54 61 69 89 97
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33 53 58 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| '''6''' 14 15 '''39''' 46 48 '''72''' 91 93
|style="background-color:#FFF;padding:2px 10px"| '''12''' 21 36 '''40''' 54 61 '''69''' 89 97
|style="background-color:#FFF;padding:2px 10px"| '''20''' 27 32 '''33''' 53 58 '''72''' 84 97
|}
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"| Данные
|-
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
|style="background-color:#FFF;padding:2px 10px"| 6 39 72 12 40 69 20 33 72
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 33 39 40 69 72 72
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 '''33''' 39 40 '''69''' 72 72
|-
|style="background-color:#FFF;padding:2px 10px"| Разделители
|style="background-color:#FFF;padding:2px 10px"| 33 69
|}
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"|
!style="background-color:#EEE"| 1 процессор
!style="background-color:#EEE"|
!style="background-color:#EEE"|
!style="background-color:#EEE"| 2 процессор
!style="background-color:#EEE"|
!style="background-color:#EEE"|
!style="background-color:#EEE"| 3 процессор
!style="background-color:#EEE"|
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| После слития
|style="background-color:#FFF;padding:2px 10px"| 6 12 14
|style="background-color:#FFF;padding:2px 10px"| 15 20 21
|style="background-color:#FFF;padding:2px 10px"| 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 36 39 40
|style="background-color:#FFF;padding:2px 10px"| 46 48 53
|style="background-color:#FFF;padding:2px 10px"| 54 58 61 69
|style="background-color:#FFF;padding:2px 10px"| 72 72
|style="background-color:#FFF;padding:2px 10px"| 84 89 91
|style="background-color:#FFF;padding:2px 10px"| 93 97 97
|}
=== Анализ ===
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>,их сортировать мы будем с помощью быстрой сортировки, а так же учитывая что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>. После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин, это займёт <tex>\displaystyle O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. В итоге мы получим <tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex><tex dpi=145> =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.
=== См. также ===
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
=== Описание ===
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:
* сохраняет размер списка более сбалансированным на протяжении всего процесса
* избегает повторных перестановок ключей
=== Алгоритм ===
На вход подаётся <tex>n</tex> элементов. Для начала надо разделить входные данные на <tex>p</tex> равных частей, где <tex>p</tex> {{---}} количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex dpi=145>0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>. Теперь нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex dpi=145> p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>. После чего разделим данные в процессорах согласно полученному массиву разделителей. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Разделение происходит следующим образом, данные в каждом процессоре разобьём на группы элементов, попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>. Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
=== Пример ===
Количество элементов <tex>27</tex>, количество процессоров <tex>3</tex>.
Исходный набор данных:
<tex>[15, 46, 48, 93, 39, 6, 72, 91, 14, 36, 69, 40, 89, 61, 97, 12, 21, 54, 53, 97, 84, 58, 32, 27, 33, 72, 20]</tex>:
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"| 1 процессор
!style="background-color:#EEE"| 2 процессор
!style="background-color:#EEE"| 3 процессор
|-
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
|style="background-color:#FFF;padding:2px 10px"| 15 46 48 93 39 6 72 91 14
|style="background-color:#FFF;padding:2px 10px"| 36 69 40 89 61 97 12 21 54
|style="background-color:#FFF;padding:2px 10px"| 53 97 84 58 32 27 33 72 20
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 6 14 15 39 46 48 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 12 21 36 40 54 61 69 89 97
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33 53 58 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| '''6''' 14 15 '''39''' 46 48 '''72''' 91 93
|style="background-color:#FFF;padding:2px 10px"| '''12''' 21 36 '''40''' 54 61 '''69''' 89 97
|style="background-color:#FFF;padding:2px 10px"| '''20''' 27 32 '''33''' 53 58 '''72''' 84 97
|}
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"| Данные
|-
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
|style="background-color:#FFF;padding:2px 10px"| 6 39 72 12 40 69 20 33 72
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 33 39 40 69 72 72
|-
|style="background-color:#FFF;padding:2px 10px"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| 6 12 20 '''33''' 39 40 '''69''' 72 72
|-
|style="background-color:#FFF;padding:2px 10px"| Разделители
|style="background-color:#FFF;padding:2px 10px"| 33 69
|}
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание этапа
!style="background-color:#EEE"|
!style="background-color:#EEE"| 1 процессор
!style="background-color:#EEE"|
!style="background-color:#EEE"|
!style="background-color:#EEE"| 2 процессор
!style="background-color:#EEE"|
!style="background-color:#EEE"|
!style="background-color:#EEE"| 3 процессор
!style="background-color:#EEE"|
|-
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
|-
|style="background-color:#FFF;padding:2px 10px"| После слития
|style="background-color:#FFF;padding:2px 10px"| 6 12 14
|style="background-color:#FFF;padding:2px 10px"| 15 20 21
|style="background-color:#FFF;padding:2px 10px"| 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 36 39 40
|style="background-color:#FFF;padding:2px 10px"| 46 48 53
|style="background-color:#FFF;padding:2px 10px"| 54 58 61 69
|style="background-color:#FFF;padding:2px 10px"| 72 72
|style="background-color:#FFF;padding:2px 10px"| 84 89 91
|style="background-color:#FFF;padding:2px 10px"| 93 97 97
|}
=== Анализ ===
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex dpi=145>O( \frac {n\log(n/p)}{p})</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>,их сортировать мы будем с помощью быстрой сортировки, а так же учитывая что их количество порядка <tex>p</tex>, то можно сказать, что они сортируются за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>. После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет <tex dpi=145>\frac {n}{p^2}</tex>, а <tex>\mathrm {merge} </tex> двух массивов выполняется за сумму их длин, это займёт <tex>\displaystyle O(\sum \limits_{k=2}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2}-\frac {n}{p^2})=O(n)</tex>. В итоге мы получим <tex dpi=145> O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)</tex><tex dpi=145> =O(\frac {n\log(n/p)}{p}+p^2\log(p)+\frac {n}{p\log p}+p)=O(\frac {n\log(n/p)}{p})</tex>.
=== См. также ===
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
