AOP_Tom3 (1021738), страница 85
Текст из файла (страница 85)
Гольбертон (Г. Е. Но1- Ьегсоп). Сам метод впервые был опубликован в работе Е. Н. Гг1епс1, 1АСМ 3 (1956), 144 — 145, 165. В этом довольно сложном алгоритме использовалось ЗР буферов ввода и каждому файлу ввода предназначалось по три буфера. Алгоритм Г несколько более совершенен, поскольку в нем используются плавающие буфера, что позволяет, таким образом, любому одному файлу потребовать сразу даже Р+ 1 буферов ввода, хотя всего требуется не более 2Р буферов. Слияние с менее чем 2Р буферами обсуждается в конце этого раздела.
Некоторые интересные подходы к совершенствованию алгоритма Г рассматриваются в разделе 5.4.9. Сравнительный анализ схем слияния. Используем теперь наши знания о лентах и слиянии, чтобы сравнить эффективность различных схем слияния, рассмотренных в разделах 5.4.2 — 5.4.5. Будет весьма поучительно проанализировать детально каждый метод в применении к одному и тому же примеру. Рассмотрим поэтому сортировку файла, каждая запись которого содержит 100 символов, причем в памяти для записи данных доступно 100,000 символьных ячеек 1не считая места для программы, ее вспомогательных переменных и сравнительно небольшого пространства, необходимого для ссылок в дереве выбора).
Исходные данные расположены на ленте в случайном порядке блокамн по 5 000 символов, и результат должен получиться в том же формате. В нашем распоряжении имеется пять рабочих НМЛ в дополнение к устройству,на котором находится вводная лента. Общее число сортируемых записей — 100,000, но эта информация алгоритму сортировки заранее не известна. В диаграмму А (здесь и далее см. вкладку) сведены те операции, которые выполняются, когда к нашим данным применяется десять различных схем слияния. Обратившись к этой важной иллюстрации, очень полезно всабразить, что вы наблюдаете за реальной сортировкой: медленно просматривайте каждую строку слева направо, мысленно представляя себе шесть лент, осуществляющих чтение, запись, перемотку и/или обратное чтение, как указано иа диаграмме.
В течение Р-путевого слияния вводные ленты будут находиться в движении в 1/Р раз реже, чем выводная лента. Заметим, что на диаграмме А предполагается, что, когда пер- воначальная вводная лента полностью прочитана 1и перемотана, чтобы ее убрать). умелый оператор снимает ее и заменяет рабочей лентой за 30 с. В примерах 2 — 4 это и есть время критического пути, когда компьютер в бездействии ожидает оператора.
Но в остальных примерах операция снятия и установки лент совмещена с другой работай. (На диаграмме А по горизонтали указано время в минутах.) Пример 1. Сбалансированное слияние с прямым чтением. Напомним описание задачи: записи имеют длину 100 символов, внутренней памяти достаточно для одновременного хранения 1 000 записей и каждый блок вводной ленты содержит 5 000 символов (50 записей). Всего имеется 100,000 записей (что равно 10,000,000 символов или 2 000 блоков).
Мы ничем не связаны в выборе размера блоков для промежуточных файлов, При шегтиленточном сбалансированном слиянии используется трехпутевое слияние, так что техника алгоритма г требует 8 буферов; можно, следовательно, использовать блоки, содержащие по 1000/8 = 125 записей 1или 12 500 символов). Проход начального распределения может использовать выбор с замещением 1алгоритм 5.4.1Н), и, чтобы поддерживать непрерывную работу лент, будем использовать два буфера ввода по 50 записей плюс два буфера вывода по 125 записей.
Это оставляет для дерева выбора место объемом 650 записей. Ббльшая часть начальных серий будет, следовательно, иметь длину около 1 300 записей (10 или 11 блоков); на диаграмме А получилось 78 начальных серий, причем последняя серия короткая. При первом проходе слияния, как показано, сливаются 9 серий на ленту 4, а не чередуются ленты 4 — 6.
Это дает возможность выполнять полезную работу в то время, когда оператор вычислительной машины устанавливает рабочую ленту на устройство 6; так как общее числа серий 5 известно сразу погле завершения начального распределения, то алгоритм знает, что на ленту 4 должно быть слито Г5/9) серий, затем Ц5 — 3)/9) — на ленту 5, .затем ~(5 — 6)/9) — на ленту 6. Вся процедура сортировки в этом примере может быть изображена с использованием обозначений, введенных в разделе 5.4.2, следующим образом: 126 12Б Зэ Зэ 3" 93 9тб' 9з 27' 27' 24' 78 1 Пример 2. Миогофазное слияние с прямым чтением. Второй пример на диаграмме А иллюстрирует многофазное слияние в соответствии с алгоритмом 5.4.2Р. В этом случае мы выполняем пятипутевое слияние, поэтому память разбита на 12 буферов по 83 записи. В течение первоначального выбора с замещением мы имеем два буфера ввода объемом 50 записей в два буфера вывода объемом 83 записи, что оставляет 734 записи в дереве; таким образом, начальные серии на этот раз будут иметь длину около 1 468 записей (17 или 18 блоков).
В данной ситуации получено 5 = 70 начальных серий, причем длины двух последних в действительности равны только четырем блокам и одному блоку соответственно. Схему слияния можно изобразить так: о о о со орос е мотки оо с ос ос ос 1О. Многофазное слияние с прямым чтен ем Каскадное слияние с прямым чтением Многофазное слияние с расщепление лент Каскадное слияние с совмещением пе Сбалансированное слияние с обратны чтением Многофазное слияние с обратным чте ием Каскадное слияние с обратным чтени Осциллирующая сортировка с обратн м чтением Осцилпирующая сортировка с прямы чтением $ о ~Й ! $ В ДиаграммаА. Слияние на лентах Обозначения ПЕЛ Чтение в прямом направлении Е.'Л2 Чтение в обратном направлении 1МИ Запись в прямом направлении Е::Л Перемотка в обратном направлении пгтп;ц Смена ленты оператором 012112 18 013117 114 013115 11г 14 01з11в 115 17 1з 11 081421оз 1421 5з 2153 52 5' 48 ,14 42 4' 18 84 82 81 1г 16'19' 19' 34' 0' Удивительно, но для многофазного слияния необходимо на 25 с больше, челз для значит1шьно более простого сбалансированного слияния! Это объясняется двумя основными причинами.
1) Этот случай особенно удачен для сбалансированного слияния, так как Я = 78 очень близко к точной степени 3. Если бы было получено 82 начальные серии, то сбалансированное слияние потребовало бы еще одного прохода. 2) При многофазном слиянии теряется 30 с во время замены вводной ленты и в целом свыше 5 мин проходит в ожидании завершения операций перелютки. В противоположность этому сбалансированное слияние требовало сравнительно небольшого времени перемотки. Во второй фазе многофазного слияния сэкономлено 13 с, так как 8 фиктивных серий на ленте 6 можно считать присутствующими даже во время перемотки этой ленты, но затем не происходит никакого совмещения перемотки.
Таким образом, многофазный метод проигрывает, несмотря на то что он требует значительно меньшего времени чтения/записи. Пример 3. Каскадное слияние с прямым чтением. Этот случай аналогичен предыдущему, только в нем используется алгоритм 5.4,362 114 (м 11г 1ы 115 15 13 114 115 516з 5з бзбг — 12' 6' 18' 18' 1з2з38 22 161 70' (Просматривая диаграмму А, не забывайте представлять каждый пример в дей- ствии.) 121 118 115 18 — 01 02117 02115 02111 0214 021344 Пример 4.
Многофазное слияние с расщеплением лент. Эта процедура, описанная в конце раздела 5.4.2, позволяет совместить большую часть времени перемотки. Она использует четырехпутевое слияние, так что мы делим память на 10 буферов по 100 записей; в дереве выбора имеется 700 записей, и в результате оказывается, что образовано 72 начальные серии. Последняя серия вновь очень короткая. Использована схема распределения, аналогичная представленной в алгоритме 5.4.20, за ней следует простой, но в некоторой степени специализированный метод размещения фиктивных серий: 11з 110 111 1в 14 12 17 14 1в 15 1г 13' 13'14' 13'14' 141 18' 18' 27' 21 Среди всех примеров на диаграмме А, в которых не используется чтение в обратном направлении, в зтол1, как оказывается, наилучшее время выполнения.
Поскольку Я никогда не бывает очень большим, можно разработать более сложный алгоритм, который позволит разлгестить фиктивные серии езце лучше (см. упр. 5.4.2 — 126)). Пример 5. Каскадное слияние с совмещением перемоток. Эта процедура работает почти так же быстро, как предыдущая, хотя управляющий ею алгоритм более прост. Мы используем для начального распределения метод каскадной сортировки, как в алгоритме 5.4.3С, но с Т = 5, а не Т = 6.
Затем использование лент в каждой фазе каждого "каскада" чередуется таким образом, что мы обычно не выполняем запись на ленту, пока она почти наверняка не окажется перемотанной. Короче говоря, схема такова: 121 122 119 110 14 17 122235 4ш 4' 72 — 82 7282 26' — 8' 72' 221 161 Пример 6. Сбалансированное слияние с обратным чтением.
Этот пример похож на пример 1, но все перемотки устранены: А20 1 ,429 1 120 1 119 719 пу з Авз Аз А9Ав П27 Агв Так как в примере 1 было сравнительно мало перемоток, эта схема не намного лучше., чем в случае прямого чтения. Фактически она оказывается несколько медленнее многофазной схемы с расщеплением лент, несмотря на удачное значение Я = 78. 317г 3'7213' 3'7'13' 7213' 7' 13' 13' 44 4431 44 31 4з 423' 4'3' 3' 624' 624 3'4' 62443241 61443241 42324' 413241 314 3'4' 4' 021944 1944 1 4,14 1з44 14 42 ,12 Пример 7. Многофазное слияние с обратным чтением. В этом примере используется только пять лент из шести, чтобы устранить время перемотки и смены вводной ленты.
Таким образом, применяется только четырехпутевое слияние и такая же структу'ра буферов, как в примерах 4 и 5. Используется распределение, аналогичное приведенному в алгоритме 5.4.21У, но направление серий чередуется и лента 1 фиксируется, как конечная выводная лента. Сначала записывается восходящая серия на ленту 1., затем — нисходящие серии 2-4, после этого восходящие серии на ленты 2-4, нисходящие серии на ленты 1-3 и т. д, Всякий раз, когда переключается направление, выбор с замещением обычно дает более короткую серию, поэтому было образовано 77 начальных серий вместо 72 в примерах 4 и 5.
Эта процедура в результате дает распределение (22, 21, 19, 15) серий, а ближайшее точное распределение -- (29, 56, 52, 44). В упр. 5.4.4-5 показано, как построить строки чисел слияния, которые могут использоваться для размещения фиктивных серий оптимальным образом. Такая процедура может выполняться на практике, поскольку конечность бобины гарантирует, что Я никогда не будет слишком большим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
