18. Ожидаемое число остановок есть Es>iP гдера - вероятность того, что необходимо не менее s остановок. Пусть дз - 1 - Ps+i - вероятность того, что необходимо не более S остановок. Тогда из упр. 17 следует, что < f{s - 1 + [s = 0]), где f{s) = Ь\"а/(Ьп)\ и q = n{{b+m)elb)\ Если f{t-\) < 1 < f{t), то E.>iP- > Pi + • • Н-Р* = t-(go + - • •+gt-i) > t - + /(0) + • • + /(t - 2)) > t - (q1-« + q1-« + • + q-i) >< - 1 > L - 1.

19. Осуществляя анализ, выполните шаг (vii) в обратном направлении, распределяя записи сначала в ящик 1, а затем - в ящик 2. Это именно та операция, которая моделируется в отношении файла ключей на шаге (iv). [Princeton Conference on Information Sciences and Systems 6 (1972), 140-144.]

20. Следует серьезно отнестись к выбору метода внутренней сортировки, учитывая ограничения, которые нак-тадываются страничной организацией. Такие методы, как метод Шелла с уменьшением смещения, вычисление адреса, пирамидальная сортировка и сортировка списка, вряд ли приемлемы, если мал реальный объем оперативной памяти, поскольку при их реализации потребуется большое число "рабочих страниц" Методы быстрой сортировки, обменной поразрядной сортировки и последовательно распределяемого слияния или поразрядной сортировки значительно лучше "себя чувствуют" в страничной среде.

Существуют определенные нюансы, которые можно учитывать при создании алгоритмов внешней сортировки, но которые исключаются при использовании автоматической системы распределения страниц: (i) выбор на основе предсказания файла исходных данных, который должен читаться следующим, чтобы нужные данные оказались загруженными к тому моменту, когда в них появится необходимость; (ii) выбор размера буфера п порядка слияния в соответствии с характеристиками оборудования и данных.

С другой стороны, виртуальная машина значительно упрощает программирование и с ее помощью можно получить неплохие результаты, если программист работает аккуратно и учитывает возможности той реальной вычислительной системы, для которой разрабатывается программа. Первое достаточно полное исследование этой проблемы выполнено Браун (Brawn), Густавсоном (Gustavson) и Манкиным (Mankin) [САСМ 13 (1970), 483-494.]

21. \{L-j)/D]; см. CMath, формула (3.24).

22. После считывания группы из D блоков, которые содержат aj, понадобится знать Oj+D-i прежде, чем будет выполнено считывание следующей группы из D блоков. Если хранить Oj+D-i с оу, то понадобятся также значения ао, ап-2 в виде некоторого заголовка файла с тем, чтобы начать процесс.

Но, следуя этой схеме, невозможно записать блоки оо...ав 1 до тех пор, пока не будет вычислено ар .агв-а- Таким образом, потребуется 3D - 1 выходных буфера вместо 2D для того, чтобы продолжительное время сохранять записываемую информацию. Отсюда следует, что лучше записать значения а в отдельный короткий файл. [Такие же соображения можно привести и по отношению к рандомизированному разделению.]

23. (а) Для реализации алгоритма 5.4.6F требуется 4 входных буфера, каждый объемом, соответствующим размеру суперблока DB. (Если к этому прибавить еще и буфера вывода, то в сумме получится 6DJ3 записей в буферах оперативной памяти в случае использования алгоритма 5.4.6F и 5DJ3 - в случае использования алгоритма SyncSort.)

(b) В то время, когда считывается группа из D блоков, нужно иметь в своем распоряжении пространство для буферов, чтобы хранить предыдущие D блоков и один незавершенный блок, т. е. (2D -I- 1)В записей. (Для вывода требуется еще 2DJ3, но в результате многих операций обработки данных в ходе выполнения 2-путевого слияния на практике передается на выход сравнительно небольшой объем информации.)

24. Пусть блоком в хронологическом порядке будет блок ji серии ki, в частности ji = О и ki = I при 1 < I < Р- Этот блок будет считываться в момент времени t; = ЕГ=1 Д

tikd = \{r\l<r<lHkr = kH(xk+jr) modD = d}

есть число блоков серии к на диске d, которые хронологически < / и d = (хк, + ji) mod D. Пусть Uifc = {г I 1 < г < / и /Сг = к}\; тогда

tikd -

uik - (d - Xk) mod D

поскольку jr пробегает значения О, 1, ..., uik - 1, если 1 < г < I и кг = к. Последовательность tl для примера из (19)-(21) есть

11111 22223 43456 34567 82345 67893 ....

После того как начнется слияние с 1-го в хронологическом порядке блока, количество необходимых блоков в буферах будет составлять Ii + D + Р, если I > Р. Здесь /( есть число "инверсий с равенством" в tj, а именно - \{г \ г > I и tr < ti}\, т. е. число заполненных буферов, в которые мы считали информацию, но еще не готовы ее использовать; D представляет буфера, в которые будут считываться следующие исходные данные, и Р - частично заполненные буфера, из которых берутся данные для слияния. (Приняв некоторые специальные меры, можно, используя связи, как в случае с алгоритмом SyncSort, ослабить последнее требование с Р до Р - 1, но усложнение процесса, которое при этом происходит, вряд ли сделает такую операцию целесообразной.)

Таким образом, проблема сведена к определению верхней оценки Можно предположить, что входные серии имеют бесконечно большую длину. Предположим также, что S в элементах {ti,..., t(} больше, чем ti; тогда ti имеет tiD - I + s инверсий с равенством, поскольку точно tiD элементов < t;. Отсюда следует, что максимум /; получается, когда S = О и ti есть максимум слева направо. Имеем ЕГ=1 ~ значит, учитывая приведенные выше формулы, для ti получаем

/, < max(t,D - О < (wifc - (d - Хк) mod D + D - 1 - Щк)

= P{D - 1) - (d - Xk) modD

<P<D-1)- min (d-xk) mod D

и существуют хронологические порядки, для которых достижима эта верхняя оценка.

Предположим, что rt кз Хк равны t. Желательно выбрать Хк таким образом, чтобы максимизировать mino<d<D sj, где Sd = J2k=i( ~ f) ~ J2t=o(( ~ ) )*-Можно предположить, что минимум будет при d = 0. Тогда si = so -\- Р - riD, S2 =

Si+P-riD, Отсюда получаем п < [P/D\, ri +Г2 < [2P/D\, ..., поэтому минимумом

является

so = {D- 1)п + (£) - 2)г2 + + < xilfcP/DJ = к(Р - l)(D - 1) + gcd(P, D)-l),

что вытекает из результатов упр. 1.2.4-37. Эта граница достигается, когда Xj = [jD/P] - 1 при 1 < j < Р.

Имея такое Xj, можно работать с любой хронологической последовательностью на полной скорости, если в нашем распоряжении есть /max -i- D + Р = PD + + Р +

I gcd(P, D) - 1 входных буферов, в каждом из которых отведено место для В записей. (Это особенно хорошо, когда D = 2 или 3.)

25. Обратите внимание на то, что в цикле 4 мы возвращаемся к чтению fi с диска 0.

Цикл 1 Цикл 2 Цикл 3 Цикл 4 Цикл 5 Цикл 6 Цикл 7 Цикл 8

Активные чтения Активные слияния

еоЬодоаоСо--------

fidodidifo ао-------

02/1062513 oobocodo----

fiCibigiai aobocodocofogoho 02/2/116352 aoboCodiCifogoho diasfsbiCi aibiCodsCifigiho 0261004 63/251/10 026101463/251/10

сюз/з 7 64 ? d,de ? ?

Прочие В ожидании

(-------) ao

ЬоСо(ео5о---) do

60/050(12/1-) ho

diidiCidsfigiai) 61

diCidsai fibi gi{) 02

/2бз(/г152---) di

(/11625213/364-) Cl

/г1Ь252аз/зб4( ? ) ds

26. В TO время, когда D блоков считываются и D блоков записываются, процедура слияния могла бы сформировать до Р + (5 - 1 блоков на выход, предполагая выполнение схемы (24). (Но не Р + Q, поскольку только один буфер слияния будет абсолютно пуст.) Считывание выполняется с той же скоростью, что и запись, а потому необходимо D + Р + Q - 1 буферов вывода для предотвращения задержки вывода.

Однако в среднем не более D блоков являются выводными для калсдых входных D блоков, так что на практике нужно ориентироваться примерно на 3D выходных буферов.

27. (а) Еп{гп1,... ,тр) = J2tLi4t, где qt есть вероятность того, что в некоторой урне содержится не менее t шаров. Очевидно, что qt < 1 и

< Рг(урна к содержит не менее t шаров) = nPr(5n(mi,..., тпр) > t).

(b) Производящая функция вероятностей для 8п{тп1,..., тПр) такова: piz) = flz-{l + iz-l)n/n),

где qk - [mkln\ и rk = mk mod п. Теперь 1 + а < (1 + а/п)" и 1 + аг/п < (1 + а/пУ, когда а > 0; отсюда имеем Pr(5„(mi,..., Шр) > t) < (1+ а)"р(1+ «) < {1 + а)~* ПГ=1(1 + а/п)""" ={1 + а)~*{1 + а/п)".

Если t <т/п, используется член "1" в сформулированном минимуме. Если t > т/п, величина (1 -I- а)~{1 + а/п)" принимает минимальное значение (п - l)"~m"/(n"t(m - t)"~), когда а = (nt - т)/{т -1).

28. Как нам кажется, числовой подсчет подтверждает это предположение. Например, получим

29. (a) В момент t со всех дисков считываются блоки, которые появятся не ранее, чем блок, маркированный в момент t. Следующие Q блоков никогда не будут удалены из группы прочих буферов, если они прочитаны. Таким образом, интересующие нас блоки на