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

Перейти к навигации Перейти к поиску
Строка 16: Строка 16:


== Основные результаты ==
== Основные результаты ==
В модели ввода-вывода были доказаны точные верхняя и нижняя границы для задачи сортировки и для задачи перестановки массива [1]. В частности, было доказано, что сортировка требует переноса @(^rlogM/B ^) блоков памяти, а перестановка массива – @(min{JV, NB logM/B NBg) блоков. Поскольку нижние границы для модели ввода-вывода соблюдаются также и в модели без явного задания параметров кэша, нижние границы из работы [1] немедленно задают нижнюю границу в Q(^\ogM/B ^) переносов содержимого памяти для сортировки без явного задания параметров кэша и Q(min{N,^\ogM/B ^}) переносов – для перестановки массива без явного задания параметров кэша. Верхняя граница из [1] не может быть применена к модели без явного задания параметров кэша, поскольку эти алгоритмы используют значения параметров B и M.
В модели ввода-вывода были доказаны точные верхняя и нижняя границы для задачи сортировки и для задачи перестановки массива [1]. В частности, было доказано, что сортировка требует переноса <math>\Theta(\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> блоков памяти, а перестановка массива – <math>\Theta(min \{ N, \frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M} \})</math> блоков. Поскольку нижние границы для модели ввода-вывода соблюдаются также и в модели без явного задания параметров кэша, нижние границы из работы [1] непосредственно задают нижнюю границу в <math>\Omega (\frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M})</math> переносов содержимого памяти для сортировки без явного задания параметров кэша и <math>\Omega (min \{ N, \frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{M} \} )</math> переносов – для перестановки массива без явного задания параметров кэша. Верхняя граница из [1] не может быть применена к модели без явного задания параметров кэша, поскольку эти алгоритмы используют значения параметров B и M.




Бинарная сортировка слиянием (Mergesort) выполняет O(N log2 N) сравнений, но если ее анализировать в рамках модели без явного задания параметров кэша, она производит O(NB log2 MN) переносов блоков памяти, что в ©(log f) раз отличается от значения нижней границы (предполагается рекурсивная реализация бинарной сортировки слиянием, чтобы значение M входило в знаменатель компонента log WM границы количества переносов блоков). Еще одним алгоритмом сортировки на базе сравнения является классический алгоритм быстрой сортировки (Quicksort), предложенный Хоаром в 1962 году [9], который выполняет ожидаемые O(Nlog2 N) сравнений и ожидаемые O(NBlog2 MN) переносов блоков памяти. Оба этих алгоритма обеспечивают достаточно высокую производительность в смысле количества переносов блоков благодаря тому, что они основаны на повторяющемся сканировании массивов – не использующий подобный подход алгоритм сортировки кучей (Heapsort) [10] демонстрирует весьма слабую эффективность в виде @(JVlog2 MN) переносов блоков памяти. В модели ввода-вывода оптимальная эффективность 0(^logM/B ^) достигается в результате обобщения бинарной сортировки слиянием до @(^)-сторонней сортировки слиянием [1].
''Бинарная сортировка слиянием (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] демонстрирует весьма слабую эффективность в виде @(JVlog2 MN) переносов блоков памяти. В модели ввода-вывода оптимальная эффективность 0(^logM/B ^) достигается в результате обобщения бинарной сортировки слиянием до @(^)-сторонней сортировки слиянием [1].




Источник — http://pco.iis.nsk.su/wega/index.php/Сортировка_без_явного_задания_параметров_кэша