Выборочная сортировка

Samplesort — это алгоритм сортировки , который представляет собой алгоритм «разделяй и властвуй», часто используемый в системах параллельной обработки. Обычные алгоритмы сортировки «разделяй и властвуй» разделяют массив на подинтервалы или сегменты. Затем сегменты сортируются по отдельности, а затем объединяются вместе. Однако если массив распределен неравномерно, производительность этих алгоритмов сортировки может значительно снизиться. Выборочная сортировка решает эту проблему, выбирая выборку размером s из n -элементной последовательности и определяя диапазон сегментов путем сортировки выборки и выбора элементов p -1 < s из результата. Эти элементы (называемые разделителями) затем делят массив на p сегментов примерно одинакового размера. Выборочная сортировка описана в статье 1970 года «Выборочная сортировка: выборочный подход к сортировке дерева минимальной памяти» У.Д. Фрейзера и А.К. МакКеллара.

Алгоритм

Выборочная сортировка — это обобщение быстрой сортировки . Если быстрая сортировка делит входные данные на две части на каждом этапе на основе одного значения, называемого опорной точкой, то выборочная сортировка вместо этого берет большую выборку из входных данных и соответствующим образом делит данные на сегменты. Как и быстрая сортировка, она затем рекурсивно сортирует сегменты.

Чтобы разработать реализацию выборочной сортировки, необходимо определиться с количеством сегментов p . Когда это будет сделано, фактический алгоритм работает в три этапа:

1. Отберите p -1 элементов со входа ( разделители ). Отсортируйте их; каждая пара соседних разделителей затем определяет сегмент .
2. Перебирайте данные в цикле, помещая каждый элемент в соответствующий сегмент. (Это может означать: отправить его на процессор в многопроцессорной системе.)
3. Отсортируйте каждое из ведер.

Полный отсортированный вывод представляет собой объединение сегментов.

Общая стратегия состоит в том, чтобы установить p равным количеству доступных процессоров. Затем данные распределяются между процессорами, которые выполняют сортировку сегментов, используя другой, последовательный алгоритм сортировки.

Псевдокод

Следующий листинг показывает вышеупомянутый трехшаговый алгоритм в виде псевдокода и показывает, как алгоритм работает в принципе. Далее A — это несортированные данные, k — коэффициент передискретизации, обсуждаемый позже, а p — количество разделителей.

function sampleSort(A[1..n], k, p)
    // if average bucket size is below a threshold switch to e.g. quicksort
    if n / k < threshold then smallSort(A) 
    /* Step 1 */
    select S = [S1, ..., S(p−1)k] randomly from // select samples
    sort S // sort sample
    [s0, s1, ..., sp−1, sp] <- [-∞, Sk, S2k, ..., S(p−1)k, ∞] // select splitters
    /* Step 2 */
    for each a in A
        find j such that sj−1 < a <= sj
        place a in bucket bj
    /* Step 3 and concatenation */
    return concatenate(sampleSort(b1), ..., sampleSort(bk))

Псевдокод отличается от исходного алгоритма Фрейзера и МакКеллара. В псевдокоде выборочная сортировка вызывается рекурсивно. Фрейзер и МакКеллар вызвали выборочную сортировку только один раз и использовали быструю сортировку во всех последующих итерациях.

Сложность

Сложность, указанная в нотации Big O , для распараллеленной реализации с $p$ процессоры:

Найдите разделители.

$O\left({\frac {n}{p}}+\log(p)\right)$

Отправьте в ведра.

$O(p)$ для чтения всех узлов

$O(\log(p))$ для вещания

$O\left({\frac {n}{p}}\log(p)\right)$ для двоичного поиска по всем ключам

$O\left({\frac {n}{p}}\right)$ отправить ключи в ведро

Сортировка ведер.

$O\left(c\left({\frac {n}{p}}\right)\right)$ где $c(n)$ — это сложность базового метода последовательной сортировки. Часто $c(n)=n\log(n)$.

Количество сравнений, выполняемых этим алгоритмом, приближается к информационному теоретическому оптимуму. $\log _{2}(n!)$ для больших входных последовательностей. В экспериментах, проведенных Фрейзером и МакКелларом, алгоритму требовалось на 15% меньше сравнений, чем быстрой сортировке.

Выборка данных

Данные могут быть отобраны различными методами. Некоторые методы включают в себя:

1. Выбирайте образцы, расположенные на равном расстоянии друг от друга.
2. Выберите случайно выбранные образцы.

Передискретизация

Коэффициент передискретизации определяет, во сколько раз больше элементов данных нужно извлечь в качестве выборок, прежде чем определять разделители. Цель состоит в том, чтобы получить хорошее представление о распределении данных. Если значения данных широко распределены и повторяющихся значений не так много, тогда достаточно небольшого коэффициента выборки. В других случаях, когда в распределении много дубликатов, потребуется больший коэффициент передискретизации. В идеальном случае после шага 2 каждое ведро содержит $n/p$ элементы. В этом случае сортировка ни одного сегмента не занимает больше времени, чем других, поскольку все сегменты имеют одинаковый размер.

После вытягивания $k$ раз больше образцов, чем необходимо, образцы сортируются. После этого разделители, используемые в качестве границ сегмента, представляют собой выборки в позиции $k,2k,3k,\dots ,(p-1)k$ последовательности образцов (вместе с $-\infty$ и $\infty$ как левая и правая границы для самого левого и самого правого сегментов соответственно). Это обеспечивает лучшую эвристику для хороших разделителей, чем просто выбор $p$ разветвители случайным образом.

Оценка размера ковша

По полученному размеру выборки можно оценить ожидаемый размер сегмента и особенно вероятность того, что блок превысит определенный размер. Ниже показано, что для коэффициента передискретизации $S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)$ вероятность того, что ни в одном ведре не окажется более $(1+\epsilon )\cdot {\dfrac {n}{p}}$ элементы больше, чем $1-{\dfrac {1}{n}}$.

Чтобы показать это, позвольте $\langle e_{1},\dots ,e_{n}\rangle$ быть входными данными в виде отсортированной последовательности. Чтобы процессор мог получить больше, чем $(1+\epsilon )\cdot n/p$ элементов, должна существовать подпоследовательность входных данных длины $(1+\epsilon )\cdot n/p$ максимум S , из которых отбирается выборок. Эти случаи составляют вероятность $P_{\text{fail}}$. Это можно представить как случайную величину: $$X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}$$

По ожидаемой стоимости $X_{i}$ держит: $$E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}$$

Это будет использоваться для оценки $P_{\text{fail}}$: $$P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))$$

Используя теперь оценку Чернова , можно показать: $$P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n$$

Много одинаковых ключей

В случае большого количества одинаковых ключей алгоритм проходит множество уровней рекурсии, на которых последовательности сортируются, поскольку вся последовательность состоит из одинаковых ключей. Этому можно противодействовать путем введения сегментов равенства. Элементы, равные опорной точке, сортируются в соответствующие сегменты равенства, которые можно реализовать только с помощью одной дополнительной условной ветви. Корзины равенства далее не сортируются. Это работает, поскольку ключи встречаются более чем $n/k$ времена, вероятно, станут поворотными.

Использование в параллельных системах

Пример параллельной Samplesort на $p=3$ процессоры и коэффициент передискретизации $k=3$.

Выборочная сортировка часто используется в параллельных системах, включая распределенные системы, такие как синхронные параллельные машины. Благодаря переменному количеству разделителей (в отличие от только одного центра в Quicksort ), Samplesort очень хорошо подходит и интуитивно понятен для распараллеливания и масштабирования. Более того, сортировка Samplesort также более эффективна с точки зрения кэширования, чем реализации, например, быстрой сортировки.

Распараллеливание реализуется путем разделения сортировки для каждого процессора или узла, где количество сегментов равно количеству процессоров. $p$. Выборочная сортировка эффективна в параллельных системах, поскольку каждый процессор получает примерно одинаковый размер корзины. $n/p$. Поскольку сегменты сортируются одновременно, процессоры завершат сортировку примерно в одно и то же время, поэтому процессору не приходится ждать других.

В распределенных системах разделители выбираются путем принятия $k$ элементов на каждом процессоре, сортируя полученные $kp$ элементы с распределенным алгоритмом сортировки, принимающим все $k$-th элемент и трансляция результата всем процессорам. Это стоит $T_{\text{sort}}(kp,p)$ для сортировки $kp$ элементы на $p$ процессоры, а также $T_{\text{allgather}}(p,p)$ для распространения $p$ выбранные сплиттеры для $p$ процессоры.

С помощью полученных разделителей каждый процессор помещает свои собственные входные данные в локальные сегменты. Это занимает ${\mathcal {O}}(n/p\log p)$ с бинарным поиском . После этого локальные сегменты перераспределяются по процессорам. Процессор $i$ получает местные ведра $b_{i}$ всех других процессоров и сортирует их локально. Распределение занимает $T_{\text{all-to-all}}(N,p)$ время, где $N$ это размер самого большого ведра. Локальная сортировка занимает $T_{\text{localsort}}(N)$.

Эксперименты, проведенные в начале 1990-х годов на суперкомпьютерах Connection Machine , показали, что выборочная сортировка особенно хороша при сортировке больших наборов данных на этих машинах, поскольку она требует небольших накладных расходов на межпроцессорную связь. На современных графических процессорах этот алгоритм может быть менее эффективным, чем его альтернативы.

Эффективная реализация Samplesort

Анимированный пример суперскалярной выборочной сортировки. На каждом этапе сравниваемые числа отмечаются синим цветом, а числа, которые в противном случае читаются или записываются, отмечаются красным.

Как описано выше, алгоритм выборочной сортировки разделяет элементы в соответствии с выбранными разделителями. Эффективная стратегия реализации предложена в статье «Суперскалярная выборочная сортировка». Предлагаемая в статье реализация использует два массива размером $n$ (исходный массив, содержащий входные данные и временный) для эффективной реализации. Следовательно, эта версия реализации не является алгоритмом на месте.

На каждом этапе рекурсии данные копируются в другой массив секционированным образом. Если данные находятся во временном массиве на последнем этапе рекурсии, данные копируются обратно в исходный массив.

Определение сегментов

В алгоритме сортировки, основанном на сравнении, операция сравнения является наиболее важной частью производительности. В Samplesort это соответствует определению сегмента для каждого элемента. Это требует $\log k$ время для каждого элемента.

Суперскалярная выборочная сортировка использует сбалансированное дерево поиска, которое неявно хранится в массиве t . Корень хранится в 0, левый преемник $t_{i}$ хранится в $t_{2i}$ и правильный преемник хранится по адресу $t_{2i+1}$. Учитывая дерево поиска t , алгоритм вычисляет номер сегмента j элемента $a_{i}$ следующим образом (при условии, что $a_{i}>t_{j}$ оценивается как 1, если это правда , и 0 в противном случае):

j := 1
repeat log2(p) times
    j := 2j + (a > tj)
j := j − p + 1

Поскольку количество сегментов k известно во время компиляции, может развернуть компилятор этот цикл. Операция сравнения реализуется с помощью предикатных инструкций . Таким образом, не происходит никаких ошибочных предсказаний ветвей , которые значительно замедлили бы операцию сравнения.

Разделение

Для эффективного разделения элементов алгоритму необходимо заранее знать размеры сегментов. Чтобы разделить элементы последовательности и поместить их в массив, нам нужно заранее знать размер сегментов. Наивный алгоритм мог бы подсчитать количество элементов каждого сегмента. Затем элементы можно было бы вставить в другой массив в нужном месте. Используя это, необходимо дважды определить сегмент для каждого элемента (один раз для подсчета количества элементов в блоке и один раз для их вставки).

Чтобы избежать удвоения сравнений, суперскалярная выборочная сортировка использует дополнительный массив. $o$ (называемый оракулом), который присваивает каждому индексу элементов сегменту. Сначала алгоритм определяет содержимое $o$ путем определения сегмента для каждого элемента и размеров сегмента, а затем помещения элементов в сегмент, определяемый $o$. Массив $o$ также требует затрат на складское пространство, но поскольку необходимо только хранить $n\cdot \log k$ бит, их стоимость мала по сравнению с размером входного массива.

Выборочная сортировка на месте

Ключевым недостатком эффективной реализации Samplesort, показанной выше, является то, что она не находится на месте и требует второго временного массива того же размера, что и входная последовательность во время сортировки. Эффективные реализации, например, быстрой сортировки, находятся на месте и, следовательно, более экономичны. Однако Samplesort также можно реализовать на месте.

Алгоритм на месте разделен на четыре этапа:

1. Выборка , которая эквивалентна выборке в вышеупомянутой эффективной реализации.
2. Локальная классификация на каждом процессоре, которая группирует входные данные в блоки так, что все элементы в каждом блоке принадлежат одному и тому же сегменту, но сегменты не обязательно непрерывны в памяти.
3. Перестановка блоков приводит блоки в глобально правильный порядок.
4. При очистке перемещаются некоторые элементы по краям сегментов.

Одним из очевидных недостатков этого алгоритма является то, что он считывает и записывает каждый элемент дважды: один раз на этапе классификации и один раз на этапе перестановки блоков. Однако алгоритм работает до трех раз быстрее, чем другие современные конкуренты, работающие на месте, и до 1,5 раз быстрее, чем другие современные последовательные конкуренты. Поскольку выборка уже обсуждалась выше, три последующих этапа будут более подробно описаны ниже.

Местная классификация

На первом этапе входной массив разбивается на $p$ полосы блоков одинакового размера, по одному на каждый процессор. Каждый процессор дополнительно выделяет $k$ буферы, имеющие одинаковый размер с блоками, по одному на каждый сегмент. После этого каждый процессор сканирует свою полосу и перемещает элементы в буфер соответствующего сегмента. Если буфер заполнен, он записывается в полосу процессоров, начиная с передней части. Всегда существует хотя бы один размер буфера пустой памяти, поскольку для того, чтобы буфер был записан (т.е. буфер полон), необходимо просканировать по крайней мере весь размер буфера элементов, превышающих количество записанных обратно элементов. Таким образом, каждый полный блок содержит элементы одного и того же сегмента. Во время сканирования отслеживается размер каждого сегмента.

Перестановка блоков

Сначала выполняется операция суммирования префиксов, которая вычисляет границы сегментов. Однако, поскольку на этом этапе перемещаются только полные блоки, границы округляются до кратного размера блока и выделяется один буфер переполнения. Прежде чем начать перестановку блоков, некоторые пустые блоки, возможно, придется переместить в конец корзины. После этого указатель записи $w_{i}$ устанавливается в начало сегмента $b_{i}$ подмассив для каждого сегмента и указатель чтения $r_{i}$ устанавливается на последний непустой блок в сегменте $b_{i}$ подмассив для каждого сегмента.

Чтобы ограничить конфликты в работе, каждому процессору назначается отдельный основной сегмент. $b_{prim}$ и два буфера подкачки, каждый из которых может содержать блок. На каждом этапе, если оба буфера подкачки пусты, процессор уменьшает указатель чтения. $r_{prim}$ своего основного сегмента и читает блок по адресу $r_{prim-1}$ и помещает его в один из своих буферов подкачки. После определения целевого сегмента $b_{dest}$ блока путем классификации первого элемента блока, это увеличивает указатель записи $w_{dest}$, читает блок по адресу $w_{dest-1}$ в другой буфер подкачки и записывает блок в корзину назначения. Если $w_{dest}>r_{dest}$, буферы подкачки снова пусты. В противном случае блок, оставшийся в буферах подкачки, должен быть вставлен в корзину назначения.

Если все блоки в подмассиве основного сегмента процессора находятся в правильном сегменте, следующий сегмент выбирается в качестве основного сегмента. Если процессор однажды выбрал все сегменты в качестве основных, обработка завершается.

Очистка

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

См. также

• Флэш-сортировка
• Быстрая сортировка

Внешние ссылки

Сортировка и производные Фрейзера и МакКеллара:

• Оригинальная статья Фрейзера и МакКеллара
• DOI.org
• DOI.org

Адаптировано для использования на параллельных компьютерах:

• http://citeseer.ist.psu.edu/91922.html
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214