РИСУНОК 11.15. ПРИМЕР МНОГОФАЗНОГО СЛИЯНИЯ

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

Стратегия сливать до опустошения работает на произвольном числе магнитных лент, как показано на рис. 11.16. Слияние разбивается на множество фаз, и не каждая из них выполняется на всей совокупности данных, зато ни на одной из них не надо выполнять дополнительного копирования. На рис. 11.16 показано, как производится вычисление отрезков для начального распределения. Мы подсчитываем число отрезков на каждом устройстве, рассуждая в обратном порядке.

В случае примера, представленного на рис. 11.16, мы ставим перед собой Следующую задачу: мы хотим закончить слияние с 1 отрезком на устройстве 0. Следовательно, перед последним слиянием устройство О должно быть незагруженным, а на устройствах 1, 2 и 3 должны находиться по одному отрезку. Далее, мы определяем, каким должно быть распределение отрезков, которое потребуется для выполнения предпоследнего слияния, чтобы получить требуемое распределение. Одно из устройств 1, 2 или 3 должно быть пустым (чтобы его можно было использовать в качестве выходного устройства для предпоследнего слияния) - произвольно выбираем для этой цели устройство 3. Иначе говоря, предпоследнее слияние сливает по одному отрезку с каждого устройства О, 1 и 2 и помещает результат на устройство 3. Поскольку предпоследнее слияние оставляет О отрезков на устройствах О и 1, оно должно начинаться с одного отрезка на устройстве О и двух отрезков на каждом из устройств 1 и 2. Аналогичные рассуждения приводят нас к заключению, что слияние, предшествующее только что рассмотренному, должно начинаться с того, что на устройствах 3, О и 1 должно быть, соответственно, 2, 3 и 4 отрезка. Продолжая в том же духе, мы можем построить таблицу распределения отрезков: выбираем максимальное число из каждого ряда, заменяем его нулем и добавляем его к каждому из оставшихся чисел, чтобы получить предьщущий ряд. Этот прием соответствует определению предьщуще-го ряда слияния высшего порядка, которое порождает текущий ряд. Такая техника работает с любым количеством магнитных лент (по меньшей мере, с тремя). Возни-

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

Имея в своем распоряжении распределение отрезков, мы, применяя прямой ход рассуждений, можем вычислить их относительные размеры, фиксируя размеры после очередного слияния. Например, первое слияние в примере на рис. 11.16 порождает 4 отрезка размером в 3 относительных единицы на устройстве О, два отрезка размером 1 на устройстве 2 и 1 отрезок размера 1 на устройстве 3 и т.д. Как и в случае сбалансированного многопутевого слияния, мы можем проделать указанные операции умножения, просуммировать результаты (не включая нижнюю строку) и поделить на число начальных отрезков, чтобы вычислить меру стоимости в виде числа, кратного стоимости полного прохода по всей совокупности данных. Для простоты вычислений мы включаем фиктивные отрезки в расчет затрат, который дает нам верхнюю границу истинной стоимости.

Лемма 11.6. При наличии трех внешних устройств и пространства оперативной памяти, достаточного для размещения М записей, сортировка-слияние, в основу которой положена операция выборки с замещением с последующим двухпуте-вым многофазным слиянием, выполняет в среднем 1 +

РИСУНОК 11.16. РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ ДЛЯ МНОГОФАЗНОГО ТРЕХПУТЕВОГО СЛИЯНИЯ

В процессе начального распределения многофазного трехпутевого слияния файла, размеры которого в 17 раз превосходят объем пространства оперативной памяти, мы помещаем семь отрезков на устройство О, четыре отрезка на устройство 2 и шесть отрезков на устройство 3. Затем, на первой фазе мы выполняем слияния до тех пор, пока устройство 2 не станет пустым, при этом три отрезка размером I остаются на устройстве О, два отрезка размером I на устройстве 3, и создаем четыре отрезка размером 3 на устройстве I. Для файла, в 15 раз превышающего по размерам оперативную память, мы вначале помещаем два фиктивных отрезка на устройство О (см. рис. 11.15). Общее число блоков, подвергнутых обработки в процессе полного слияния, равно 59, на один меньше, чем в примере, иллюстрирующем сбалансированное слияние (см. рис. 11.13), но при этом мы используем на 2устройства меньше (см. упражнение 11.50).

log (ЛУЛ/) /0 эффективных проходов.

Общий анализ многофазной сортировки, выполненный Кнутом (Knuth) и другими исследователями в шестидесятых-семидесятых годах, - сложное и пространное исследование, выходящее за рамки данной книги. Для Р = Ъ используются числа Фибоначчи, отсюда и появление коэффициента ф. Другие константы появляются для Р больше 3. Коэффициент 1/0 используется в случае, когда на каждой фазе используется именно эта часть данных. Мы подсчитываем число эффективных проходов как количество считанных данных, деленных на общее количество данных. Некоторые результаты общего анализа вызывают удивление. Например, оптимальный метод распределения фиктивных отрезков по магнитным лентам предусматривает использование дополнительных фаз и большего числа фиктивных отрезков, чем можно бы было предположить, поскольку некоторые отрезки используются в слияниях намного чаше других {см. раздел ссылок).

Например, если мы хотим отсортировать 1 миллиард записей, используя для этой цели 3 устройства и пространство оперативной памяти, достаточное для размещения 1 миллиона записей, мы можем сделать это посредством двухпутевого многофазного слияния с llogSOOl/ = 8 проходами. Добавив проход начального распределения, мы получаем несколько большие затраты (один проход), чем в случае сбалансированного слияния, которое использует в два раза большее число устройств. То есть, мы можем рассматривать многофазное слияние как процедуру, позволяющую выполнять ту же работу, но с половиной аппаратных средств. Для заданного количества устройств многофазное слияние всегда обеспечивает большую эффективность, чем сбалансированная сортировка, о чем свидетельствует рис. 11.17.

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

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

Принимая эту крайнюю точку зрения, заметим, что многие из современных вычислительных систем располагают возможностью виртуальной памяти (virtual memory) - более абстрактная модель доступа к внешним устройствам, чем та, которая использовалась до сих пор. в виртуальной памяти мы получаем возможность обращаться к крупным блокам данных, содержащим большое количество записей, полагаясь на систему в вопросе гарантированной доставки адресуемых данных с внешних запоминающих устройств в оперативную память, когда нам это нужно; при этом возникает впечатление, что доступ к данным в смысле удобства ничем не отличается от прямого доступа к данным, находящимся в оперативной памяти. Однако эта иллюзия не совсем полная: пока программа обращается к ячейкам памяти, расположенных в относительной близости по отношению к ячейкам, к которым она недавно обращалась, то потребность в передаче данных с внешних устройств в оперативную память возникает нечасто и рабочие характеристики внешней памяти вполне удовлетворительны. (Например, программы, которые осуществляют последовательный доступ к дан-

РИСУНОК 11.17. СРАВНЕНИЕ ЗАТРАТ НА СБАЛАНСИРОВАННОЕ И МНОГОФАЗНОЕ СЛИЯНИЕ

Число проходов, выполняемых в рамках сбалансированного слияния на четырех магнитных лентах (сверху), всегда больше, чем число эффективных проходов, выполняемых в рамках многофазного слияния с тремя магнитными лентами (внизу). Представленные на рисунке графики получены для функций, обладающих свойствами из лемм 11.4 и 11.6, для N/Mom 1 до 100. В силу наличия фиктивных отрезков истинные характеристики многофазного слияния имеют более сложный характер, чем следует из представленной шаговой функции.