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

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

Алгоритм

Обзор

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

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

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

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

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

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

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

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

def distribute(i, j, m: int) -> None:
    """Distribute through recursive divide-and-conquer."""
    if m == 1:
        copy_elems(i, j)
    else:
        distribute(i, j, m / 2)
        distribute(i + m / 2, j, m / 2)
        distribute(i, j + m / 2, m / 2)
        distribute(i + m / 2, j + m / 2, m / 2)

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

См. также

Ссылки

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