Funnelsort - Funnelsort

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

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

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

Алгоритм

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

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

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

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

k-слияние

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

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

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

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

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

Анализ

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

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

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

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

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

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

Ленивая воронка

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

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

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

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

1. М. Фриго, С.Е. Лейзерсон, Х. Прокоп и С. Рамачандран. Алгоритмы без кеширования. В Материалы 40-го симпозиума IEEE по основам компьютерных наук (FOCS 99), стр. 285-297. 1999 г. Расширенная аннотация в IEEE, в Citeseer.
2. Харальд Прокоп. Алгоритмы, не обращающие внимания на кеш. Магистерская диссертация, Массачусетский технологический институт. 1999 г.
3. Бродал, Герт Стёльтинг; Фагерберг, Рольф (25 июня 2002 г.). «Незаметная очистка кеша». Автоматы, языки и программирование. Конспект лекций по информатике. 2380. Springer. С. 426–438. CiteSeerX  10.1.1.117.6837. Дои:10.1007/3-540-45465-9_37. ISBN  978-3-540-43864-9. . См. Также более длинный технический отчет.