Лекция 14
Теория
Для определенности я буду считать, что данные располагаются на
одной или более бобин магнитной ленты. На рис. 4-1 иллюстрируется трехпутевое
многофазное слияние. В начале, на фазе А, все денные находятся на лентах Т1 и
Т2. Предполагается, что начало каждой ленты - внизу картинки. Имеется два
упорядоченных отрезка на Т1: 4-8 и 6-7. На ленте Т2 - один отрезок 5-9. На фазе
B мы сливаем первый отрезок с ленты Т1 (4-8) с первым отрезком Т2 (5-9) и
получаем более длинный отрезок на ленте Т3 (4-5-8-9). На фазе С мы просто
переименовываем ленты, так чтобы можно было повторить слияние. На фазе D мы
повторяем слияние, получив результат на ленте Т3.
Фаза
|
T1
|
T2
|
T3
|
A
|
7
6
8
4
|
9
5
|
|
B
|
7
6
|
|
9
8
5
4
|
C
|
9
8
5
4
|
7
6
|
|
D
|
|
|
9
8
7
6
5
4
|
Рис. 4-1. Сортировка слиянием
В приведенном тексте опущены некоторые интересные детали.
Например, как были созданы начальные возрастающие отрезки? Кроме того, вы
обратили внимание: они слиты так, что не потребовалось создавать дополнительные
отрезки? Перед тем, как я объясню, каким образом были созданы начальные
отрезки, позвольте мне слегка отвлечься.
В 1202 Леонардо Фибоначчи в книге Liber Abbaci (Книга об абаке) рассмотрел следующую задачу: Сколько
пар кроликов можно получить за год, если в начале была лишь одна пара? Предположим,
что каждая пара кроликов производит потомство каждый месяц, становится
способной к воспроизводству также за один месяц, а также, что кролики не мрут.
Спустя один месяц у нас будет 2 пары кроликов, спустя 2 месяца - 3 пары. Спустя
еще месяц исходная пара и пара, рожденная в 1-й месяц, дадут каждая по паре,
так что всего у нас будет 5 пар. Ряд, в котором каждый член является суммой
двух предыдущих членов, называется последовательностью Фибоначчи:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... .
Любопытно, что ряды Фибоначчи встречаются в самых разных
ситуациях - от изучения расположения цветов на растении до оценки эффективности
алгоритма Евклида. Неудивительно, что издается журнал Fibonacci Quarterly (Ежеквартальный Фибоначчи). И, как вы уже,
конечно, догадались, ряд Фибоначчи имеет прямое отношение к порождению
начальных отрезков при внешней сортировке.
Вспомним, что сначала у нас был один отрезок на ленте Т2 и два - на ленте Т1.
Обратите внимание - числа {1,2} являются двумя последовательными членами ряда
Фибоначчи. После первого слияния у нас появился один отрезок на Т1 и один на
Т2. Заметим, что числа {1,1} - тоже два последовательных члена ряда
Фибоначчи, только на шаг раньше. Мы, таким образом, готовы предсказать, что
если бы у нас было 13 отрезков на Т2 и 21 на Т1 {13,21}, то после одного
прохода у нас было бы 8 отрезков на Т1 и 13 на Т3 {8,13}. Последовательные
проходы привели бы нас к отрезкам {5,8}, {3,5}, {2,3}, {1,1} и {0,1}, т.е.
всего понадобилось бы 7 проходов. Этот порядок идеален, при нем требуется
минимальное число проходов. Если данные действительно находятся на ленте,
минимизация числа проходов очень важна, поскольку ленты может понадобиться снимать
и устанавливать после каждого прохода. В случае, когда имеется более двух лент,
применяются числа Фибоначчи высшего
порядка.
Сначала все данные располагаются на одной ленте. Лента читается
и отрезки распределяются по другим лентам, имеющимся в системе. после того, как
созданы начальные отрезки, они сливаются, как описано выше. Один из методов,
который можно использовать для создания начальных отрезков, состоит в чтении
порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать
более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в
оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги
до тех пор, пока не будут исчерпаны входные данные:
Выбрать запись с наименьшим ключом, т.е. с ключом, значение
которого
Если все "старые" ключи меньше последнего ключа, то
мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве
первого элемента следующего отрезка.
Записываем выбранную запись.
Заменяем выбранную и записанную запись на новую из входного файла.
На рис. 4-2 выбор с замещением иллюстрируются для совсем
маленького файла. Начало файла - справа. Чтобы упростить пример, считается, что
в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в
буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в
выходной файл запись с наименьшим номером = 6. На шаге D ею оказалась запись с
ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4.
Процесс продолжается до шага F, где оказывается, что последний записанный
ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование
текущего отрезка и начинаем формирование следующего.
Шаг
|
Вход
|
Буфер
|
Выход
|
A
|
5-3-4-8-6-7
|
|
|
B
|
5-3-4-8
|
6-7
|
|
C
|
5-3-4
|
8-7
|
6
|
D
|
5-3
|
8-4
|
7-6
|
E
|
5
|
3-4
|
8-7-6
|
F
|
|
5-4
|
3 | 8-7-6
|
G
|
|
5
|
4-3 | 8-7-6
|
H
|
|
|
5-4-3 | 8-7-6
|
Рис. 4-2. Выбор с замещением
Обратите внимание мы храним записи в буфере до тех пор, пока не
наступит время записать их в выходной файл. Если вход случаен, средняя длина
отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то
упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще
говоря, эффективен более промежуточных, частичных сортировок.
Прочитав из входного файла очередную запись, мы ищем наименьший
ключ, который = последнего считанного. При этом мы, конечно, можем просто
сканировать записи в буфере. Однако, если таких записей тысячи, время поиска
может оказаться недопустимо большим. Если на этом этапе использовать двоичные
деревья, нам понадобится всего лишь lg n
сравнений.
Реализация
В кодах внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для
получения нужной записи, а makeRuns
распределяет записи согласно ряду Фибоначчи. Если количество отрезков
оказывается вне последовательности Фибоначчи, в начало каждого файла
добавляются пустые отрезки. Затем
вызывается функция mergeSort,
которая производит многофазное слияние отрезков.
|