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

Франческини в [7] показал, как неявно выполнить оптимальную сортировку без задания параметров кэша, используя только O(1) памяти – т.е. все данные хранятся во входном массиве, за исключением O(1) дополнительных слов с информацией. В частности, выходной массив является простой перестановкой входного.

'''Теорема 1 ([4], следствие 3). Пусть <math>B_1 = 1 \;</math> и <math>B_2 = \frac{M}{2} \;</math>. Для любого алгоритма сортировки на базе сравнения, выполняющегося без явного задания параметров кэша, примем за <math>t_1 \;</math> и <math>t_2 \;</math> верхние границы количества операций ввода-вывода, произведенных над блоками размеров <math>B_1 \;</math> и <math>B_2 \;</math>. Если для вещественного числа <math>d \ge 0 \;</math> выполняется условие <math>t_2 = d \cdot \frac{N}{B^2} \; log_{ \frac{M}{B^2} } \; \frac{N}{B^2}</math>, то <math>t_1 > \frac{1}{8} \cdot N \; log_2 \; \frac{N}{M}</math>.'''

Теорема доказывает, что сортировка на базе сравнения, выполняемая без явного задания параметров кэша и без предположения о высоте кэша, не может сравниться по эффективности с алгоритмами на базе модели ввода-вывода, в которой значения M и В известны алгоритму. Кроме того, из нее естественным образом следует, что если алгоритм без явного задания параметров кэша должен быть оптимальным по вводу-выводу для случая <math>B = \frac{M}{2} \;</math>, то наилучшим вариантом будет бинарная сортировка слияния: любой другой алгоритм будет также на <math>\Theta (log \; M)</math> отличаться от оптимальной границы количества переносов блоков для случая <math>M \gg B \;</math>.

Для родственной задачи перестановки массива следующая теорема утверждает, что для всех возможных предположений о высоте кэша <math>B \le M^{ \delta} \;</math> не существует алгоритма перестановки без явного задания параметров кэша с границей количества переносов блоков (даже для среднего случая), соответствующей нижней границе для наихудшего случая в модели ввода-вывода.

'''Теорема 2 ([4], теорема 2). Для всех <math>\delta > 0 \;</math> не существует алгоритма перестановки без явного задания параметров кэша, который для всех <math>M \ge 2B \;</math> и <math>1 \le B \le M^{ \delta} \;</math> демонстрирует <math>O(min \{ N, \frac{N}{B} \; log_{\frac{M}{B}} \; \frac{N}{B} \} )</math> операций ввода-вывода, усредненных по всем возможным перестановкам размера N.'''

К сортировке без явного задания параметров кэша могут сведены многие задачи. В частности, Ардж и др. [2] разработали очередь с приоритетами без явного задания параметров кэша, основанную на сведении к сортировке. Кроме того, они показали, как применить очередь с приоритетами без явного задания параметров кэша для решения совокупности графовых задач, включая ранжирование списков, базисное возможное решение (BFS), DFS и минимальные остовные деревья.

Бродаль и Фагерберг [3] показали, как модифицировать ленивый алгоритм сортировки воронкой без явного задания параметров кэша для решения некоторых задач вычислительной геометрии, включая пересечение ортогональных проекций отрезков прямых, нахождение всех ближайших соседей, задачу 3D maxima и пакетные ортогональные запросы диапазона. Все эти задачи могут быть решены при помощи вычислительного процесса, очень похожего на бинарную сортировку слиянием с дополнительными настройками в зависимости от задачи. Данная общая схема решения задач вычислительной геометрии носит название ''распределенного сметания''.

Детальное экспериментальное исследование алгоритма сортировки воронкой Funnelsort без явного задания параметров кэша было выполнено в [5]. Основной результат исследования в [5] заключается в том, что грамотно реализованный алгоритм сортировки без явного задания параметров кэша может работать быстрее, чем настроенная реализация алгоритма быстрой сортировки Quicksort, для размеров входных данных, существенно превышающих объем оперативной памяти. Эта реализация также является не менее быстрой, чем недавняя реализация с явным заданием параметров кэша, включенная в тестирование. На дисковой памяти разница с алгоритмами быстрой сортировки и алгоритмами с явным заданием параметров кэша еще заметнее, хотя рассматриваемый алгоритм работает медленнее алгоритмов многосторонней сортировки слиянием Mergesort, оптимизированных для внешней памяти – таких как TPIE [6].