Сортировка распределения без учета кэша - Cache-oblivious distribution sort

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Май 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к Сделайте это понятным для неспециалистов, не снимая технических деталей. (Май 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

Тайник-не обращая внимания сортировка по распределению это на основе сравнения алгоритм сортировки. Это похоже на быстрая сортировка, но это алгоритм, не обращающий внимания на кеш, разработанный для настройки, в которой количество элементов для сортировки слишком велико, чтобы поместиться в тайник где производятся операции. в модель внешней памяти, количество передач памяти, необходимое для выполнения своего рода ${ displaystyle N}$ элементы на машине с размером кэша ${ displaystyle Z}$ и строки кэша длиной ${ displaystyle L}$ является ${ Displaystyle О ({ гидроразрыва {N} {L}} log _ {Z} N)}$, в предположении высокого кеша, что ${ Displaystyle Z = Omega (L ^ {2})}$. Было показано, что это количество передач памяти является асимптотически оптимальным для сортировок сравнения. Эта сортировка распределения также обеспечивает асимптотически оптимальную сложность времени выполнения ${ Displaystyle Theta (N log N)}$.

Алгоритм

Обзор

Сортировка распределения работает с непрерывным массивом ${ displaystyle N}$ элементы. Для сортировки элементов он выполняет следующие действия:

1. Разбейте массив на ${ displaystyle { sqrt {N}}}$ смежные подмассивы размера ${ displaystyle { sqrt {N}}}$, и рекурсивно сортировать каждый подмассив.
2. Распределите элементы отсортированных подмассивов по ${ displaystyle q leq { sqrt {N}}}$ ведра ${ Displaystyle B_ {1}, B_ {2}, ldots, B_ {q}}$ каждый размером не более ${ displaystyle 2 { sqrt {N}}}$ так что для каждого i от 1 до q-1 каждый элемент ведра ${ displaystyle B_ {i}}$ не больше любого элемента в ${ displaystyle B_ {i + 1}.}$ Этот этап распределения является основным этапом этого алгоритма и более подробно описан ниже.
3. Рекурсивно отсортируйте каждую корзину.
4. Выведите конкатенацию сегментов.

Шаг распределения

Как упоминалось в шаге 2 выше, цель шага распределения - распределить отсортированные подмассивы по q корзинам. ${ displaystyle B_ {1}, B_ {2}, ldots, B_ {q}.}$ Алгоритм шага распределения поддерживает два инварианта. Во-первых, размер каждого ведра не должен превышать ${ displaystyle 2 { sqrt {N}}}$ в любое время и любой элемент в ведре ${ displaystyle B_ {i}}$ не больше любого элемента в ведре ${ displaystyle B_ {i + 1}.}$ Во-вторых, у каждого сегмента есть связанный вращаться, значение, превышающее все элементы в сегменте.

Первоначально, алгоритм начинается с одного пустого ковша с шарниром ${ displaystyle infty}$. По мере заполнения ведер он создает новые ведра, разделяя ведро на два, когда оно будет переполнено (при наличии хотя бы ${ displaystyle (2 { sqrt {N}} + 1)}$ размещенные в нем элементы). Разделение выполняется путем выполнения нахождение медианы линейного времени алгоритм и разбиение на основе этой медианы. Поворот нижнего сегмента будет установлен на найденное медианное значение, а стержень верхнего сегмента будет установлен на то же значение, что и сегмент до разделения. В конце этапа распределения все элементы находятся в корзинах, и два инварианта по-прежнему сохраняются.

Для этого каждый подмассив и сегмент будут иметь связанное с ними состояние. Состояние подмассива состоит из индекса следующий следующего элемента, который будет считан из подмассива, и номер сегмента bnum указывая, в какой индекс сегмента следует скопировать элемент. Условно, ${ displaystyle bnum = infty}$ если все элементы в подмассиве были распределены. (Обратите внимание: когда мы разделяем ведро, мы должны увеличивать все bnum значения всех подмассивов, bnum значение больше, чем индекс разделенного сегмента.) Состояние сегмента состоит из значения его поворота и количества элементов, находящихся в настоящее время в сегменте.

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

Вместо этого этап распределения выполняется в рекурсивной схеме «разделяй и властвуй». Шаг будет выполнен как вызов функции раздавать, который принимает три параметра i, j и m. раздавать(i, j, m) будет распределять элементы с i-го по (i + m-1) -ый подмассивы по сегментам, начиная с ${ displaystyle B_ {j}}$. В качестве предварительного условия требуется, чтобы каждый подмассив r в диапазоне ${ Displaystyle я, ldots, я + м-1}$ имеет свой ${ displaystyle bnum [r] geq j}$. Выполнение раздавать(i, j, m) гарантирует, что каждый ${ displaystyle bnum [r] geq j + m}$. Весь шаг распределения составляет раздавать${ displaystyle (1,1, { sqrt {N}})}$. Псевдокод для реализации раздачи показан ниже:

def раздавать(я, j, м: int) -> Никто:    "" "Распространяйте через рекурсивный принцип разделяй и властвуй." ""    если м == 1:        copy_elems(я, j)    еще:        раздавать(я, j, м / 2)        раздавать(я + м / 2, j, м / 2)        раздавать(я, j + м / 2, м / 2)        раздавать(я + м / 2, j + м / 2, м / 2)

В базовом случае, когда m = 1, вызывается подпрограмма copy_elems. В этом базовом случае все элементы из подмассива i, принадлежащие корзине j, добавляются сразу. Если это приводит к тому, что сегмент j имеет слишком много элементов, он разбивает сегмент с помощью процедуры, описанной ранее.

Смотрите также

• Алгоритм без кеширования
• Funnelsort
• Внешняя сортировка

Рекомендации

• Харальд Прокоп. Алгоритмы, не обращающие внимания на кеш. Магистерская диссертация, Массачусетский технологический институт. 1999 г.