11.31. Воспользуйтесь сетью из упражнения 11.30 для разработки схемы, подобной алгоритму Пратта, на базе чисел, кратных 3 и 4. Вычертите полученную сеть для Л = 32 и решите упражнение 11.29 применительно к этой сети.

11.32. Начертить версию нечетно-четной сети сортировки Бэтчера для Л = 16, в условиях которой идеальное тасование выполняется между каскадами независимых компараторов, соединяющих смежные линии (четырьмя концевыми каскадами этой сети должны быть каскады из сети слияния в нижней части рис. 11.8).

о 11.33. Написать программу слияния для машины, изображенной на рис. 11.10, соблюдая следующие соглашения: каждая инструкция есть последовательность из 15 бит, при этом /-Й бит, 1 < / < 15, показывает (если он равен 1), что процессор / и процессор / - 1 должны выполнить операцию сравнения-обмена. Программа представляет собой последовательность инструкций, а машина выполняет идеальное тасование между каждыми двумя инструкциями.

о 11.34. Написать профамму сортировки для машины, изображенной на рис. 11.10, соблюдая соглашения, сформулированные в упражнении 11.33.

11.3. Внешняя сортировка

Мы переходим к рассмотрению другого аспекта задачи абстрактной сортировки, которая возникает, когда сортируемый файл настолько велик, что не помешается целиком в оперативной памяти компьютера. Для описания такого рода ситуаций мы используем термин внешняя сортировка (external sorting). Существует множество различных типов устройств внешней сортировки, которые наоадывают различные ограничения на атомарные операции, применяемые при реализации таких видов сортировки. Кроме того, будет полезно изучить методы сортировки, использующие две простейшие базовые операции: операция считывания (read) данных из внешнего запоминающего устройства в оперативную память и операция записи (write) данных из оперативной памяти на внешнее запоминающее устройство. Мы полагаем, что стоимость этих двух операции настолько выше стоимости простейших примитивных вычислительных операций, что последние в дальнейшем мы можем полностью игнорировать. Например, в условиях такой абстрактной модели мы можем позволить себе не учитывать стоимость сортировки в оперативной памяти! При офомных размерах оперативной памяти и неэффективных методах сортировки подобный подход может оказаться неоправданным, но в общем случае на практике при необходимости всегда можно учесть эти затраты при расчете общей стоимости внешней сортировки.

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

Довольно часто жесткие требования, предъявляемые к методам доступа к данным в зависимости от типа внешних устройств, оказываются более важным фактором, чем

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

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

Первым шагом при создании высокоэффективной программы сортировки файлов сверхбольших размеров является создание копии файла. Вторым шагом может быть представление исходного файла в обратном порядке. Все трудности, с которыми приходится сталкиваться при решении этих задач, возникают и при реализации внешней сортировки. (В процессе сортировки иногда приходится выполнять одну из этих операций.) Цель использования абстрактной модели состоит в том, чтобы отделить проблемы построения программной реализации от проблем разработки алгоритма.

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

Короче говоря, абстрактная модель сортировки, которой мы в дальнейшем будем пользоваться, построена на предположении, что сортируемый файл слишком велик,

чтобы полностью поместиться в оперативную память, и что он определяет значения двух других параметров: времени выполнения сортировки (число проходов по данным) и количество используемых внешних устройств. Мы полагаем, что в нашем распоряжении имеются

N записей на внешнем устройстве, сортировку которых мы должны выполнить

пространство оперативной памяти, достаточное для размещения М записей

2Р внешних устройств, которыми мы можем пользоваться во время сортировки.

Мы присваиваем метку О внешнему устройству, на котором находится файл входных данных, и метки 1, 2, 2Р- 1 всем остальным внешним устройствам. Цель сортировки заключается в том, чтобы возвратить записи на устройство О в отсортированном виде. Как мы увидим далее, существует некоторая зависимость между Р и общим временем выполнения сортировки - мы заинтересованы в том, чтобы получить эту зависимость в числовом выражении с тем, чтобы иметь возможность сравнить конкурирующие стратегии.

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

Большая часть методов внешней сортировки соблюдает следующие принципы общего характера. Выполняется первый проход по сортируемому файлу, в процессе которого производится его разбиение на блоки, размер которых примерно соответствует пространству оперативной памяти, после чего выполняется сортировка этих блоков. Затем осуществляется слияние отсортированных блоков, при необходимости с этой целью выполняются несколько проходов файла, при этом с каждым проходом степень упорядоченности возрастает, пока весь файл не окажется отсортированным. Такой подход называется сортировкой-слиянием {sort-merge), он с успехом применяется на практике с тех пор, когда компьютеры получили широкое распространение в коммерческих приложениях в пятидесятых годах прощлого столетия.

Простейшая стратегия сортировки-слияния, получившая название сбалансированного многопутевого слияния {balanced multiway merging), показана на рис. 11.12. Этот метод состоит из прохода, осуществляющего начальное распределение {initial distribution), за которым следуют несколько проходов многопутевого слияния {multiway merging passes).

На начальном проходе мы осуществляем распределение входных данных (входа) по внешним устройствам Р, Р + 1,..., 2Р - \ в виде отсортированных блоков данных, каждый из которых содержит М записей (за исключением, возможно, заключительного блока, который меньше остальных, если N не кратно М). Такое распределение нетрудно выполнить - мы считываем первые М записей с устройства ввода, сортируем их и записываем полученный блок данных на устройство Р; затем считываем следующие М записей с входного устройства, сортируем их и записываем отсортированный блок на устройство Р + \ и т.д. Если, достигнув устройства 2Р-\, у нас все еше остаются необработанные данные (т.е., если N > РМ), мы помещаем на устрой-