Внешняя многофазная сортировка слиянием

Внешняя многофазная сортировка слиянием

    Иногда сортируемый список оказывается настолько велик, что он не помещается целиком в память компьютера. Напомним, что хотя изучаемые нами алгоритмы имеют дело с упорядочиванием ключей, подразумевается, что эти ключи связаны с целыми записями. Во многих случаях длина записи значительно превышает длину ключа. Иногда длина записи очень велика и перестановка двух записей занимает столько времени, что анализ эффективности алгоритма должен учитывать как число сравнений, так и число обменов.
    Иногда допустимо объявить массив, размер которого достаточен для размещения всех требуемых данных, хотя размеры этого массива и значительно превышают доступный компьютеру объем памяти. Тогда операционная система пользуется виртуальной памятью, и следует учитывать эффективность ее использования. Однако даже и в этом случае объем обменов между оперативной памятью и дисками может быть значительным. Даже в эффективных алгоритмах сортировки вроде "Быстрой сортировки" соотношение между частями разбиения и длиной блока логической памяти может оказаться таким, что оно приведет к большому числу перезаписываний блоков. Нередко эта проблема не осознается, пока программа не будет реализована на компьютере, причем ее скорость оказывается настолько неудовлетворительной, что приходится применять средства технического анализа для выяснения узких мест. Даже и в этом случае анализ может оказаться безрезультатным, если операционная система не предоставляет инструментов отслеживания обменов в виртуальной памяти.
    Для выяснения эффективности алгоритмов сортировки мы подсчитывали число выполняемых ими сравнений. Однако объем работы по чтению или записи на диск блоков виртуальной памяти может значительно превышать трудоемкость логических и арифметических операций. Эта работа выполняется операционной системой, и поэтому у нас нет реальных средств воздействия на ее эффективность.
    При другом подходе можно воспользоваться файлами с прямым доступом и заменить непосредственные обращения к массиву операциями поиска в файле для выхода в нужную позицию с последующим чтением блока. В результате размер используемой логической памяти уменьшается, а значит уменьшается неконтролируемая нагрузка на виртуальную память. Объем операций ввода-вывода все равно остается значительным - управляем ли мы им сами или полагаемся на операционную систему.
    В результате большинство алгоритмов сортировки на больших объемах данных оказываются непрактичными. Обратимся теперь к другой возможности: пусть у нас есть четыре файла и инструмент их слияния.
    Оценим сначала разумное число записей, которые можно хранить в оперативной памяти одновременно. Объявим массив, длина S которого равна этой величине; этот массив будет использоваться на двух этапах сортировки. На первом шаге мы прочитаем S записей и отсортируем их с помощью подходящей внутренней сортировки. Этот набор уже отсортированных записей перепишем в файл A. Затем прочитаем еще S записей, отсортируем их и перепишем в файл B. Этот процесс продолжается, причем отсортированные блоки записей пишутся попеременно то в файл A, то в файл B. Вот алгоритм, реализующий первый этап:

CreateRuns(S)
S		размер создаваемых отрезков

CurrentFile = A
while конец входного файла не достигнут do
	read S записей из входного файла
	sort S записей
	if CurrentFile = A then
		CurrentFile = B
	else
		CurrentFile = A
	end if
end while

После того, как входной файл полностью разбит на отсортированные отрезки, мы готовы перейти ко второму шагу - слиянию этих отрезков. Каждый из файлов A и B содержит некоторую последовательность отсортированных отрезков, однако, как и в случае сортировки слиянием, мы ничего не можем сказать о порядке записей в двух различных отрезках.
Процесс слияния будет аналогичен функции MergeLists из статьи "Сортировка слиянием", однако теперь вместо того, чтобы переписывать записи в новый массив, мы будем записывать их в новый файл. Поэтому мы начинаем с чтения половинок первых отрезков из файлов A и B. Читаем мы лишь по половине отрезков, поскольку мы уже выяснили, что в памяти может находиться одновременно лишь S записей, а нам нужны записи из обоих файлов. Будем теперь сливать эти половинки отрезков в один отрезок файла C. После того, как одна из половинок закончится, мы прочтем вторую половинку из того же файла. Когда обработка одного из отрезков будет завершена, конец второго отрезка будет переписан в файл C. После того, как слияние первых двух отрезков из файлов A и B будет завершено, следующие два отрезка сливаются в файл D. Этот процесс слияния отрезков продолжается с попеременной записью слитых отрезков в файлы C и D. По завершении мы получаем два файла, разбитых на отсортированные отрезки длины 2S. Затем процесс повторяется, причем отрезки читаются из файлов C и D, а слитые отрезки длины 4S записываются в файлы A и B. Ясно, что в конце концов отрезки сольются в один отсортированный список в одном из файлов. Вот алгоритм осуществления второго этапа:

PolyPhaseMerge(S)
S					размер исходных отрезков
Size = S
Input1 = A
Input2 = B
CurrentOutput = C
while not done do
	while отрезки не кончились do
		слить отрезок длины Size из файла Input1
			с отрезком длины Size из файла Input2
			записав результат в CurrentOutput
		if (CurrentOutput = A)	 then
			CurrentOutput = B
		elsif (CurrentOutput = B) then
			CurrentOutput = A
		elsif (CurrentOutput = C) then
			CurrentOutput = D
		elsif (CurrentOutput = D) then
			CurrentOutput = C
		end if
	end while
	Size = Size*2
	if (Input1 = A)	 then
		Input1 = C
		Input2 = D
		CurrentOutput = A
	else
		Input1 = A
		Input2 = B
		CurrentOutput = C
	end if
end while

Прежде, чем перейти к анализу, посмотрим, с каким количеством отрезков мы имеем дело, и как это количество влияет на число проходов. Если в исходном файле N записей и в память помещается одновременно S записей, то после выполнения процедуры CreateRuns мы получаем R = [N / S] отрезков, распределенных по двум файлам. При каждом проходе алгоритма PolyPhaseMerge пары отрезков сливаются, поэтому число отрезков уменьшается вдвое. После первого прохода будет [R / 2] отрезков, после второго - [R / 4] и, в общем случае, после j-го прохода будет [R / 2^j] отрезков. Работа завершается, если остается один отрезок, то есть после D проходов, где [R / 2^D] = 1, то есть при D = [log₂R] проходов процесса слияния.

Сайт управляется системой uCoz