5. Если бы, например, все ключи во всех файлах были равны, то мы не могли бы просто делать произвольный выбор во время прогнозирования; прогноз должен быть совместим с решениями, принимаемыми процессом слияния. Возможный безопасный путь состоит в том, чтобы найти на шагах F1 и F4 наименьшее возможное тп, т. е. считать, что все записи из файла С[г] меньше, чем все записи, имеющие тот же ключ в файле C[j], если i < j. (В сущности, номер файла присоединяется к ключу.)

6. На шаге С1 установить также ТАРЕСТ +1] <- Г+ 1. На шаге С8 слияние должно идти на ТАРЕ[р + 2] вместо ТАРЕ[р+1]. На шаге СЭ установить (ТАРЕ[1],... ,ТАРЕ[Т+1]) •(-(ТАРЕ [Т+1],...,ТАРЕС1]).

7. Метод, показанный на диаграмме А, есть

(AiDi)AoDo(AiDifAoDo{AiDifAo,

Di(AiDi)AoDo{AiDifAoDoaAoDoAo, DiAoDoiAiDifAoDoaAiDiAo, DiAiDiaAiDiAo,

где q = {AoDofAiDiAoDo{AiDif{AoDoyAiDi(AoDofAiDiAoDo. Ha первой фазе слияния записывается DoAsDsAiDiAiDiAoDoAiDiAiDiAiDiAoDoAiDiAoDoiAiDiy на ленту 5; на следующей записывается AiDiAnDiAiDiAiDnAoDoAiDiAiDiAr на ленту 1, на следующей - D13A4D4A0D0A10 на ленту 4. Последние фазы таковы:

A4D4A4 - D19A3D3A12 D13A4D4A4 D0A3

Аа D23A11 D19A3 D13A4 -

- D23 Dig D13 D22

а77 - -

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

9. Р = 5, В = 8300, В = 734, 5 = "(3 + l/P)iV/(6P)l + I = 74, uj х 1.094, а я: 0.795, /9 и -1.136, а = Р = 0. Значение формулы (9) я 855 с, к которому мы добавляе.м время начальной перемотки, получая в итоге 958 с. Экономия примерно одной минуты во время слияния не компенсирует потерю времени из-за начальной перемотки и смены ленты (если мы не работаем в мультипрограммном режиме).

10. Во время стандартного многофазного слияния перематывается около 54% файла (столбец "Проходы/фазы" в табл. 5,4,2-1), а самая длинная перемотка в стандартном каскадном слиянии охватывает примерно aka„-k/an ~ (4/(2Т - 1)) cos(7r/(4T - 2)) < файла (из упр. 5.4.3-5 и соотношения 5.4.3-(13)).

11. Только для начальной и конечной перемоток имеет смысл использовать быструю перемотку, так как бобина, содержащая весь файл примера, заполнена лишь немногим более чем на 10/23. Применяя в примере 8 значения тг - f.946 In 5 - 1.204] и тг = 1/8, получаем следующие итоговые оценки для примеров 1-9:

1115, 1296, 1241, 1008, 1014, 967, 891, 969, 856,

12. (а) Очевидное решение с 4Р + 4 буферами состоит в том, чтобы просто одновременно выполнять чтение и запись на спаренные ленты. Заметим, однако, что достаточно трех буферов вывода (в любой момент мы выполняем вторую половину операции записи из одного, первую половину операции записи из второго и заполняем третий). Это наводит на мысль о соответствующем улучшении ситуации с буферами ввода. Оказывается, что

необходимо и достаточно ЗР буферов ввода и 3 буфера вывода, если использовать несколько ослабленный метод "прогнозирования" Лучший и более простой подход, предложенный Дж. Сю (J. Sue), позволяет добавить к каждому блоку "опережающий ключ", который определяет последний ключ следующего блока. Метод Сю требует 2Р --1 буферов ввода и 4 буфера вывода и является видоизмененным алгоритмом F. (См. также раздел 5.4.9.)

(Ь) В этом случае большое значение а означает, что число проходов по всем данным, которое мы должны выполнить, лежит между пятью и шестью, что сводит на нет преимущество слияния с двойной скоростью. Эта идея значительно лучше работает на восьми или девяти лентах.

13. Нет. Рассмотрите, например, положение непосредственно перед AieAieAieAie. Однако две полные бобины могут быть обработаны.

14. det

/О -poz О

0 1 - piz -poz

1 О О \0 О О

15. Матрица А имеет вид

/Bioz Buz

z-l\ z-l

fl-p>iz -poz -p>2Z 1-piz

-1 0

-poz 1 0

z-l\

1 J

BlnZ l-z\

BnOZ

0 . 0 .

BnlZ

. 0 . 0

BnnZ

1-z 0 0

Следовательно,

det(/ - A) = det

/1-Bioz -Bnz

-Bnoz 0

-BnlZ

Bio + Bii -I- • -I- Bin = 1,

Bno + Bni + --- + Bnnl

-Bl(n-1)2 -BinZ\

1 - Bn(n-l)Z -BnnZ

-1 1

(11)

и можно прибавить все столбцы к первому, а затем вынести (1 - г). Значит, дд(г) имеет вид /1д(г)/(1 - г) и а = /iq(1), поскольку /iq(1) О и det(/ - А) ф О для \z\ < 1.

РАЗДЕЛ 5.4.7

1. Выполняйте сортировку от младших цифр к старшим поочередно в системах счисления с основанниями Р иТ - Р. (Если сгруппированы пары цифр, то получим, в сущности, чистое основание Р (Т - Р). Так, если Р = 2 и Т = 7, то система счисления - двоично-пятеричная, которая очевидным образом связана с десятичными обозначениями.)

2. Если К - ключ, находящийся в диапазоне от О до Рп - 1, то пусть фибоначчиевым представлением Fn - 1 - К будет On-2Pn-i -I- • -I- aiF2, где aj равны О или 1 и нет двух последовательных единиц. После фазы j на ленте (j + l) mod 3 находятся ключи с Oj = О, а на ленте (j - 1) mod 3 - ключи с Oj = 1 в порядке убывания значений aj-i ... oi.

[Представьте сортировальную машину для перфокарт с карманами "О" и "1" и рассмотрите процедуру сортировки Fn карт, на которых перфорированы ключи Оп-2 ... ai в п-2 колонках. Обычная процедура их сортировки в порядке убывания, которая начинается с младшей цифры, может быть упрощена, поскольку все, что находится в кармане "1" в конце одного прохода, попадает на следующем проходе в карман "О".]

4. Если бы на уровне 2 находился внешний узел, то нам не удалось бы построить такое хорошее дерево. В противном случае на уровне 3 имеется самое большее три внешних узла, на уровне 4 - шесть, так как предполагается, что каждый внешний узел оказывается на одной и той же ленте.

6. 09, 08,

.., 10, 29, ..., 20, 39, ..., 30, 40, 41, ..., 49, 59, ...-, 50, 60, 61, ..., 99.

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

РАЗДЕЛ 5.4.8

1. Да. Пусть направления файла и дерева выбора чередуются от возрастающего к убывающему, тогда в результате получим шейкер-сортировку Р-го порядка (см. упр. 9).

2. Пусть Zn = Yn - Xn; решим рекуррентные соотношения для Zn , заметив, что

{N + 1)NZn+i = N{N - \)Zn + N + N;

следовательно,

Zn = 1(N+1)+(j/n{N-1) приМ>М.

Теперь исключим Yn и получим X

= (Я+1-Ям+2) + 2(

2/М-1-2 З V 3

N+1 М+2 1

ЗМ+4

{N+1)N(N-1) {М+2){М+1)М J М+2

N> М.

3. Да. Найдите элемент, который является медианой, за 0{N) шагов, используя построение, аналогичное приведенному в теореме 5.3.3L, и с его помощью разделите файл. Еще один интересный подход, предложенный Р. У. Флойдом (R. W. Floyd) и Э. Дж. Смитом (А. J. Smith), состоит в том, чтобы слить две серии из N элементов за 0{N) единиц времени следующим образом. Раздвиньте элементы на ленте, оставив между ними промежутки, затем последовательно занесите в каждый такой промежуток число, которое определяет конечное положение элемента, предшествующего этому промежутку.

4. Можно объединить график для этажей {1,...,р--1} с графиком для этажей {д,..., п}: когда по первому графику лифт впервые достигает этажа р -I- 1, то подняться на этаж q и действовать в соответствии со вторым графиком (считая текущих пассажиров лифта "дополнительными" людьми в алгоритме теоремы К). После выполнения этого графика вернуться на этаж р -I- 1 и возобновить прежний график.