2.2.5. Транспонирование методом «ввод строки-вывод столбца»

Этот алгоритм является обобщением предложенного Кнутом [2.12] алгоритма транспонирования матриц, хранящихся в ЗУ последовательного типа. В первоначальном виде алгоритм транспонирует матрицу хранящуюся последовательно (в форме одна запись — одна строка) за проходов, используя ячеек ОЗУ и четыре дополнительных последовательных файла. Рассмотрим работу алгоритма. На каждом шаге создаются два файла.

Шаг 1.

Шаг 2.

Каждые два файла на следующем шаге обрабатываются синхронно посредством считывания одной записи из каждого входного файла и последующей записи данных в выходные файлы в новом порядке, по две записи в каждый файл попеременно. Очевидно, транспонирование будет получено после проходов или после операций считывания и записи.

В процессе работы возникает необходимость в незначительном изменении размеров записей. Фактически требуется увеличивать некоторые записи таким образом, чтобы на шаге, они содержали по элементов, где — четное число. Это означает, что некоторые входные записи на последнем шаге содержат элементов.

Тщательное рассмотрение алгоритма показывает, что шаг в действительности соответствует последовательности полных

перестановок [2.11] пар массивов, элементами которых являются подмассивы из элементов. В этом смысле алгоритм Кнута, конечно, подобен алгоритму Стоуна [2.11], но перестановки выполняются при выводе на внешнее ЗУ и переупорядоченные массивы на каждом шаге не формируются в ОЗУ на этом шаге. Такое обстоятельство наводит на мысль о небольшой модификации алгоритма, при которой на последнем шаге транспонируются матрицы элементами которых являются матрицы-столбцы из элементов. Таким образом, получаем строки транспонированной матрицы в ОЗУ перед записью их в выходной файл. Это свойство полезно, если алгоритм применяется в сочетании, например, с вычислением БПФ.

Рассмотренный алгоритм может быть естественным образом обобщен на случай прямоугольных матриц с помощью метода, описанного в подразд. 2.2.3. Он эффективен для транспонирования матриц, хранящихся в ЗУ последовательного типа. Например, он, вообще говоря, более эффективен, чем подход, предложенный в [2.14, 2.15] (доказательство см. в [2.6]).

Пусть матрица А хранится в ЗУ с произвольным доступом. Тогда алгоритм имеет обобщение, которое работает в точности аналогично алгоритму разбиения на квадраты, за исключением только одного аспекта. Имея матрицу размерами которая построена из фрагментов строк матрицы А, формируем строки записывая последовательных столбцов подматриц в оперативную память. Тогда строки матриц будут состоять из частей строк матрицы А размера Обычно нет необходимости дополнять строки на выходе фиктивными данными для выравнивания размеров матрицы.

Отметим, что для двоичного случая этот метод не идентичен методу разбиения на квадраты. Однако они равноценны в отношении требований к ресурсам, т. е.

Имеющиеся отличия иногда могут оказаться важными. Так, перестановки на месте не столь просты, как транспонирование квадратных матриц. Но обычно это нас не интересует до последнего шага, и поэтому можно считать, что оба метода будут работать одинаково (см. примеры в разд. 2.5). Более важны особенности, которые касаются требований к внешней памяти. Применительно к квадратным матрицам, хранящимся в файлах с произвольным доступом, оба алгоритма могут работать с оставлением на месте с одним единственным файлом. Это справедливо также для метода прямоугольных разбиений, приведенного ниже, который можно заставить работать с квадратами Для неквадратных матриц эти три метода уже не подобны друг другу.

Первоначальный выходной файл может всегда быть последовательным и неизменным. Независимо от этого метод разбиения на квадраты может работать с оставлением на месте вплоть до шага на котором матрица А запоминается во второй области произвольного доступа. Метод разбиения на прямоугольники требует двух областей произвольного доступа для размещения

Кроме того, размеры файлов будут меняться.

Наконец, метод «ввод строки-вывод столбца» может быть реализован подобно методу разбиения на квадраты. Если, однако, на последнем шаге порядок, в котором обрабатываются группы строк изменяется (см. пример в разд. 2.6), строки А могут формироваться последовательно. К тому же метод работает с последовательными файлами, если число дополнительных файлов составляет

Конечно, существуют также прямоугольные варианты приведенного в этом разделе алгоритма. Мы советуем читателю самому разобраться в этих деталях.