4551
правка
Сортировка без явного задания параметров кэша: различия между версиями
Материал из WEGA
Сортировка без явного задания параметров кэша (посмотреть исходный код)
Версия от 16:04, 11 марта 2017
, 11 марта 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
''Бинарная сортировка слиянием (Mergesort)'' выполняет <math>O(N \; log_2 \; N)</math> сравнений, но если ее анализировать в рамках модели без явного задания параметров кэша, она производит <math>O(\frac{N}{B} \; log_2 \; \frac{N}{M})</math> переносов блоков памяти, что в <math>\Theta(log \; \frac{M} {B})</math> раз отличается от значения нижней границы (предполагается рекурсивная реализация бинарной сортировки слиянием, чтобы значение M входило в знаменатель компонента log N/M границы количества переносов блоков). Еще одним алгоритмом сортировки на базе сравнения является классический алгоритм быстрой сортировки (Quicksort), предложенный Хоаром в 1962 году [9], который выполняет ожидаемые <math>O(N \; log_2 \; N)</math> сравнений и ожидаемые <math>O(\frac{N}{B} \; log_2 \; \frac{N}{M})</math> переносов блоков памяти. Оба этих алгоритма обеспечивают достаточно высокую производительность в смысле количества переносов блоков благодаря тому, что они основаны на повторяющемся сканировании массивов – не использующий подобный подход алгоритм сортировки кучей (Heapsort) [10] демонстрирует весьма слабую эффективность в виде | ''Бинарная сортировка слиянием (Mergesort)'' выполняет <math>O(N \; log_2 \; N)</math> сравнений, но если ее анализировать в рамках модели без явного задания параметров кэша, она производит <math>O(\frac{N}{B} \; log_2 \; \frac{N}{M})</math> переносов блоков памяти, что в <math>\Theta(log \; \frac{M}{B})</math> раз отличается от значения нижней границы (предполагается рекурсивная реализация бинарной сортировки слиянием, чтобы значение M входило в знаменатель компонента log N/M границы количества переносов блоков). Еще одним алгоритмом сортировки на базе сравнения является классический алгоритм быстрой сортировки (Quicksort), предложенный Хоаром в 1962 году [9], который выполняет ожидаемые <math>O(N \; log_2 \; N)</math> сравнений и ожидаемые <math>O(\frac{N}{B} \; log_2 \; \frac{N}{M})</math> переносов блоков памяти. Оба этих алгоритма обеспечивают достаточно высокую производительность в смысле количества переносов блоков благодаря тому, что они основаны на повторяющемся сканировании массивов – не использующий подобный подход ''алгоритм сортировки кучей (Heapsort)'' [10] демонстрирует весьма слабую эффективность в виде <math>\Theta (N \; log_2 \; \frac{N}{M})</math> переносов блоков памяти. В модели ввода-вывода оптимальная эффективность <math>O(\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> достигается в результате обобщения бинарной сортировки слиянием до <math>\Theta (\frac{M}{B})</math>-сторонней сортировки слиянием [1]. | ||
Фриго и др [8] представили два алгоритма сортировки без явного задания параметров кэша, которые также могут использоваться для перестановки массива элементов. Первый алгоритм [8, глава 4] носит название сортировки воронкой (Funnelsort) и напоминает классическую бинарную сортировку слиянием; второй алгоритм [8, глава 5] является алгоритмом сортировки распределением. Оба алгоритма обеспечивают оптимальные O( | Фриго и др [8] представили два алгоритма сортировки без явного задания параметров кэша, которые также могут использоваться для перестановки массива элементов. Первый алгоритм [8, глава 4] носит название ''сортировки воронкой (Funnelsort)'' и напоминает классическую бинарную сортировку слиянием; второй алгоритм [8, глава 5] является алгоритмом ''сортировки распределением''. Оба алгоритма обеспечивают ''оптимальные'' <math>O(\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> переносов блоков памяти при условии соблюдения ''предположения о высоте кэша'' <math>M = \Omega (B^2) \;</math>. | ||
'''Сортировка воронкой''' | '''Сортировка воронкой''' | ||
| Строка 28: | Строка 29: | ||
Базовая идея алгоритма сортировки воронкой заключается в перегруппировке процесса сортировки, выполняемого алгоритмом бинарной сортировки слиянием, таким образом, чтобы обработанные данные хранились «локально». Это достигается за счет применения двух базовых принципов: | Базовая идея алгоритма сортировки воронкой заключается в перегруппировке процесса сортировки, выполняемого алгоритмом бинарной сортировки слиянием, таким образом, чтобы обработанные данные хранились «локально». Это достигается за счет применения двух базовых принципов: | ||
(1) Рекурсия верхнего уровня, которая разбивает входной массив на | (1) Рекурсия верхнего уровня, которая разбивает входной массив на <math>N^{1/3} \;</math> последовательностей размера <math>N^{2/3} \;</math>, рекурсивно выполняет сортировку воронкой этих последовательностей и затем сливает полученные подпоследовательности при помощи алгоритма <math>N^{1/3} \;</math>-слияния. | ||
(2) ''Алгоритм k-слияния'' определяется рекурсивным образом. Он выполняет бинарное слияние k входных последовательностей согласно продуманному графику с соответствующим рекурсивным расположением данных в памяти с использованием буферов для хранения приостановленных процессов слияния (см. рис. 1). Были выполнены два последовательных упрощения без ухудшения асимптотического количества переносов блоков памяти. В работе [3] было доказано, что бинарное слияние может выполняться «ленивым» образом, что упрощает планирование слияния. В работе [5] было замечено, что рекурсивное расположение элементов k-слияния не является обязательным. Достаточно того, чтобы элемент k-слияния хранился в последовательном массиве, т.е. буферы могут располагаться в произвольном порядке, что упрощает алгоритм сборки для k-слияния. | |||
