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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Сортировка PSRS ==
 
== Сортировка PSRS ==
 +
=== Описание ===
 +
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная разработана Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет три преимущества по сравнению с быстрой сортировкой. Она сохраняет размер списка более сбалансированным на протяжении всего процесса, что позволяет избегать повторных перестановок ключей и не требует, чтобы число процессов было кратно двойке.
 
=== Алгоритм ===
 
=== Алгоритм ===
Для начала надо разделить входные данные на 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,\frac {n}  {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex> и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами <tex>\displaystyle 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>. Далее с сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
 
=== Пример ===
 
=== Пример ===
Количество элементов 27, количество процессоров 3.
+
Количество элементов <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>:
 
Исходный набор данных <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"| Описание этапа
 
!style="background-color:#EEE"| 1 процессор
 
!style="background-color:#EEE"| 1 процессор
 
!style="background-color:#EEE"| 2 процессор
 
!style="background-color:#EEE"| 2 процессор
Строка 27: Строка 30:
 
|}
 
|}
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание команды
+
!style="background-color:#EEE"| Описание этапа
 
!style="background-color:#EEE"| Данные
 
!style="background-color:#EEE"| Данные
 
|-
 
|-
Строка 43: Строка 46:
 
|}
 
|}
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| Описание команды
+
!style="background-color:#EEE"| Описание этапа
 
!style="background-color:#EEE"|             
 
!style="background-color:#EEE"|             
 
!style="background-color:#EEE"| 1 процессор
 
!style="background-color:#EEE"| 1 процессор
Строка 88: Строка 91:
 
|}
 
|}
 
=== Анализ ===
 
=== Анализ ===
При <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(\displaystyle \frac {n}{p\log(n/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>\displaystyle\frac {n}{p^2}</tex>< а merge двух массивов выполняется за сумму их длин, это займёт <tex>\displaystyle O(\sum \limits_{k=1}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2})=O(n)</tex>. В итоге мы получаем <tex>O(\frac {n}{p\log(n/p)})+O(p^2\log(p))+O(n)+O(p)</tex><tex>\displaystyle =O(\frac {n}{p\log(n/p)}+p^2\log(p)+\frac {n}{p\log p}+p)=O(n)</tex>.
 +
=== См. также ===
 +
[[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]

Версия 03:35, 11 июня 2014

Сортировка PSRS

Описание

Parallel Sorting by Regular Sampling — параллельная сортировка, разработанная разработана Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет три преимущества по сравнению с быстрой сортировкой. Она сохраняет размер списка более сбалансированным на протяжении всего процесса, что позволяет избегать повторных перестановок ключей и не требует, чтобы число процессов было кратно двойке.

Алгоритм

Для начала надо разделить входные данные на n равных частей, где [math]n[/math] — количество процессоров. Далее запустить алгоритм быстрой сортировки на каждом из процессоров. Далее мы должны сформировать массив элементами которого будут элементы из каждого процессора с индексами [math]0,\frac {n} {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}[/math] и элементы стоящие в процессорах левее выбранных. Далее на нам потребуется отсортировать полученный массив и выбрать из него p разделителей с индексами [math]\displaystyle p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1[/math]. Теперь разделим данные в процессорах согласно полученному массиву разделителей. Пусть [math]a_1, a_2,..., a_j[/math] разделители, элементы в каждом процессоре разобьём не группы элементов, попадающие в соответствующие полу-интервалы [math](-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)[/math]. Далее с сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.

Пример

Количество элементов [math]27[/math], количество процессоров [math]3[/math]. Исходный набор данных [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(\displaystyle \frac {n}{p\log(n/p)})[/math]. Выбор порядка [math]p[/math] элементов в каждом процессоре произойдёт за [math]O(p)[/math],их сортировать мы будем с помощью быстрой сортировки, а так же учитывая что их количество порядка [math]p[/math], то можно сказать, что они сортируются за [math]O(p^2\log(p^2))=O(p^2\log(p))[/math]. После обмена данными будет произведено слияние [math]p[/math] массивов в каждом процессоре, учитывая что при равномерном распределении данных длина сливаемых массивов будет [math]\displaystyle\frac {n}{p^2}[/math]< а merge двух массивов выполняется за сумму их длин, это займёт [math]\displaystyle O(\sum \limits_{k=1}^{p} \frac {k \cdot n}{p^2})=O(\frac {n \cdot p \cdot (p+1)}{2p^2})=O(n)[/math]. В итоге мы получаем [math]O(\frac {n}{p\log(n/p)})+O(p^2\log(p))+O(n)+O(p)[/math][math]\displaystyle =O(\frac {n}{p\log(n/p)}+p^2\log(p)+\frac {n}{p\log p}+p)=O(n)[/math].

См. также

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