4551
правка
Сортировка без явного задания параметров кэша: различия между версиями
Перейти к навигации
Перейти к поиску
Сортировка без явного задания параметров кэша (посмотреть исходный код)
Версия от 15:52, 11 марта 2017
, 11 марта 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
== Основные результаты == | == Основные результаты == | ||
В модели ввода-вывода были доказаны точные верхняя и нижняя границы для задачи сортировки и для задачи перестановки массива [1]. В частности, было доказано, что сортировка требует переноса | В модели ввода-вывода были доказаны точные верхняя и нижняя границы для задачи сортировки и для задачи перестановки массива [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 | ''Бинарная сортировка слиянием (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]. | ||