|
Рис. 11.12. Пример трехпутевого сбалансированного слияния
На проходе начального распределения мы выбираем из входных данных элементы A S O, сортируем их и записываем упорядоченную последовательность A O S на первое выходное устройство. Далее мы выбираем из входных данных элементы R T I, сортируем их и записываем упорядоченную последовательность I R T на второе выходное устройство. Продолжая таким образом и циклически переключаясь между выходными устройствами, мы окончательно получаем 15 отрезков: по пять на каждом выходном устройстве. На первом этапе слияния сливаются отрезки A O S, I R T и A G N, и получается последовательность A A G I N O R S T, которую мы записываем на первое выходное устройство, затем выполняется слияние вторых отрезков на входных устройствах, и получается последовательность D E G G I M N N R, которую мы записываем на второе выходное устройство и т.д.; теперь получилось сбалансированное распределение данных на трех устройствах. После еще двух проходов слияния сортировка завершается.
Мы выполняем P-путевое слияние блоков данных размером M, помещенных на входные устройства, и получаем отсортированные блоки данных размером PM, которые максимально сбалансированно размещаем на выходных устройствах. Сначала сливаются первые блоки с каждого входного устройства, а результат этого слияния записывается на устройство 0, затем сливаются вторые блоки с каждого входного устройства и записываются на устройство 1 и т.д. После использования устройства P - 1 вторые блоки данных записываются на устройство 0, затем на устройство 1 и т.д. Этот процесс продолжается до тех пор, пока все входные данные не будут исчерпаны. После распределения количество отсортированных блоков на каждом устройстве равно N/PM, округленному до ближайшего целого числа в ту или другую сторону. Если N кратно PM, то все блоки имеют размер PM, иначе последний блок меньше остальных. Если N не больше PM, то остается один отсортированный блок (на устройстве 0), и на этом сортировка заканчивается.
В противном случае мы повторяем этот процесс и выполняем второй проход многопутевого слияния, рассматривая устройства 0, 1, ..., P - 1 в качестве входных, а устройства P, P + 1, ..., 2P - 1 в качестве выходных. В результате P-путевого слияния отсортированных блоков размером PM, размещенных на входных устройствах, получаются блоки размером P2M, которые размещаются на выходных устройствах. Сортировка заканчивается по завершении второго прохода (результат на устройстве P), если N не больше P2M.
Продолжая таким образом и переключаясь между устройствами от 0 до P - 1 и устройствами от P до 2P - 1, каждое P-путевое слияние увеличивает размер блоков в P раз, пока в конечном итоге не получится один блок, на устройстве 0 или на устройстве P. Последнее слияние на каждом проходе может не быть полным P-путевым слиянием, если это не так, то процесс хорошо сбалансирован. Этот процесс проиллюстрирован на рис. 11.13, где указаны только количество и относительные размеры отрезков. Оценку стоимости слияния можно получить, выполнив умножения, указанные в представленной на рисунке таблице, просуммировав результаты (без нижней строки) и поделив сумму на число первоначальных отрезков. Эти вычисления выражают затраты через количество проходов по данным.
Чтобы выполнить P-путевое слияние, можно воспользоваться очередью с приоритетами размером P. Нужно постоянно выбирать из каждого из P сливаемых упорядоченных блоков наименьший элемент из числа еще не выведенных, и затем заменять выведенный элемент следующим из того же блока. Для выполнения этой процедуры в очереди с приоритетами хранятся индексы устройств, значение ключа следующей записи считывается с указанного устройства (а по достижении конца блока выдается сигнальное значение, большее всех ключей в записях) и определяется функция <. Тогда само слияние сводится к простому циклу, который считывает очередную запись с устройства с минимальным ключом и выдает ее в выходной файл, после чего заменяет эту запись в очереди с приоритетами следующей записью с того же устройства, и так до тех пор, пока наименьший ключ в очереди с приоритетами не станет равным сигнальному значению. Можно воспользоваться реализацией пирамидального дерева и сделать время обслуживания очереди с приоритетами пропорциональным log P, но обычно P так мало, что эти затраты незаметны по сравнению с операциями записи на внешнее устройство. В нашей абстрактной модели мы игнорируем затраты на содержание очереди с приоритетами и предполагаем, что имеется эффективный метод последовательного доступа к данным на внешних устройствах, поэтому время выполнения можно измерять подсчетом количества проходов по данным. Для практических целей можно воспользоваться элементарной реализацией очереди с приоритетами и сосредоточить усилия на создании программ, обеспечивающих максимально производительное использование внешних устройств.
Do'stlaringiz bilan baham: |
