Сортировка методом простого слияния

⇐ ПредыдущаяСтр 9 из 69Следующая ⇒

Предположим, что имеется последовательный файл A, состоящий из записей a1, a2, ..., an. Для сортировки используются два вспомогательных файла B и C.

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3,... пишутся в файл B, а записи a2, a4,...-в файл C. Начальное слияние производится над парами (a1, a2), (a3, a4),... и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей.

Пример:

Начальное состояние файла A	8 23 5 65 44 33 1 6
Первый шаг Распределение Файл B Файл C Слияние: файл A	8, 5, 44, 1 23, 65, 33, 6 8 23, 5 65, 33 44, 1 6
Второй шаг Распределение Файл B Файл C Слияние: файл A	8 23, 33 44 5 65, 1 6 5 8 23 65, 1 6 33 44
Третий шаг Распределение Файл B Файл C Слияние: файл A	5 8 23 65 1 6 33 44 1 5 6 8 23 33 44 65

Для выполнения внешней сортировки методом прямого слияния в основной памяти требуется расположить всего лишь две переменные - для размещения очередных записей из файлов B и C.

После выполнения i подобного рода проходов у нас получатся два файла, состоящие из серий длины 2ⁱ. Если 2ⁱ > п, тогда один из этих двух файлов будет пустым, а другой будет содержать единственную серию длиной п, т.е. будет отсортирован. Так как 2ⁱ > п при i > logn, то нетрудно заметить, что в этом случае будет достаточно [log n] + 1 проходов. Каждый проход требует чтения и записи двух файлов, длина каждого из них равна примерно n/2. Общее число блоков, прочитанных или записанных во время одного из проходов, составляет, таким образом, около 2п/b, где b — количество записей, умещающихся в одном блоке. Следовательно, количество операций чтения и записи блоков для всего процесса сортировки равняется О((n log n)/b), или, говоря по-другому, количество операций чтения и записи примерно такое же, какое требуется при выполнении O(log п) проходов по данным, хранящимся в единственном файле. Этот показатель является существенным улучшением в сравнении с О(п) проходами, которые требуются многим из алгоритмов сортировки.

Общий объем работы, выполняемой алгоритмом, по существу, пропорционален т + п, поэтому ясно, что слияние – более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подфайлы до тех пор, пока не будет отсортирован весь файл. Такой подход можно рассматривать как развитие идеи сортировки вставками: вставка нового элемента в упорядоченный файл – частный случай слияния при п = 1!

Сортировка методом естественного слияния

При использовании метода прямого слияния не принимается во внимание то, что исходный файл может быть частично отсортированным, т.е. содержать упорядоченные подпоследовательности записей. Серией называется подпоследовательность записей ai, a(i+1), ..., aj такая, что ak < = a(k+1) для всех i < = k < j, ai < a(i-1) и aj > a(j+1). Метод естественного слияния основывается на распознавании серий при распределении и их использовании при последующем слиянии.

Как и в случае прямого слияния, сортировка выполняется за несколько шагов, в каждом из которых сначала выполняется распределение файла A по файлам B и C, а потом слияние B и C в файл A. При распределении распознается первая серия записей и переписывается в файл B, вторая - в файл C и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C, вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла A. Процесс завершается, когда в файле A остается только одна серия.

Пример:

Начальное состояние файла A	8 23 5 65 44 33 1 6
Первый шаг Распределение Файл B Файл C Слияние: файл A	8 23, 44, 1 6 5 65, 33 5 8 23 44 65, 1 6 33
Второй шаг Распределение Файл B Файл C Слияние: файл A	5 8 23 44 65 1 6 33 1 5 6 8 23 33 44 65

Очевидно, что число чтений/перезаписей файлов при использовании этого метода будет не хуже, чем при применении метода прямого слияния, а в среднем - лучше. С другой стороны, увеличивается число сравнений за счет тех, которые требуются для распознавания концов серий. Кроме того, поскольку длина серий может быть произвольной, то макс. размер файлов B и C может быть близок к размеру файла A.

Сортировка методом многопутевого слияния

Основой метода является распределение серий исходного файла по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия.

Пример сортировки слиянием: Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.

Начальное состояние файла А	6 5 3 1 8 7 2 4
Первый шаг (сравнили соседние элементы и отсортировали)	5 6, 1 3, 7 8, 2 4
Второй шаг (сравнили соседние элементы и отсортировали - по 2)	1 3 5 6, 2 4 7 8
Итог (сравнили соседние элементы и отсортировали – остальные 4)	1 2 3 4 5 6 7 8

Многофазная сортировка

При использовании рассмотренного выше метода сбалансированной многопутевой внешней сортировки на каждом шаге примерно половина вспомогательных файлов используется для ввода данных и примерно столько же для вывода сливаемых серий. Идея многофазной сортировки состоит в том, что из имеющихся m вспомогательных файлов (m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода образуемых серий. Как только один из файлов ввода становится пустым, его начинают использовать для вывода серий, получаемых при слиянии серий нового набора (m-1) файлов. Таким образом, имеется первый шаг, при котором серии исходного файла распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое слияние серий из (m-1) файла, пока в одном из них не образуется одна серия.

Пример:

Начальное состояние файла А	4 2 9 0 5 1 6 3 8 7
Первый шаг Файл B Файл C	2 4 1 5 7 8 0 9 3 6
Второй шаг Файл B Файл C	0 2 4 9 7 8 1 3 5 6
Третий шаг Файл B Файл C	0 1 2 3 4 5 6 9 7 8
Слияние и выход в файл А	0 1 2 3 4 5 6 7 8 9

Время внешней сортировки зависит от: внутренней сортировки частей файла; многократного считывания и записи данных на диск; ходов головки между актами считывания/записи; действий в памяти при слиянии упорядоченных частей.

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

Рассмотрим случай, когда " узким местом" является слияние, а не считывание или запись данных. Это может произойти по следующим причинам.

1. если в нашем распоряжении есть много дисководов или накопителей на магнитной ленте, ввод-вывод можно ускорить настолько, что время для выполнения слияния превысит время ввода-вывода.

2. использование накопителей с высокой скоростью чтения/записи (SSD).

2. Может стать экономически выгодным применение более быстродействующих каналов обмена данными.

Поэтому имеет смысл подробнее рассмотреть проблему, с которой можно столкнуться в случае, когда " узким местом" в процессе сортировки слиянием данных, хранящихся во вторичной памяти, становится их объединение. Сделаем следующие предположения.

1. Мы объединяем серии, размеры которых намного превышают размеры блоков.

2. Существуют два входных и два выходных файла. Входные файлы хранятся на одном внешнем диске (или каком-то другом устройстве, подключенном к основной памяти одним каналом), а выходные файлы — на другом подобном устройстве с одним каналом.

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

С учетом этих предположений рассмотрим класс стратегий слияния, которые предусматривают выделение в основной памяти нескольких входных буферов (место для хранения блока). В каждый момент времени какой-то из этих буферов будет содержать невыделенные для слияния записи из двух входных серий, причем одна из них будет находиться в состоянии считывания из входного файла. Два других буфера будут содержать выходные записи, т.е. выделенные записи в надлежащим образом объединенной последовательности. В каждый момент времени один из этих буферов находится в состоянии записи в один из выходных файлов, а другой заполняется записями, выбранными из входных буферов. Выполняются (возможно, одновременно) следующие действия.

1. Считывание входного блока во входной буфер.

2. Заполнение одного из выходных буферов выбранными записями, т.е. записями с наим-ми ключами среди тех, которые в настоящий момент находятся во входном буфере.

3. Запись данных другого выходного буфера в один из двух формируемых выходных файлов.

В соответствии с нашими предположениями, эти действия занимают одинаковое время. Для обеспечения максимальной эффективности их следует выполнять параллельно. Это можно делать, если выбор записей с наименьшими ключами не включает записи, считываемые в данный момент.

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒