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

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

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