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

(2) Алгоритм k-слияния определяется рекурсивным образом. Он выполняет бинарное слияние k входных последовательностей согласно продуманному графику с соответствующим рекурсивным расположением данных в памяти с использованием буферов для хранения приостановленных процессов слияния (см. рис. 1). Были выполнены два последовательных упрощения без ухудшения асимптотического количества переносов блоков памяти. В работе [3] было доказано, что бинарное слияние может выполняться «ленивым» образом, упрощая планирование слияния. В работе [5] было замечено, что рекурсовное расположение элементов k-слияния не является обязательным. Достаточно того, чтобы элемент k-слияния хранился в последовательном массиве, т.е. буферы могут располагаться в произвольном порядке, что упрощает алгоритм сборки для k-слияния.

Для родственной задачи перестановки массива следующая теорема утверждает, что для всех возможных предположений о высоте кэша B < Ms не существует алгоритма без явного задания параметров кэша с границей количества переносов блоков (даже для среднего случая), оебспечивающего нижнюю границу для наихудшего случая в модели ввода-вывода.

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