2.2. Методы транспонирования матриц, хранящихся во внешних запоминающих устройствах
2.2.1. Определение критериев эффективности
В следующих разделах будет описан ряд методов транспонирования матриц, хранящихся в ОЗУ так, что каждая запись содержит одну строку (или столбец). В дальнейшем, однако, будем всегда считать, что матрицы записаны построчно. Работа всех алгоритмов, в общем, состоит в том, что они считывают ограниченное число записей в ОЗУ, переупорядочивают их, формируют новые выходные записи и заносят их в выходной файл, совпадающий или не совпадающий с входным файлом. Эффективность алгоритмов будет определяться с точки зрения требуемого числа ячеек RM ОЗУ и числа операций ввода-вывода 10 (т. е. числа записей, которые нужно считать или записать). Эти показатели не учитывают всех вычислительных затрат, однако неучтенной частью можно пренебречь или считать ее неизменной для разных методов, если они применяются к одной и той же матрице. Точнее, существуют два основных неучтенных вида затрат.
К первому виду относятся затраты на переупорядочение данных в памяти для формирования новых выходных записей. Однако новые записи на выходе можно создавать без фактического перемещения данных в памяти. Например, можно использовать неявные циклы в операторах вывода в Фортране (см. разд. 2.7). Следовательно, затраты процессорного времени невелики и, кроме того, они пропорциональны произведению числа элементов матрицы на число просмотров данных, которое уже учитывается в числе операций ввода-вывода. Хотя мы считаем все алгоритмы построенными именно таким способом, для простоты будем говорить о транспонировании матриц и переупорядочении массивов в памяти.
Неточность оценки второго вида возникает вследствие того, что при учете числа пересылаемых записей мы пренебрегаем возможным различием длин записей для того или иного метода. Поэтому для большей точности необходимо учитывать также число слов, подлежащих пересылке. Однако затратами на это можно пренебречь по двум причинам. Во-первых, время доступа к одной записи обычно намного больше, чем время пересылки одного слова. Для современных быстродействующих накопителей на дисках отношение этих времен обычно превышает 1000. Во-вторых, тщательное рассмотрение различных методов показывает, что возможные изменения длины записи обычно малы по сравнению с этим отношением.
