РИСУНОК 11.12.

На проходе начального распределения берем элементы AS О из набора входных данных, сортируем их и помещаем отсортированную совокупность А О S на первое устройство для выходных данных. До/гее мы берем элементы R TI из набора входных данных, сортируем их и помещаем отсортированную совокупность IRT на второе устройство для выходных данных. Продолжая таким образом, производя соответствующие операции на выходных устройствах в цикле, мы в конечном итоге получаем 15 отрезков: по пять на каждом выходном устройстве. На первой стадии слияния мы осуществляем слияние отрезков AOS, IR Т и А G N, в результате чего получаем последовательность А AG IN О RS Т, которую мы записываем на первое выходное устройство, затем мы выполняем слияние вторых отрезков на входных устройствах и получаем последовательность DEGGIMNNR, которую мы записываем на втором выходном устройстве, и т.д.; таким способом мы выполняем сбалансированное распределение данных на три устройства. Сортировка завершается двумя дополнительными проходами, на которых выполняется слияние.

ство Р + 1 второй отсортированный блок и т.д. до тех пор, пока весь ввод не будет исчерпан. По завершении процедуры распределения количество отсортированных блоков, размещенных на каждом устройстве, равно значению N/M, округленному до ближайшего целого числа в сторону уменьшения или увеличения. Если N есть кратное Л/, то размеры всех блоков одинаковы и равны N/M (если это не так, то все блоки, за исключением последнего, равны N/M). Для небольших N число блоков может оказаться меньше Р, ввиду чего одно или большее число устройств могут оказаться пустыми.

На первом многопутевом проходе, осуществляющем слияние, мы рассматриваем устройства в интервале от /до 2/* - 1 как входные, а устройства в интервале от О до Р- 1 как выходные. Мы осуществляем /-путевое слияние блоков данных размером М, помещенных на входные устройства, в результате которого получаем отсортированные блоки данных размером РМ, которые затем помещаем на выходные устройства с соблюдением условия максимально возможного баланса. Прежде всего, мы производим слияние первых блоков с каждого входного устройства и помещаем результат этого слияния на устройство О, затем мы помещаем результат слияния вторых блоков на каждом входном устройстве, на устройство 1 и т.д. По достижении устройства Р - \ мы далее помещаем второй блок данных на устройство О, затем второй блок на устройство 1 и т.д. Мы продолжаем этот процесс до тех пор, пока все входные данные не будут исчерпаны. По завершении процедуры распределения число отсортированных блоков на каждом устройстве равно N/iPM), округленное до

15+1

2*3 2*3 1+3

5+1 5+1 5+1

1+9 1*6

1+15

ближайшего целого числа в сторону увеличения или уменьшения. Если N есть кратное РМ, то все блоки имеют размер РМ (в противном случае заключительный блок имеет меньший размер). Если N не больше РМ, то остается один отсортированный блок (на устройстве 0) и на этом сортировка заканчивается.

В противном случае мы повторяем этот процесс и выполняем второй проход многопутевого слияния, рассматривая устройства О, 1,..., Р- 1 как входные устройства, а устройства Р, Р + 1,..., 2Р- 1 как выходные. Мы выполняем /*-путевое слияние с целью получить из отсортированных блоков размера РМ, посешенных на входных устройствах, блоки размером РМ с последуюшим их размещением на выходных устройствах. Сортировка заканчивается по завершении второго прохода (результат находится на устройстве Р), если N не больше РМ.

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

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

Чтобы выполнить /*-путевое слияние, мы можем воспользоваться очередью по приоритетам размером Р. Мы хотим постоянно иметь на выходе наименьший элемент из числа тех, которые еще не поступали на выход, из каждого из Р отсортированных блоков, подлежащих слиянию, с последующей заменой каждого элемента на выходе следующим элементом из того же блока. Чтобы завершить эту процедуру, мы отслеживаем индексы устройств с помощью операции operator<, считывающей значение ключа следующей записи, которая должна быть считана с указанного устройства (и порождающей служебную метку, которая превосходит по значению все ключи записей по достижении конца блока). Само слияние представляет собой простой цикл, который считывает очередную запись с устройства, имеющего минимальный ключ, и

РИСУНОК 11.13. РАСПРЕДЕЛЕНИЕ ПРОХОДОВ В 3-ПУТЕВОМ СБАЛАНСИРОВАННОМ СЛИЯНИИ.

В процессе начального распределения трехпутевой сбалансированной сортировки-слияния файла, размеры которого в 15 раз превосходят пространство оперативной памяти, мы размещаем 5 отрезков, размер которых в относительных единицах равен 1, на устройствах 4, 5 и 6, При этом устройства О, 1 и 2 остаются незагруженными. На первой стадии слияния мы помещаем отрезки размера 3 на устройства О и 1 и один отрезок размера 3 на устройство 2, оставляя устройства 3, 4 и 5 незагруженными. Далее вы выполняем слияние отрезков, находящихся на устройствах О, 1 и 2, и снова отправляем результаты на устройства 3, 4и 5 и так далее, продолжая процесс до тех пор, пока останется только один отрезок на устройстве 0. Общее число обработанных таким образом записей равно 60: четыре прохода по 15 записям.

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

Лемма 11.4. При наличии 2Р внешних устройств и оперативной памяти, достаточной для размещения М записей, сортировка-слияние, в основу которой положено Р-путевое сбалансированное слияние, требует выполнения 1 + log (N/M) проходов.

Один проход нужен для распределения. Если N = МР, то блоки получают размер MP после первого слияния, МР после второго, МР после третьего и т.д. Сортировка заканчивается после того, как будут выполнены к = log/. (N/M) проходов. В противном случае, если имеет место условие Л/< jV < М *, эффект неполных и пустых блоков приводит к появлению различий в размерах блоков ближе к концу процесса, тем не менее, он завершится после выполнения к = \\ogp(N/M)\ проходов.

Например, если мы хотим отсортировать 1 миллиард записей, имея для этой цели шесть внешних устройств и оперативную память, позволяющую разместить 1 миллион записей, мы можем решить эту задачу через трехпутевую сортировку-слияние, выполнив в общем целом восемь проходов по данным - один проход для начального распределения и [logs 10001 = 7 проходов слияния. После выполнения прохода начального распределения мы получим отсортированные блоки данных, содержащие по 1 миллиону записей, 3 миллиона записей в каждом блоке после первого слияния, 9 миллионов записей в каждом блоке после второго слияния, 27 миллионов записей в каждом блоке после третьего слияния и т.д. Можно подсчитать, что на сортировку файла уходит в 9 раз больше времени, чем на то, чтобы просто получить его копию.

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