..........;.....:...........,

Диаграмма А. Слияние на лентах

Обозначения ZZZZl Чтение в прямом направлении kwwi Чтение в обратном направлении ШШЛ Запись в прямом направлении

I......I Перемотка в обратном направлении

loool Смена ленты оператором

Удивительно, но для многофазного слияния необходимо на 25 с больше, чем для значительно более простого сбалансированного слияния! Это объясняется двумя основными причинами.

1) Этот случай особенно удачен для сбалансированного слияния, так как 5 = 78 очень близко к точной степени 3. Если бы было получено 82 начальные серии, то сбалансированное слияние потребовало бы еще одного прохода.

2) При многофазном слиянии теряется 30 с во время замены вводной ленты и в целом свыше 5 мин проходит в ожидании завершения операций перемотки. В противоположность этому сбалансированное слияние требовало сравнительно небольшого времени перемотки. Во второй фазе многофазного слияния сэкономлено 13 с, так как 8 фиктивных серий на ленте 6 можно считать присутствующими даже во время перемотки этой ленты, но затем не происходит никакого совмещения перемотки. Таким образом, многофазный метод проигрывает, несмотря на то что он требует значительно меньшего времени чтения/записи.

Пример 3. Каскадное слияние с прямым чтением. Этот случай аналогичен предыдущему, только в нем используется алгоритм 5.4.3С:

701 - - - -

(Просматривая диаграмму А, не забывайте представлять каждый пример в действии.)

Пример 4. Многофазное слияние с расщеплением лент. Эта процедура, описанная в конце раздела 5.4.2, позволяет совместить большую часть времени перемотки. Она использует четырехпутевое слияние, так что мы делим память на 10 буферов по 100 записей; в дереве выбора имеется 700 записей, и в результате оказывается, что образовано 72 начальные серии. Последняя серия вновь очень короткая. Использована схема распределения, аналогичная представленной в алгоритме 5.4.2D, за ней следует простой, но в некоторой степени специализированный метод размещения фиктивных серий:

121 119 115 18 021»

02117 02115 021" 021* - 02194"

721

Среди всех примеров на диаграмме А, в которых не используется чтение в обратном направлении, в этом, как оказывается, наилучшее время выполнения. Поскольку 5 никогда не бывает очень большим, можно разработать более сложный алгоритм, который позволит разместить фиктивные серии еще лучше (см. упр. 5.4.2-(26)).

Пример 5. Каскадное слияние с совмещением перемоток. Эта процедура работает почти так же быстро, как предыдущая, хотя управляющий ею алгоритм более прост. Мы используем для начального распределения метод каскадной сортировки, как в алгоритме 5.4.3С, но с Г = о, а не Г = 6. Затем использование лент в каждой фазе каждого "каскада" чередуется таким образом, что мы обычно не выполняем запись на ленту, пока она почти наверняка не окажется перемотанной. Короче говоря, схема такова:

221 22 jio

1* 1 - - 122235 410 72 - 8 7282 - 41 - 251 - 81 221 iQi

Пример 6. Сбалансированное слияние с обратным чтением. Этот пример похож на пример 1, но все перемотки устранены:

Af Af - - -

43 43 4241

Лд Лд Лд /Ig

D\ Dl Dl

Dl, Dl, Dl,

Так как в примере 1 было сравнительно мало перемоток, эта схема не намного лучше, чем в случае прямого чтения. Фактически она оказывается несколько медленнее многофазной схемы с расщеплением лент, несмотря на удачное значение 5 = 78.