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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Анализ)
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
== Описание ==
 
== Описание ==
Parallel Sorting by Regular Sampling {{---}} параллельная сортировка, разработанная Ханмао Ши, Рисажем Канселом и Джонатаном Шеффером в 1992 году. Имеет два преимущества по сравнению с быстрой сортировкой:  
+
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>. Далее сольём соответствующие группы, которые отсортированы по в возрастанию, в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
+
* Начало.
 +
* '''Шаг 1.''' Исходный массив в <tex>n</tex> элементов разделим поровну между <tex>p</tex> процессорами.
 +
* '''Шаг 2.''' На каждом процессоре запускам [[Быстрая сортировка|быструю сортировку]].
 +
* '''Шаг 3.''' Формируем вспомогательный массив из элементов каждого процессора под индексами <tex dpi=145>0,\frac {n}  {p^2}, \frac {2n}{p^2},...,\frac {(p-1)n}{p^2}</tex>.
 +
* '''Шаг 4.''' Сортируем вспомогательный массив с помощью быстрой сортировки.
 +
* '''Шаг 5.''' Формируем массив разделителей из элементов вспомогательного массива под индексами <tex dpi=145>  p + [\frac {p} {2}] - 1, 2p + [\frac {p}{2}] - 1,...,(p-1)p + [\frac {p}{2}] - 1</tex>.
 +
* '''Шаг 6.''' Делим данные в процессорах с помощью массива разделителей следующим образом. Пусть <tex>a_1, a_2,..., a_j</tex> {{---}} разделители. Тогда данные в каждом процессоре разобьём на группы элементов,                             попадающие в соответствующие полуинтервалы <tex>(-\infty,a_1],(a_1,a_2],...,(a_j,+\infty)</tex>.
 +
* '''Шаг 7.''' Сливаем соответствующие группы элементов в массивы. Слияние будем производить поочерёдно, то есть сначала сольём первую группу со второй потом результат с третей и так далее. В итоге получим отсортированный набор данных.
 +
* '''Шаг 8.''' Данные из процессоров поочерёдно записываем в исходный массив. Данные отсортированы.
 +
* Конец.
  
 
== Пример ==
 
== Пример ==
Строка 87: Строка 96:
 
|style="background-color:#FFF;padding:2px 10px"| 72 84 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"| После слияния
 
|style="background-color:#FFF;padding:2px 10px"| 6 12 14   
 
|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"| 15 20 21
Строка 100: Строка 109:
  
 
== Анализ ==
 
== Анализ ==
При <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 dpi=145> 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>.
+
При <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>\mathrm {merge} </tex> займёт <tex dpi=145> 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)+n+p)=O(\frac {n\log(n/p)}{p})</tex>.
  
 
== См. также ==
 
== См. также ==
 
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 
* [[Многопоточная сортировка слиянием|Многопоточная сортировка слиянием]]
 
+
* [[Быстрая сортировка|Быстрая сортировка]]
 +
== Источники информации ==
 +
* [https://wiki.engr.illinois.edu/download/attachments/99155993/Sort+ParaProg(Quinn)chpt14.5.pdf?version=1&modificationDate=1203641170000| Статья о PSRS]
 +
* [http://users.cms.caltech.edu/~cs284/lectures/29oct97/sld003.htm| Презентация]
 +
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Сортировка]]
 
[[Категория:Сортировка]]
 +
[[Категория: Многопоточные сортировки]]

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

Описание

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

  • сохраняет размер списка более сбалансированным на протяжении всего процесса
  • избегает повторных перестановок ключей

Алгоритм

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

Пример

Количество элементов [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( \frac {n\log(n/p)}{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]\frac {n}{p^2}[/math], а [math]\mathrm {merge} [/math] двух массивов выполняется за сумму их длин. Поэтому [math]\mathrm {merge} [/math] займёт [math] 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)[/math].

Откуда получаем итоговую асимптотику:

[math] O(\frac {n\log(n/p)}{p})+O(p^2\log(p))+O(n)+O(p)[/math]

Что равно:

[math]O(\frac {n\log(n/p)}{p}+p^2\log(p)+n+p)=O(\frac {n\log(n/p)}{p})[/math].

См. также

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