Специальные методы сортировки a

Рис. 11.13.
Распределение отрезков в сбалансированном 3-путевом слиянии
В процессе начального распределения сбалансированной трехпутевой сортировки-слияния файла, размер которого в 15раз больше размера оперативной памяти, на устройства 3, 4 и 5 записываются по 5 отрезков, размер которых в относительных единицах равен 1, а устройства 0, 1 и 2 остаются пустыми. На первом этапе слияния два отрезка размером 3 записываются на устройства 0 и 1, и один отрезок размером 3 на устройство 2, после чего устройства 3, 4 и 5 остаются пустыми. Далее выполняется слияние отрезков, находящихся на устройствах 0, 1 и 2, а результаты записываются снова на устройства 3, 4 и 5 и т.д., пока не останется только один отрезок на устройстве 0. Общее количество обработанных записей равно 60: четыре прохода по 15 записям.
Лемма 11.4. При наличии 2P внешних устройств и оперативной памяти, достаточной для размещения Mзаписей, сортировка-слияние на основе P-путевого сбалансированного слияния выполняет порядка   проходов.
Один проход нужен для распределения. Если N = MP^k , то блоки имеют размер MP после первого слияния, MP² после второго, MP³ после третьего и т.д. Сортировка заканчивается после   проходов. В противном случае, если MP^k-1k < N < MP^k , наличие неполных и пустых блоков приводит ближе к концу процесса к появлению различий в размерах блоков, но он все равно завершается после выполнения   проходов. 
Например, если нужно отсортировать 1 миллиард записей, используя шесть внешних устройств и оперативную память, позволяющую разместить 1 миллион записей, это можно сделать с помощью трехпутевой сортировки-слияния, выполнив всего восемь проходов по данным: один проход начального распределения и   проходов слияния. После начального распределения получаются отсортированные отрезки данных, содержащие по 1 миллиону записей, после первого слияния - по 3 миллиона записей, после второго слияния - по 9 миллионов записей, после третьего слияния - по 27 миллионов записей в каждом блоке и т.д. Можно подсчитать, что на сортировку файла уйдет в 9 раз больше времени, чем на его копирование.
Наиболее важное решение, которое приходится принимать на практике при подготовке сортировки-слияния - это выбор значения P, т.е. порядка слияния. В используемой нами абстрактной модели последовательный метод доступа накладывает ограничение, что P должно быть равно половине числа доступных внешних устройств. Такая модель реалистична для многих внешних запоминающих устройств. Однако существует множество других внешних запоминающих устройств, для которых возможен и не последовательный доступ, хотя его стоимость и больше. Если для сортировки доступно всего лишь небольшое количество внешних устройств, использование методов доступа, отличных от последовательного, становится неизбежным. В таких случаях все еще можно использовать многопутевое слияние, но при этом нужно учитывать, что увеличение значения P приводит к уменьшению числа проходов, но увеличивает количество (медленных) операций непоследовательного доступа.
Упражнения
11.35. В стиле примера, представленного на рис. 11.12, покажите, как ключи E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S сортируются с помощью 3-путе-вого сбалансированного слияния.
11.36. Как отразится на количестве проходов многопутевого слияния удвоение количества внешних устройств?
11.37. Как отразится на количестве проходов многопутевого слияния увеличение объема доступной оперативной памяти в 10 раз?
11.38. Разработайте интерфейс для внешних входных и выходных устройств, который использует последовательную передачу блоков данных с асинхронно работающих внешних устройств (или подробно ознакомьтесь с существующим в вашей системе). Реализуйте с помощью этого интерфейса P-путевое слияние, чтобы P было максимально возможным при условии, что P входных файлов и выходной файл должны размещаться на различных выходных устройствах. Сравните время выполнения полученной программы с временем, необходимым для последовательного копирования файлов на выходные устройства.
11.39. Пользуясь интерфейсом из упражнения 11.38, напишите программу обращения порядка записей в файле максимально допустимого в вашей системе размера.
11.40. Как выполнить идеальное тасование всех записей на внешнем устройстве?
11.41. Разработайте модель стоимости многопутевого слияния, которое охватывает алгоритмы, способные переключаться с одного файла на другой на том же самом устройстве с фиксированной стоимостью переключения, которая намного превышает стоимость последовательного чтения.
11.42. Разработайте способ внешней сортировки, основанный на разбиении, подобном используемому в быстрой сортировке или MSD-сортировке, проанализируйте его и сравните с многопутевой сортировкой. Можно использовать высокий уровень абстракции, как при описании сортировки-слияния в этом разделе, однако нужно стремиться к тому, чтобы можно было спрогнозировать время выполнения для заданного числа устройств и заданного объема оперативной памяти.
11.43. Как отсортировать содержимое внешнего устройства, если недоступны любые другие внешние устройства (кроме оперативной памяти)?
11.44. Как отсортировать содержимое внешнего устройства, если доступно лишь еще одно устройство (а также оперативная память)?