Содержимое файла 2 Го2 05

Номер строки Буфера файла 1 1 -01 03 К-

Буфера файла 2 ->02 05 <-

03 -> 04 09 <- -> 05 <-

09 <-

-> 05 Н 06 07 К-

-> 091<- -> 07[->08 10к-

-> 09->11 13К- -Н 10 К-

->11 13 К- -> 1-12 14 К-

-Н 1316 18 К- -Н иК-

Затем исходные данные читаются из 1-го файла

2-го файла

2-го файла

1-го файла

2-го файла

1-го файла

2-го файла

Рис. 84. Очереди буферов в соответствии с алгоритмом F.

алгоритма F, поскольку мы не смогли бы продолжить работу в строке 4, если бы в строке 3 выбрали файл 1 для ввода вместо файла 2.

Чтобы доказать работоспособность алгоритма F, мы должны проверить выполнение двух условий во время реализации алгоритма:

i) всегда имеется свободный буфер (т. е. всегда можно найти к на шаге F4);

ii) если буфер ввода исчерпывается во время слияния, то его преемник уже присутствует в памяти (т. е. ЗСС[г]] на шаге F2 имеет осмысленное значение).

Допустим, что условие (i) не выполняется, т. е. все буфера заняты в некоторый момент, когда мы достигаем шага F4. Каждый раз, когда мы приходим к этому шагу, суммарный объем необработанных данных во всех буферах составляет ровно Р емкостей буфера, т. е. данных ровно столько, сколько нужно для заполнения Р буферов, ибо данные вводятся и выводятся с одинаковой скоростью. Некоторые буфера заполнены лишь частично, однако для каждого файла частично заполнен максимум один буфер, так что всего таких буферов не более Р. По предположению все 2Р буферов заняты, так что по меньшей мере Р из них должны быть заполнены целиком. Это может случиться, только если Р буферов полны и Р пусты, иначе мы бы имели слишком много данных. Но максимум один буфер может быть одновременно пуст и недоступен; следовательно, условие (i) не может не выполняться.

Допустим, что условие (ii) не выполняется, т. е. для некоторого файла в памяти нет необработанных записей, но текущий буфер вывода еще не полон. Согласно принципу прогнозирования нужно иметь не более одного блока данных для всех остальных файлов, так как мы не читаем блок из файла, если этот блок не потребуется прежде, чем будут исчерпаны буфера какого-нибудь другого файла. Таким образом, общее число необработанных записей составляет максимум Р - 1 блоков; добавление неполного буфера вывода дает привод к менее чем Р буферным емкостям данных в памяти; значит, получено противоречие.

Этот анализ подтверждает работоспособность алгоритма F; он также показывает, что возможны особые ситуации, при которых алгоритм едва-едва избегает

крушения. Нами здесь не упомянута еще одна важная тонкость, касающаяся возможного равенства ключей; это обсуждается в упр. 5. [См. также упр. 4, в котором рассматривается случай Р = 1.]

Один из способов изящного завершения алгоритма F состоит в присвоении LCm] значения оо на шаге F3, если только что прочитанный блок был последним в серии. (Конец серии всегда некоторым особым образом помечается.) После того как будут прочитаны все данные во всех файлах, мы, в конце концов, обнаружим на шаге F4, что все L равны оо; тогда обычно можно начать чтение первых блоков следующих серий в каждом файле, выполняя начальную установку для следующей фазы слияния по мере вывода последних Р Н-1 блоков.

Таким образом, можно поддерживать полную скорость работы выводной ленты, осуществляя чтение в любое время не более одной ленты. Исключение из этого правила встречается на шаге F1, где было бы полезно читать сразу несколько лент, чтобы обеспечить возможность начать работу; но обычно шаг F1 можно организовать так, чтобы он совмещался с предыдущей частью вычислений.

Идея просмотра последней записи каждого блока, чтобы предсказать, какой буфер первым станет пустым, была высказана в 1953 году Ф. Э. Гольбертон (F. Е. Но1-berton). Сам метод впервые был опубликован в работе Е. Н. Friend, JACM 3 (1956), 144-145,165. В этом довольно сложном алгоритме использовалось ЗР буферов ввода и каждому файлу ввода предназначалось по три буфера. Алгоритм F несколько более совершенен, поскольку в нем используются плавающие буфера, что позволяет, таким образом, любому одному файлу потребовать сразу даже Р-Ь1 буферов ввода, хотя всего требуется не более 2Р буферов. Слияние с менее чем 2Р буферами обсуждается в конце этого раздела. Некоторые интересные подходы к совершенствованию алгоритма F рассматриваются в разделе 5.4.9.

Сравнительный анализ схем слияния. Используем теперь наши знания о лентах и слиянии, чтобы сравнить эффективность различных схем слияния, рассмотренных в разделах 5.4.2-5.4.5. Будет весьма поучительно проанализировать детально каждый метод в применении к одному и тому же примеру. Рассмотрим поэтому сортировку файла, каждая запись которого содержит 100 символов, причем в памяти для записи данных доступно 100,000 символьных ячеек (не считая места для программы, ее вспомогательных переменных и сравнительно небольшого пространства, необходимого для ссылок в дереве выбора). Исходные данные расположены на ленте в случайном порядке блоками по 5 ООО символов, и результат должен получиться в том же формате. В нашем распоряжении имеется пять рабочих НМЛ в дополнение к устройству, на котором находится вводная лента.

Общее число сортируемых записей - 100,000, но эта информация алгоритму сортировки заранее не известна.

В диаграмму А (здесь и далее см. вкладку) сведены те операции, которые выполняются, когда к нашим данным применяется десять различных схем слияния. Обратившись к этой важной иллюстрации, очень полезно вообразить, что вы наблюдаете за реальной сортировкой: медленно просматривайте каждую строку слева направо, мысленно представляя себе шесть лент, осуществляющих чтение, запись, перемотку и/или обратное чтение, как указано на диаграмме. В течение Р-путевого слияния вводные ленты будут находиться в движении в 1/Р раз реже, чем выводная лента. Заметим, что на диаграмме А предполагается, что, когда пер-

воначальная вводная лента полностью прочитана (и перемотана, чтобы ее убрать), умелый оператор снимает ее и заменяет рабочей лентой за 30 с. В примерах 2-4 это и есть время критического пути, когда компьютер в бездействии ожидает оператора. Но в остальных примерах операция снятия и установки лент совмещена с другой работой. (На диаграмме А по горизонтали указано время в минутах.)

Пример 1. Сбалансированное слияние с прямым чтением. Напомним описание задачи: записи имеют длину 100 символов, внутренней памяти достаточно для одновременного хранения 1 ООО записей и каждый блок вводной ленты содержит 5 ООО символов (50 записей). Всего имеется 100,000 записей (что равно 10,000,000 си.мволов или 2 ООО блоков).

Мы ничем не связаны в выборе размера блоков для промежуточных файлов. При шестиленточном сбалансированном слиянии используется трехпутевое слияние, так что техника алгоритма F требует 8 буферов; можно, следовательно, использовать блоки, содержащие по 1000/8 = 125 записей (или 12 500 символов).

Проход начального распределения может использовать выбор с замещением (алгоритм 5.4.1R), и, чтобы поддерживать непрерывную работу лент, будем использовать два буфера ввода по 50 записей плюс два буфера вывода по 125 записей. Это оставляет для дерева выбора место объемом 650 записей. Большая часть начальных серий будет, следовательно, иметь длину около 1 300 записей (10 или И блоков); на диаграмме А получилось 78 начальных серий, причем последняя серия короткая.

При первом проходе слияния, как показано, сливаются 9 серий на ленту 4, а не чередуются ленты 4-6. Это дает возможность выполнять полезную работу в то время, когда оператор вычислительной машины устанавливает рабочую ленту на устройство 6; так как общее число серий S известно сразу после завершения начального распределения, то алгоритм знает, что на ленту 4 должно быть слито [5/9] серий, затем [(5 - 3)/9] - на ленту 5, затем ("(5 - 6)/9] - на ленту 6.

Вся процедура сортировки в этом примере может быть изображена с использованием обозначений, введенных в разделе 5.4.2, следующим образом:

26 -26 j26

- - - 3 3 3« дЗ дЗ 9201

- - - 271 271 241 781

Пример 2. Многофазное слияние с прямым чтением. Второй пример на диаграмме А иллюстрирует многофазное слияние в соответствии с алгоритмом 5.4.2D. В этом случае мы выполняем пятипутевое слияние, поэтому память разбита на 12 буферов по 83 записи. В течение первоначального выбора с замещением мы имеем два буфера ввода объемом 50 записей и два буфера вывода объемом 83 записи, что оставляет 734 записи в дереве; таким образом, начальные серии на этот раз будут иметь длину около 1 468 записей (17 или 18 блоков). В данной ситуации получено 5 = 70 начальных серий, причем длины двух последних в действительности равны только четырем блокам и одному блоку соответственно. Схему слияния можно изобразить так: