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

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

(5) <math>\Theta \bigg( \frac{n}{D} \bigg( 1 + \frac{rank( \gamma )}{log \; m} \bigg) \bigg) ,</math> '''где <math>\gamma</math> – подматрица размером log n x log B матрицы A, расположенная в ее левом нижнем углу.'''

Одним из требований является выбор S - 1 элементов разбиения таким образом, чтобы корзины были примерно одинакового размера. В этом случае размеры корзин уменьшаются от одного уровня рекурсии к другому на относительный коэффициент <math>\Theta(S)</math>, и, таким образом, существует <math>O(log_S \; n)</math> уровней рекурсии. На каждом уровне рекурсии выполняется сканирование данных. По мере прохождения элементов через внутреннюю память они разбиваются на S корзин в онлайновом режиме. Когда буфер размером B заполняется для одной из корзин, его блок записывается на диски при следующем вводе-выводе, и другой буфер используется для хранения следующего набора входящих элементов для этой корзины. Таким образом, максимальное число корзин (и элементов разбиения) равно <math>S = \Theta(M/B) = \Theta(m)</math>, а результирующее число уровней рекурсии равно <math>\Theta(log_m \; n)</math>. Как выполнить каждый уровень рекурсии за линейное число операций ввода-вывода, обсуждается в [2,11,16].