Многофазная сортировка

Многоканальную (m-канальную) сортировку слиянием можно выполнить с помо­щью лишь т + 1 файлов (в отличие от описанной выше 2/n-файловой стратегии). При этом выполняется ряд проходов с объединением серий из т файлов в более длинные серии в (т + 1)-м файле. Вот последовательные шаги такой процедуры.

1. В течение одного прохода, когда серии от каждого из т файлов объединяются в серии (т + 1)-го файла, нет нужды использовать все серии от каждого из т входных файлов. Когда какой-либо из файлов становится выходным, он запол­няется сериями определенной длины, причем количество этих серий равно ми­нимальному количеству серий, находящихся в сливаемых файлах.

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

Подобный процесс сортировки слиянием называется многофазной сортировкой. Точный подсчет требуемого количества проходов как функции от т (количества файлов) и п (количество записей), а также нахождения оптимального начального распределения серий между т файлами оставлен для упражнений. Однако мы при­ведем здесь один пример общего характера.

Когда скорость ввода-вывода не является „узким местом"

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

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

Рассмотрим случай, когда "узким местом" является слияние, а не считывание или запись данных. Это может произойти по следующим причинам.

1. Как мы уже видели, если в нашем распоряжении есть много дисководов или на­копителей на магнитной ленте, ввод-вывод можно ускорить настолько, что время для выполнения слияния превысит время ввода-вывода.

2. Может стать экономически выгодным применение более быстродействующих ка­налов обмена данными.

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

1. Мы объединяем серии, размеры которых намного превышают размеры блоков.

2. Существуют два входных и два выходных файла. Входные файлы хранятся на одном внешнем диске (или каком-то другом устройстве, подключенном к основ­ной памяти одним каналом), а выходные файлы — на другом подобном устрой­стве с одним каналом.

3. Время считывания, записи и выбора для заполнения блока записей с наимень­шими ключами среди двух серий, находящихся в данный момент в основной памяти, одинаково.

С учетом этих предположений рассмотрим класс стратегий слияния, которые пре­дусматривают выделение в основной памяти нескольких входных буферов (место для хранения блока). В каждый момент времени какой-то из этих буферов будет содер­жать невыделенные для слияния записи из двух входных серий, причем одна из них будет находиться в состоянии считывания из входного файла. Два других буфера бу­дут содержать выходные записи, т.е. выделенные записи в надлежащим образом объединенной последовательности. В каждый момент времени один из этих буферов находится в состоянии записи в один из выходных файлов, а другой заполняется за­писями, выбранными из входных буферов.

Выполняются (возможно, одновременно) следующие действия.

1. Считывание входного блока во входной буфер.

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

3. Запись данных другого выходного буфера в один из двух формируемых выход­ных файлов.

В соответствии с нашими предположениями, эти действия занимают одинаковое время. Для обеспечения максимальной эффективности их следует выполнять парал­лельно. Это можно делать, если выбор записей с наименьшими ключами не включает записи, считываемые в данный момент. Следовательно, мы должны разработать та­кую стратегию выбора буферов для считывания, чтобы в начале каждого этапа (состоящего из описанных действий) b невыбранных записей с наименьшими ключа­ми уже находились во входных буферах (b — количество записей, которые заполня­ют блок или буфер).

Условия, при которых слияние можно выполнять параллельно со считыванием, достаточно просты. Допустим, k₁ и k₂ — наибольшие ключи среди невыбранных за­писей в основной памяти из первой и второй серий соответственно. В таком случае в основной памяти должно быть по крайней мере b невыбранных записей, ключи ко­торых не превосходят min(k_l, k₂).