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

Funnelsort — это на основе сравнения алгоритм сортировки . Он похож на сортировку слиянием , но это алгоритм, не учитывающий кэш , разработанный для условий, когда количество элементов для сортировки слишком велико, чтобы поместиться в кэш , в котором выполняются операции. Он был представлен Маттео Фриго, Чарльзом Лейзерсоном , Харальдом Прокопом и Шридхаром Рамачандраном в 1999 году в контексте модели забвения кэша .

Математические свойства

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

Алгоритм

Базовый обзор

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

1. Разделить ввод на $N^{1/3}$ массивы размера $N^{2/3}$и рекурсивно сортировать массивы.
2. Объединить $N^{1/3}$ отсортированные последовательности с помощью $N^{1/3}$-слияние. (Этот процесс будет описан более подробно.)

Сортировка воронками аналогична сортировке слиянием в том смысле, что некоторое количество подмассивов сортируется рекурсивно, после чего на этапе слияния подмассивы объединяются в один отсортированный массив. Объединение выполняется с помощью устройства, называемого k-merger, которое описано в разделе ниже.

к -слияния

A k -слияние занимает $k$ отсортированные последовательности. При одном вызове k-слияния он выводит первый $k^{3}$ элементы отсортированной последовательности, полученные путем слияния k входных последовательностей.

На верхнем уровне воронкообразная сортировка использует $N^{1/3}$-слияние $N^{1/3}$ последовательности длины $N^{2/3}$и вызывает это слияние один раз.

-слияние K строится рекурсивно из ${\sqrt {k}}$-слияния. Он состоит из ${\sqrt {k}}$ вход ${\sqrt {k}}$-слияния $I_{1},I_{2},\ldots ,I_{\sqrt {k}}$и один выход ${\sqrt {k}}$-слияние $O$. входов k разделены на ${\sqrt {k}}$ наборы ${\sqrt {k}}$ входы каждый. Каждый из этих наборов является входом для одного из входных слияний. Выход каждого входного слияния подключен к буферу, FIFO очереди , которая может хранить $2k^{3/2}$ элементы. Буферы реализованы как циклические очереди .Результаты ${\sqrt {k}}$ буферы подключаются ко входам выходного слияния $O$. Наконец, вывод $O$ является результатом всего k-слияния.

В этой конструкции любое входное слияние выводит только $k^{3/2}$ элементы одновременно, но буфер, в который он выводит, имеет вдвое больше места. Это сделано для того, чтобы входное слияние можно было вызвать только тогда, когда в его буфере недостаточно элементов, но при вызове оно выводило сразу много элементов (а именно, $k^{3/2}$ из них).

K - слияние рекурсивно работает следующим образом. Для вывода $k^{3}$ элементы, он рекурсивно вызывает слияние выходных данных $k^{3/2}$ раз. Однако прежде чем он позвонит $O$, он проверяет все свои буферы, заполняя каждый из них, который заполнен менее чем наполовину. Чтобы заполнить i-й буфер, он рекурсивно вызывает соответствующее слияние входных данных. $I_{i}$ один раз. Если это невозможно сделать (из-за исчерпания входных данных при слиянии), этот шаг пропускается. Поскольку этот вызов выводит $k^{3/2}$ элементов, буфер содержит как минимум $k^{3/2}$ элементы. В конце всех этих операций k -слияние выдало первый $k^{3}$ его входных элементов в отсортированном порядке.

Анализ

Большая часть анализа этого алгоритма вращается вокруг анализа пространства и сложности промахов в кэше k-слияния.

Первое важное ограничение состоит в том, что k-слияние может быть уложено в $O(k^{2})$ космос. Чтобы увидеть это, мы позволим $S(k)$ обозначаем пространство, необходимое для k-слияния. Чтобы соответствовать $k^{1/2}$ буферы размера $2k^{3/2}$ берет $O(k^{2})$ космос. Чтобы соответствовать ${\sqrt {k}}+1$ меньшие буферы занимают $({\sqrt {k}}+1)S({\sqrt {k}})$ космос. Таким образом, пространство удовлетворяет рекуррентности $S(k)=({\sqrt {k}}+1)S({\sqrt {k}})+O(k^{2})$. Это повторение имеет решение $S(k)=O(k^{2})$.

Отсюда следует, что существует положительная константа $\alpha$ так что проблема размера не более $\alpha {\sqrt {Z}}$ полностью помещается в кэш, а это означает, что он не вызывает дополнительных промахов в кэше.

Сдача в аренду $Q_{M}(k)$ обозначают количество промахов в кэше, вызванных вызовом k-слияния, можно показать, что $Q_{M}(k)=O((k^{3}\log _{Z}k)/L).$ Это делается с помощью индукционного рассуждения. Он имеет $k\leq \alpha {\sqrt {Z}}$ в качестве базового случая. Для большего k мы можем ограничить количество раз a ${\sqrt {k}}$-слияние называется. Выходное слияние называется именно $k^{3/2}$ раз. Общее количество вызовов при входных слияниях не более $k^{3/2}+2{\sqrt {k}}$. Это дает общую границу $2k^{3/2}+2{\sqrt {k}}$ рекурсивные вызовы. Кроме того, алгоритм проверяет каждый буфер на предмет необходимости заполнения. Это делается на ${\sqrt {k}}$ буферизует каждый шаг для $k^{3/2}$ шаги, ведущие к максимуму $k^{2}$ кэш промахивается для всех проверок.

Это приводит к рецидиву $Q_{M}(k)\leq (2k^{3/2}+2{\sqrt {k}})Q_{M}({\sqrt {k}})+k^{2}$, которое, как можно показать, имеет решение, указанное выше.

Наконец, общий кэш отсутствует $Q(N)$ ибо весь сорт можно проанализировать. Это удовлетворяет повторяемости $Q(N)=N^{1/3}Q(N^{2/3})+Q_{M}(N^{1/3}).$ Можно показать, что это имеет решение $Q(N)=O((N/L)\log _{Z}N).$

Ленивая сортировка воронками

Ленивая сортировка воронками — это модификация сортировки воронок, представленная Гертом Столтингом Бродалем и Рольфом Фагербергом в 2002 году. Модификация заключается в том, что при вызове слияния не требуется заполнять каждый из своих буферов. Вместо этого он лениво заполняет буфер только тогда, когда он пуст. Эта модификация имеет то же асимптотическое время выполнения и передачу памяти, что и исходная воронкообразная сортировка, но имеет применение в алгоритмах, не учитывающих кэш, для решения задач вычислительной геометрии в методе, известном как очистка распределения.

См. также

• Алгоритм, не обращающий внимания на кэш
• Сортировка распределения без учета кэша
• Внешняя сортировка