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

(4)<math>\Theta \bigg( \frac{n}{D} log_m min \{ M, p, q, n \} \bigg),</math>

где N = pq и n = N/B.

Транспонирование матриц является частным случаем более общего класса перестановок, называемых перестановками типа «''перестановка битов и дополнение''» (bit-permute/complement, BPC), которые, в свою очередь, являются подмножеством класса перестановок типа «''перемножение битовых матриц и дополнение''» (bit-matrix-multiply/complement, BMMC). BMMC-перестановки определяются неособенной матрицей A размера log N x log N, содержащей только нули и единицы, и вектором длины log N с такими же элементами. Элемент с двоичным адресом x отображается перестановкой на двоичный адрес, заданный Ax ф c, где В обозначает поразрядное исключающее «ИЛИ». BPC-перестановки являются частным случаем BMMC-перестановок, в котором A является матрицей перестановок, то есть каждая строка и каждый столбец A содержат по одному значению 1. BPC-перестановки включают в себя транспонирование матрицы, бит-реверсивную перестановку (которая возникает при быстром преобразовании Фурье), обращение векторов, перестановку элементов гиперкуба и переблокировку матрицы. Кормен и коллеги [6] характеризуют оптимальное число операций ввода-вывода, необходимое для выполнения любой заданной BMMC-перестановки, исключительно как функцию от соответствующей матрицы A, а дакже дают оптимальный алгоритм ее реализации.

Теорема 4 [6]. При наличии D дисков количество операций ввода-вывода, необходимых для выполнения BMMC-перестановки, заданной матрицей A и вектором c, равно  

где у – подматрица размером log n x log B матрицы A, расположенная в ее левом нижнем углу.

Двумя основными парадигмами внешней сортировки являются распределение и слияние, которые будут рассмотрены далее для модели PDM.

Сортировка распределением [ ] представляет собой рекурсивный процесс, который использует набор из S - 1 элементов разбиения для распределения элементов на S несовпадающих «корзин». Все элементы в одной корзине предшествуют всем элементам в следующей корзине. Сортировка завершается рекурсивной сортировкой отдельных корзин и объединением их в единый, полностью отсортированный список.

Одним из требований является выбор S - 1 элементов разбиения таким образом, чтобы корзины были примерно одинакового размера. В этом случае размеры корзин уменьшаются от одного уровня рекурсии к другому на относительный коэффициент 0{S), и, таким образом, существует O(logS n) уровней рекурсии. На каждом уровне рекурсии выполняется сканирование данных. По мере прохождения элементов через внутреннюю память они разбиваются на S корзин в онлайновом режиме. Когда буфер размером B заполняется для одной из корзин, его блок записывается на диски при следующем вводе-выводе, и другой буфер используется для хранения следующего набора входящих элементов для этой корзины. Таким образом, максимальное число корзин (и элементов разбиения) равно S = 0{MIB) = 0{m), а результирующее число уровней рекурсии равно @(logm n). Как выполнить каждый уровень рекурсии за линейное число операций ввода-вывода, обсуждается в [2,11,16].