Модификация каскадной сортировки. Если добавить еще одну ленту, то почти все операции перемотки в процессе каскадной сортировки можно совместить. Например, можно выполнить слияние Т1-Т5 на Т7, Т1-Т4 на Т6, Т1-ТЗ на Т5 (которая к этому моменту уже перемотана), Т1-Т2 на Т4 и начать следующий проход, когда на Т4 будет перемотано сравнительно немного данных. Эффективность этого процесса можно предсказать на основании изложенного выше анализа каскадного метода (подробности приводятся в разделе 5.4.6).

Схема "компромиссного слияния", которая включает многофазную и каскадную схемы как частные случаи, была предложена Д. Э. Кнутом в САСМ 6 (1963), 585-587. Каждая фаза состоит из (Т - 1)-, (Т - 2)-, ..., Р-путевого слияний, где Р - любое фиксированное число между 1 и Т - 1. Если Р = Т - 1, значит, это многофазный метод; если Р = 1, это чистый каскадный метод; если Р = 2, это каскадный метод без фаз копирования. Анализ такой схемы был проделан в работах С. Е. Radke, IBM Systems J. 5 (1966), 226-247, и W. Н. Burge, Ргос. IFIP Congress (1971), 1, 454-459. Бурж нашел производящую функцию Т„(а;)2" для каждого (Р, Т)-компромиссного слияния, обобщающую соотношение 5.4.2-(16). Он показал, что наилучшее значение Р (с точки зрения наименьшего числа обрабатываемых начальных серий) как функции от S при 5 -> оо (если непосредственно использовать схему распределения и пренебречь временем перемотки) есть соответственно (2,3,3,4,4,4,3,3,4) при Т = (3,4,5,6,7,8,9,10,11). Эти значения Р с ростом Г сильнее отклоняются в сторону каскадного, а не многофазного метода, и оказывается, что компромиссное слияние никогда не станет существенно лучше каскадного. С другой стороны, при оптимальном выборе уровней и распределении фиктивных серий, как описано в разделе 5.4.2, чистый многофазный метод кажется наилучшим среди всех компромиссных методов слияния. К сожалению, оптимальное распределение сравнительно трудно реализовать.

В работе Th. L. Johnsen, BIT 6 (1966), 129-143, исследовано сочетание сбалансированного и многофазного слияний; модификация сбалансированного слияния с совмещением перемоток предложена в работе М. А. Гоетца (М. А. Goetz), Digital Computer Users Handbook, M. Klerer, G. A. Korn (New York: McGraw-Hill, 1967), 1.311-1.312. Можно представить себе и многие другие гибридные схемы.

УПРАЖНЕНИЯ

1. [10] Используя табл. 1, сравните каскадное слияние с описанной в разделе 5.4.2 версией многофазного слияния с "расщеплением лент". Какой метод лучше? (Временем перемотки пренебречь.)

► 2. [22] Сравните метод каскадной сортировки с тремя лентами, использующий алгоритм С, и метод многофазной сортировки с тремя лентами, использующий алгоритм 5.4.2D. Какие сходства и различия вы заметите?

3. [23] Составьте таблицу, показывающую, что происходит при сортировке на шести лентах ста начальных серий при помощи алгоритма С.

4. [М20] (Дж. Н. Рэйни (G. N. Raney).) "Каскадное распределение п-го уровня" - мультимножество, определенное следующим образом (для шести лент): {1,0,0,0,0} есть каскадное распределение 0-го уровня; если на последующих уровнях {о, Ь, с, d, е} - каскадное распределение п-го уровня, то {a + b+c+d+e, a + b+c+d, a + b+c, a+b, a} будет каскадным распределением (п + 1)-го уровня. (Так как мультимножество не упорядочено.

из единственного распределения п-го уровня можно образовать до 5! различных распределений {п -I- 1)-го уровня.)

a) Докажите, что любое мультимножество {о, 6,с, d, е} из взаимно простых чисел является каскадным распределением п-го уровня при некотором п.

b) Докажите, что распределение, используемое в каскадной сортировке, оптимально в том смысле, что если {о, Ь, с, d, е} - любое распределение п-го уровня, причем о > 6 > с > d > е, то будем иметь о < Оп, Ь < Ьп, с < Сп, d < dn, е < вп, где (an,bn,Cn,dn,en) - распределение, определенное в (1).

► 5. [20] Докажите, что каскадные числа, определенные в (1), удовлетворяют закону

акап-к + ЬкЬп-к + СкСп-к + dkdn-k + вквп-к = «п при О < fc < п.

[Указание. Для лучшего понимания этого соотношения рассмотрите, сколько серий различной длины выводится в течение fc-ro прохода полной каскадной сортировки.]

6. [М20] Найдите матрицу Q размера 5x5, такую, что первая строка содержит каскадные числа для шести лент Un Ьп Сп dn вп при всех п > 0.

7. [М20] При условии, что каскадное слияние применяется к точному распределению Оп начальных серий, найдите формулу для величины сэкономленной работы, когда исключается однопутевое слияние.

8. [НМ23] Выведите формулу (12).

9. [Ш26] Выведите формулы (14).

► 10. [М28] Вместо системы (4) для изучения каскадных чисел воспользуйтесь в качестве исходных тождествами

Сп = ап-1 = lft{\)an-i,

dn = 2o„ i - en-2 = lft{l)an-i - ()оп-з,

Cn = 3on-i - dn-2 - 2en-2 = lft{l)an-i - (з)оп-з - {1)ап-ь

и т. д. Полагая

, . /т\ /т+1\ 3 , /т--2\ 5

выразите через эти г-многочлены A{z), B{z) и т. д.

11. [М38] Пусть

/»м = Ё(<"",""0

Докажите, что производящая функция A{z) для Т-ленточных каскадных чисел есть

fT-3{z)/fT-i{z),

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

12. [МО] Докажите, что схема распределения Фергюсона оптимальна в том смысле, что при любом другом методе размещения фиктивных серий, удовлетворяющем (2), во время первого прохода будет обрабатываться не меньше начальных серий при условии, что во время Этого прохода используется стратегия шагов С7-С9.

13. [40] В тексте раздела предполагается большую часть времени перемотки совмещать путем добавления дополнительной ленты. Попытайтесь развить эту идею. (Например, схема, приведенная в тексте, включает ожидание перемотки ленты Т4. Не будет ли лучше исключить Т4 из первой фазы слияния следующего прохода?)

Многие накопители на магнитных лентах позволяют читать ленту в направлении, противоположном тому, в котором осуществлялась запись. Рассмотренные ранее схемы слияния предполагают запись информации на ленту в прямом направлении, перемотку ленты, ее чтение в прямом направлении и еще одну перемотку. (Файлы на ленте, следовательно, ведут себя, как очереди "первым включается - первым исключается".) Чтение в обратном направлении (в дальнейшем будем для краткости назьтать эту операцию обратным чтением) позволяет обойтись без перемотки: запись на ленту вьшолняется в прямом направлении и считывается в обратном. (В этом случае файлы ведут себя, как стеки, поскольку здесь действует правило "последним включается - первым исключается".) Схемы сбалансированного, многофазного и каскадного слияний можно приспособить для обратного чтения. Основное отличие состоит в том, что слияние изменяет порядок серий, если считывание происходит в прямом направлении, а запись - в обратном. Если две серии находятся на ленте в порядке возрастания, то их можно слить, выполняя считывание в обратном направлении, однако при этом серии расположатся в порядке убывания. Полученные таким образом нисходящие серии станут восходящими на следующем проходе; следовательно, алгоритм слияния должен уметь работать с сериями обоих направлений. Программисту, впервые столкнувшемуся с обратным чтением, может показаться, что он стоит на голове!

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

Т1 Т2 ТЗ Т4

Проход! AiAiAiAi AiAiAiAi - - Начальное распределение

Проход 2 - - D2D2 D2D2 Слияние на ТЗ и Т4

Проход S Ai Ai - - Слияние на Т1 и Т2

Проход 4 - - Dg - Окончательное слияние на ТЗ

Здесь Аг обозначает серию, имеющую относительную длину г и расположенную в порядке возрастания, если лента читается в прямом направлении, как в предыдущих примерах; Dr - аналогичное обозначение для нисходящей серии длиной г. Во время второго прохода восходящие серии становятся нисходящими. Они оказываются нисходящими при вводе, так как мы читаем ленты Т1 и Т2 в обратном направлении. Серии вновь изменяют ориентацию на третьем проходе.

Заметим, что описанный процесс завершается формированием на ленте ТЗ результата в порядке убывания. Если это плохо (что зависит от того, должен ли результат читаться в обратном направлении или же лента, содержащая его, должна быть снята и отложена для использования в дальнейшем), можно скопировать его на другую ленту, изменив направление. Более быстрым способом была бы перемотка Т1 и Т2 после третьего прохода; при этом во время четвертого прохода получается As. Еще лучше было бы начать с восьми нисходящих серий на первом проходе, так как при этом поменялись бы местами все А и D. Однако для сбалансированного слияния 16 начальных серий потребовалось бы, чтобы начальные серии были восходящими, но поскольку обычно заранее неизвестно, сколько начальных серий будет