ном порядке. Собственные команды, изменяющие размер записей, могут затруднить совмещение некоторых операций ввода-вывода в осциллирующей сортировке.

Генераторы сортировки заботятся о таких системных деталях, как соглашения о метках на лентах; они также часто обеспечивают подсчет контрольной суммы или иные проверки того, что никакая часть файла не пропала и не изменилась. Иногда имеются средства для остановки сортировки в удобных местах и возобновления ее позднее. Самые высококачественные генераторы позволяют записям иметь динамически меняющиеся длины [см. D. J. Waks, САСМ 6 (1963), 267-272].

*Слияние с меньшим числом буферов. Мы видели, что 2Р + 2 буферов достаточно для поддержания быстрого движения лент в течение Р-путевого слияния. В завершение этого раздела проведем математический анализ времени слияния в том случае, когда в нашем распоряжении имеется меньше 2Р + 2 буферов.

Очевидно, что желательно иметь два буфера вывода - можно будет выполнять запись из одного буфера, образуя в это же время следующий блок вывода в другом. Поэтому можно вообще не рассматривать вопрос вывода и заняться только вводом.

Допустим, имеется Р + Q буферов ввода, где 1 < Q < Р. Воспользуемся для описания нашей ситуации моделью, предложенной в работе L. J. Woodrum, IBM Systems J. 9 (1970), 118-144. Чтение одного блока ленты занимает одну единицу времени. Обозначим через ро вероятность того, что в течение этого времени ни один из буферов ввода не станет пустым, через pi - что один буфер станет пустым, через р>2 - что два или больше буферов станут пустыми и т. д. По завершении чтения ленты мы оказываемся в одном из Q + 1 состояний.

Состояние 0. Q буферов пусты. Мы начинаем читать блок подходящего файла в один из них, используя метод прогнозирования, описанный ранее в этом разделе. Через один такт времени мы переходим в состояние 1 с вероятностью ро, в противном случае остаемся в состоянии 0.

Состояние 1. Q - I буферов пусты. Начинаем выполнять чтение в один из них, предсказывая подходящий файл. Через один такт времени переходим в состояние 2 с вероятностью ро, в состояние 1 с вероятностью pi и в состояние О с вероятностью р>2.

Состояние Q - 1. Один буфер пуст. Начинаем выполнять чтение в него, предсказывая подходящий файл. Через один такт времени переходим в состояние Q с вероятностью ро, в состояние Q - 1 с вероятностью pi, в состояние 1 с вероятностью Pq-i и в состояние О с вероятностью p>q.

Состояние Q. Все буфера заполнены. Чтение лент останавливается в среднем на тактов времени, и затем мы переходим в состояние Q - 1.

Начинаем с состояния 0. Модель этой ситуации соответствует марковскому процессу (см. упр. 2.3.4.2-26), который можно проанализировать с помощью производящих функций следующим интересным способом. Пусть z - произвольный параметр, и предположим, что каждый раз, когда мы решаем осуществлять чтение с ленты, делаем это с вероятностью г:, а с вероятностью l - z завершаем выполнение алгоритма. Пусть 9q{z) - 1]„>о о5,г:"(1 - z) - среднее число появлений в этом процессе состояния Q; отсюда следует, что а"* - это греднее число появлений

состояния Q, если было прочитано ровно п блоков. Тогда п + а\(л - среднее суммарное время, затраченное на ввод и вычисления. Если бы имелось полное совмещение, как в алгоритме с (2Р + 2) буферами, то суммарное время включало бы только п единиц, так что ар представляет время задержки чтения.

Пусть Aij - вероятность того, что мы переходим из состояния i в состояние j в этом процессе при О < г, j < Q + 1, где Q + 1 - новое состояние "остановки" Например, при малых Q матрицы А будут следующими:

Q = l:

Q = 2:

g = 3:

Из упр. 2.3.4.2- 26(b) имеем, чтоgqiz) = coiactoiQo{I-A)/det{I-A). Так, например, если Q = 1, имеем

gi {z) = det

/О -1 О

/1 -p>iz -1

V о

-Poz 1 О

l-piz-poz 1-z

= PYnpoz-{l-z),

n>0

так что йп"* = npo- Это, конечно, очевидно заранее, так как при Q = 1 задача очень проста. Аналогичное вычисление для Q - 2 (см. упр. 14) дает менее очевидную формулу:

„(2) р1п Ро(1-рГ)

(10)

В общем случае можно показать, что о)» имеет вид afn + 0(1) при п ос, где константу а*) не слишком трудно вычислить (см. упр. 15). Как оказывается, a()=pl/{{l-pi?-p,P2).

Исходя из природы слияния, довольно разумно предположить, что /х = 1/Р, и мы имеем биномиальное распределение

Например, если Р = 5, то ро = .32768, pi = .4096, рг = -2048, рз = .0512, р4 = -0064 и р5 = .00032; следовательно, а) « 0.328, а) 0.182 и а) « 0.125. Другими словами, если мы используем 5 + 3 вводных буферов вместо 5 + 5, то можно ожидать дополнительного времени "задержки чтения" порядка 0.125/5 « 2.5%.

Конечно, эта модель - только очень грубое приближение. Мы знаем, что при Q - Р вообще нет времени задержки, но если судить по модели, то есть. Дополнительное время задержки чтения для меньших Q почти точно уравновешивает вьшгрыш в накладных расходах, получаемый от использования более крупных блоков, так что выбор простой схемы с Q = Р кажется оправданным.

УПРАЖНЕНИЯ

1. [13] Выведите формулу для вычисления точного числа символов на ленте, если в каждом блоке содержится п символов. Считайте, что лента могла бы вместить ровно 23 ООО ООО символов, если бы не было междублочных промежутков.

2. [15] Объясните, почему первый буфер файла 2 в строке 6 на рис. 84 совсем пуст.

3. [20] Будет ли алгоритм F работать должным образом, если вместо 2Р буферов ввода имеется только 2Р-1? Если да, докажите это; если нет, приведите пример, когда алгоритм не выполняется.

4. [20] Как изменить алгоритм F, чтобы он работал и при Р = 1?

>• 5. [21] Если в различных файлах имеются равные ключи, необходимо в процессе прогнозирования действовать очень аккуратно. Объясните, почему. Покажите, как избежать трудностей, если более строго определить операции слияния и прогнозирования в алгоритме F.

6. [22] Какие изменения при работе с Т +1 лентами следует сделать в алгоритме 5.4.3С, чтобы преобразовать его в алгоритм каскадного слияния с совмещением перемотки? • 7. [26] Начальное распределение в примере 7 диаграммы А порождает

(AiI3i)" Di(AiDiy° Зl(AlЗl) A(AiA)

на лентах 1-4, где (AiDi) означает AiDiAiDiAiDiAiDiAiDiAiDiAiDi. Покажите, как вставить дополнительные серии Ло и Do наилучшим из возможных способов (в том смысле, что общее число обрабатываемых во время слияния начальных серий будет минимальным), чтобы привести распределение к следующему виду:

A(DAy* (DAf (DA) (DA).

Указание. Чтобы сохранить четность, необходимо вставлять серии Ао и Jo в виде соседних пар. Числа слияния для каждой начальной серии могут быть подсчитаны, как в упр. 5.4.4-5; здесь появляется некоторое упрощение, так как соседние серии всегда имеют соседние числа слияния.

8. [20] На диаграмме А видно, что большинство схем начального распределения серий (за исключением начального распределения для каскадного слияния) имеет тенденцию к помещению последовательных серий на различные ленты. Если бы последовательные серии попали на одну ленту, то мы могли бы сэкономить стартстопное время. Можно ли поэтому считать продуктивной идею изменения алгоритмов распределения так, чтобы они реже переключали ленты?

9. [22] Оцените, сколько времени заняло бы выполнение многофазного алгоритма с обратным чтением из показанных на диаграмме А, если бы для сортировки использовались все Т = 6 лент, а не Г = 5, как в примере 7. Было ли разумно избегать использования