WikiDer > Сортировка распределения без учета кэша

Cache-oblivious distribution sort

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

Алгоритм

Обзор

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

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


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

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

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

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

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

Вместо этого этап распределения выполняется в рекурсивной схеме «разделяй и властвуй». Шаг будет выполнен как вызов функции раздавать, который принимает три параметра i, j и m. раздавать(i, j, m) будет распределять элементы с i-го по (i + m-1) -ый подмассивы по сегментам, начиная с . В качестве предварительного условия требуется, чтобы каждый подмассив r в диапазоне имеет свой . Выполнение раздавать(i, j, m) гарантирует, что каждый . Весь шаг распределения составляет раздавать. Псевдокод для реализации раздачи показан ниже:

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 имеет слишком много элементов, он разбивает сегмент с помощью процедуры, описанной ранее.

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

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