Обсуждение:PSRS-сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Для начала надо разделить входные данные на n равных частей, где <tex>n</tex> - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее  мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex>0, n/p^2, 2n/p^2,...,(p-1)n/p^2</tex> и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex>p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)p + [p / 2] - 1</tex>. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
 
Для начала надо разделить входные данные на n равных частей, где <tex>n</tex> - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее  мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами <tex>0, n/p^2, 2n/p^2,...,(p-1)n/p^2</tex> и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex>p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)p + [p / 2] - 1</tex>. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.
 
=== Пример ===
 
=== Пример ===
Количество элементов 45, количество процессоров 3.
+
Количество элементов 27, количество процессоров 3.
Исходный набор данных <tex>[6, 3, 7, 3, 8, 9, 5, 1, 3, 9, 0, 4, 7, 4, 3, 7, 8, 2, 4, 1, 0, 6, 3, 7, 8, 3, 9, 3, 6, 5, 8, 9, 0, 4, 3, 2, 5, 1, 5, 7, 3, 9, 4, 2, 7]</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:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| Описание команды
 
!style="background-color:#EEE"| Описание команды
Строка 12: Строка 12:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
 
|style="background-color:#FFF;padding:2px 10px"| Разделение между процессорами
|style="background-color:#FFF;padding:2px 10px"| 6 3 7 3 8 9 5 1 3 9 0 4 7 4 3
+
|style="background-color:#FFF;padding:2px 10px"| 15 46 48 93 39 6 72 91 14
|style="background-color:#FFF;padding:2px 10px"| 7 8 2 4 1 0 6 3 7 8 3 9 3 6 5
+
|style="background-color:#FFF;padding:2px 10px"| 36 69 40 89 61 97 12 21 54
|style="background-color:#FFF;padding:2px 10px"| 8 9 0 4 3 2 5 1 5 7 3 9 4 2 7
+
|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"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3 4 4 5 6 7 7 8 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 6 14 15 39 46 48 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3 4 5 6 6 7 7 8 8 9
+
|style="background-color:#FFF;padding:2px 10px"| 12 21 36 40 54 61 69 89 97
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3 4 4 5 5 7 7 8 9 9
+
|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"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 3 3 '''3 3''' 4 4 5 '''6 7''' 7 8 9 '''9'''  
+
|style="background-color:#FFF;padding:2px 10px"| '''6''' 14 15 '''39''' 46 48 '''72''' 91 93 
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 2 3 '''3 3''' 4 5 6 '''6 7''' 7 8 8 '''9'''  
+
|style="background-color:#FFF;padding:2px 10px"| '''12''' 21 36 '''40''' 54 61 '''69''' 89 97
|style="background-color:#FFF;padding:2px 10px"| '''0''' 1 2 2 '''3 3''' 4 4 5 '''5 7''' 7 8 9 '''9'''
+
|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:#CCC;margin:0.5px"
Строка 31: Строка 31:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
 
|style="background-color:#FFF;padding:2px 10px"| Выбранные элементы
|style="background-color:#FFF;padding:2px 10px"| 6 8 9 9 0 3 7 1 0 8 3 5 8 3 2 7 3 7
+
|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"| После сортировки
|style="background-color:#FFF;padding:2px 10px"| 0 0 0 3 3 3 3 3 3 5 6 6 7 7 7 9 9 9
+
|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"| Выбор элементов
|style="background-color:#FFF;padding:2px 10px"| 0 0 0 3 3 '''3''' 3 3 3 5 6 '''6''' 7 7 7 9 9 '''9'''
+
|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"| Разделители
|style="background-color:#FFF;padding:2px 10px"| 3 6 9
+
|style="background-color:#FFF;padding:2px 10px"| 33 69
 
|}
 
|}
В данном примере для удобства были выбраны другие элементы.
 
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
 
!style="background-color:#EEE"| Описание команды
 
!style="background-color:#EEE"| Описание команды
Строка 56: Строка 55:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
 
|style="background-color:#FFF;padding:2px 10px"| После сортировки частей
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 6
+
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 4 5 6 6
+
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 8 9
+
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 5
+
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
 
|style="background-color:#FFF;padding:2px 10px"| После обмена данными
|style="background-color:#FFF;padding:2px 10px"| 0 1 3 3 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 6 14 15
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 3 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 12 21
|style="background-color:#FFF;padding:2px 10px"| 0 1 2 2 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 20 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 6
+
|style="background-color:#FFF;padding:2px 10px"| 39 46 48
|style="background-color:#FFF;padding:2px 10px"| 4 5 6 6
+
|style="background-color:#FFF;padding:2px 10px"| 36 40 54 61 69
|style="background-color:#FFF;padding:2px 10px"| 4 4 5 5
+
|style="background-color:#FFF;padding:2px 10px"| 53 58
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 72 91 93
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 8 9
+
|style="background-color:#FFF;padding:2px 10px"| 89 97
|style="background-color:#FFF;padding:2px 10px"| 7 7 8 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 72 84 97
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 10px"| После слития
 
|style="background-color:#FFF;padding:2px 10px"| После слития
|style="background-color:#FFF;padding:2px 10px"| 0 0 0 1 1 1  
+
|style="background-color:#FFF;padding:2px 10px"| 6 12 14  
|style="background-color:#FFF;padding:2px 10px"| 2 2 2 3 3 3 
+
|style="background-color:#FFF;padding:2px 10px"| 15 20 21
|style="background-color:#FFF;padding:2px 10px"| 3 3 3 3 3 3
+
|style="background-color:#FFF;padding:2px 10px"| 27 32 33
|style="background-color:#FFF;padding:2px 10px"| 4 4 4 4 
+
|style="background-color:#FFF;padding:2px 10px"| 36 39 40 
|style="background-color:#FFF;padding:2px 10px"| 4 5 5 5
+
|style="background-color:#FFF;padding:2px 10px"| 46 48 53
|style="background-color:#FFF;padding:2px 10px"| 5 6 6 6
+
|style="background-color:#FFF;padding:2px 10px"| 54 58 61 69
|style="background-color:#FFF;padding:2px 10px"| 7 7 7 7 7  
+
|style="background-color:#FFF;padding:2px 10px"| 72 72  
|style="background-color:#FFF;padding:2px 10px"| 7 8 8 8 8
+
|style="background-color:#FFF;padding:2px 10px"| 84 89 91
|style="background-color:#FFF;padding:2px 10px"| 9 9 9 9 9
+
|style="background-color:#FFF;padding:2px 10px"| 93 97 97
 
|}
 
|}
 
=== Анализ ===
 
=== Анализ ===
 
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex>O(n/p\log(n/p))</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>,их сортировка произойдёт за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>. После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре, это займёт <tex>O(n/p\log p)</tex>. В итоге мы получаем <tex>O(n/p\log(n/p))+O(p^2\log(p))+O(n/p\log p)+O(p)</tex><tex>=O(n/p\log(n/p)+p^2\log(p)+n/p\log p+p)=O(n/p\log(n/p))</tex>
 
При <tex>n</tex> элементах и <tex>p</tex> процессорах начальная сортировка выполнится за <tex>O(n/p\log(n/p))</tex>. Выбор порядка <tex>p</tex> элементов в каждом процессоре произойдёт за <tex>O(p)</tex>,их сортировка произойдёт за <tex>O(p^2\log(p^2))=O(p^2\log(p))</tex>. После обмена данными будет произведено слияние <tex>p</tex> массивов в каждом процессоре, это займёт <tex>O(n/p\log p)</tex>. В итоге мы получаем <tex>O(n/p\log(n/p))+O(p^2\log(p))+O(n/p\log p)+O(p)</tex><tex>=O(n/p\log(n/p)+p^2\log(p)+n/p\log p+p)=O(n/p\log(n/p))</tex>

Версия 23:21, 10 июня 2014

Сортировка PSRS

Алгоритм

Для начала надо разделить входные данные на n равных частей, где [math]n[/math] - количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами [math]0, n/p^2, 2n/p^2,...,(p-1)n/p^2[/math] и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами [math]p + [p / 2] - 1, 2p + [p / 2] - 1,...,(p-1)p + [p / 2] - 1[/math]. Теперь разделим данные в процессорах согласно полученному массиву разделителей и сольём данные соответствующие части в в массив.

Пример

Количество элементов 27, количество процессоров 3. Исходный набор данных [math][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][/math]:

Описание команды 1 процессор 2 процессор 3 процессор
Разделение между процессорами 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
После сортировки частей 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97
Выбор элементов 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97
Описание команды Данные
Выбранные элементы 6 39 72 12 40 69 20 33 72
После сортировки 6 12 20 33 39 40 69 72 72
Выбор элементов 6 12 20 33 39 40 69 72 72
Разделители 33 69
Описание команды 1 процессор 2 процессор 3 процессор
После сортировки частей 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97
После обмена данными 6 14 15 12 21 20 27 32 33 39 46 48 36 40 54 61 69 53 58 72 91 93 89 97 72 84 97
После слития 6 12 14 15 20 21 27 32 33 36 39 40 46 48 53 54 58 61 69 72 72 84 89 91 93 97 97

Анализ

При [math]n[/math] элементах и [math]p[/math] процессорах начальная сортировка выполнится за [math]O(n/p\log(n/p))[/math]. Выбор порядка [math]p[/math] элементов в каждом процессоре произойдёт за [math]O(p)[/math],их сортировка произойдёт за [math]O(p^2\log(p^2))=O(p^2\log(p))[/math]. После обмена данными будет произведено слияние [math]p[/math] массивов в каждом процессоре, это займёт [math]O(n/p\log p)[/math]. В итоге мы получаем [math]O(n/p\log(n/p))+O(p^2\log(p))+O(n/p\log p)+O(p)[/math][math]=O(n/p\log(n/p)+p^2\log(p)+n/p\log p+p)=O(n/p\log(n/p))[/math]