5 - время в секундах, необходимое оператору для снятия и замены вводной ленты,

Bi - число символов в блоке нерассортированного ввода. Во - число символов в блоке рассортированного вывода.

Для MIXT имеем т = 1/60000, р = 2/5, а = 300, 7 = 480. В примере, рассмотренном выше, = 100000, С = 100, М = 100000, 6 = 30, = В„ = 5000. Обычно именно эти характеристики оборудования и данных решающим образом влияют на время сортировки (хотя время перемотки часто задается более сложным выражением, чем просто коэффициентом р). Имея указанные параметры и схему слияния, вычислим еще некоторые величины:

Р - максимальный порядок слияния в схеме,

Р - число записей в дереве выбора с замещением,

5 - число начальных серий,

7г = а In 5 + /3 - приблизительное среднее число чтений и записей каждого символа, не считая начального распределения и окончательного слияния,

тг = а 1п5 -Ь /3 - приблизительное среднее число перемоток каждого символа во время промежуточных фаз слияния,

В - число символов в блоке в промежуточных фазах слияния,

Ui,u,Uo - "коэффициенты накладных расходов" - действительное время, необходимое для чтения или записи в пересчете на один символ (с учетом промежутков и стартстопного времени), отнесенное к общему времени т.

В примерах диаграммы А размеры блоков и буферов выбраны в соответствии с формулой

С, (1)

. С{2Р + 2).

чтобы блоки могли быть максимально большими при условии совместимости со схемой буферизации алгоритма F. (Во избежание ненужных забот во время последнего прохода величина Р должна быть достаточно малой, чтобы (1) обеспечило В > Во-) Размер дерева во время выбора с замещением будет, следовательно, таковым:

Р = {М -2Bi-2B)/C. (2)

Для случайных данных число начальных серий можно оценить формулой

опираясь на результаты раздела 5.4.1. Предполагая, что Bi < В и что вводная лента во время распределения может работать с полной скоростью (см. ниже), распределение начальных серий займет примерно NCuiT с, где

iJi = {Bi + j)/Bi. (4)

Во время слияния схема буферизации допускает совмещение чтения, записи и вычислений, но при частом переключении вводных лент необходимо учитывать и старт-стопное время; поэтому положим, что

= (5-Ь7 + т)/5, (5)

и время слияния оценим формулой

{7r + p7r)NCuJT. (6)

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

Wo = (Во + -/)/Во. (7)

Можно оценить время вьшолнения последнего слияния и перемотки как

пС{1 + p)uJot;

на практике оно могло бы быть несколько больше из-за наличия неравных блоков (ввод и вывод не синхронизированы, как в алгоритме F), но это время будет, в основном, одинаково для всех схем слияния.

Прежде чем переходить к более специфическим формулам для отдельных схем, попробуем обосновать два из сделанных выше предположений.

a) Может ли система, реализующая выбор с замещением "поспеть" за вводной лентой? В примере на диаграмме А, вероятно, может, так как дня выбора новой записи требуется около десяти итераций внутреннего цикла алгоритма 5.4.1R и в нашем распоряжении время Cwjt > 1667 мкс, за которое следует выполнить эти итерации. Тщательно запрограммировав цикл выбора с замещением, можно достичь этого на многих компьютерах (что и происходило даже в 70-х годах). Заметим, что при слиянии положение несколько менее критическое: время вычисления для одной записи почти всегда меньше времени работы НМЛ при Р-путевом слиянии, так как Р не очень велико.

b) Должны ли мы на самом деле выбирать в качестве В максимально возможный размер буфера, как задано в формуле (1)? Выбрав большой размер буфера, можно сократить отношение издержек w в (5), но при этом увеличится число начальных серий 5, так как Р уменьшается. Сразу и не скажешь, какой фактор важнее. Рассматривая время слияния как функцию от а; = CP, можно выразить его в виде

\ \ x 6/ ) \в4-х)

для некоторых подходящих констант 61,62,63,64, причем 63 > 64. Дифференцирование по x показывает, что есть некоторое Nq, такое, что для всех N > No невыгодно увеличивать х за счет размера буфера. В примерах, приведенных на диаграмме А, Ао оказалось, грубо говоря, равным 10 ООО; при сортировке более 10 ООО записей большой размер буфера предпочтительнее.

Заметим, однако, что при сбалансированном слиянии число проходов резко изменяется, когда S "проходит" через степень Р. Если заранее известно приближенное значение Л, то размер буфера следует выбрать таким, чтобы 5 с большой вероятностью оказалось немного меньше степени Р. Например, размер буфера для первого графика диаграммы А был равен 12 500, так как 5 = 78. Это было вполне удовлетворительно, но если бы 5 оказалось равным 82, было бы значительно лучше немного уменьшить размер буфера.

Формулы для десяти примеров. Возвращаясь к диаграмме А, попытаемся вывести формулы, аппроксимирующие время работы для каждого из десяти методов. В большинстве случаев основная формула

NCuJiT -ь (тг -ь p-k)NCu)t -ь (1 -ь p)NCuJcT (9)

будет достаточно хорошим приближением к суммарному времени сортировки, если мы определим число промежуточных проходов слияния тг = a\nS + Р и число промежуточных проходов перемотки тг = alnS + j3. Иногда необходимо внести в (9) некоторую поправку; специфика каждого метода учитывается следующим образом.

Пример 1. Сбалансированное слияние с прямым чтением. Формулы

тг = [In S/ln Р] - 1, тг = [In 5/ln Р] /Р могут использоваться для Р-путевого слияния с 2Р лентами.

Пример 2. Многофазное слияние с прямым чтением. Можно положить тг «тг, так как за каждой фазой обычно следует перемотка приблизительно такой же длины, как предшествующее слияние. Из табл. 5.4.2-1 получаем в случае шести лент значения а й 0.795, /3 « 0.864 - 2. (Значение 2 вычитается из-за того, что элементы таблицы включают наряду с промежуточными проходами также начальный и конечный.) К значению, полученному по формуле (9), нужно добавить время перемотки вводной ленты после начального распределения, а именно - рМСилт+6.

Пример 3. Каскадное слияние с прямым чтением. Из табл. 5.4.3-1 следуют значения а я 0.773, -р « 0.808 - 2. Время перемотки сравнительно трудно оценить; возможно, предположение тг я тг достаточно точно отражает суть дела. Как и в примере 2, нужно добавить к (9) время начальной перемотки.

Пример 4. Многофазное слияние с расщеплением лент. Из табл. 5.4.2-6 получаем а я 0.752, j3 я 1.024 - 2. Происходит совмещение почти всех операций перемотки, за исключением перемотки после начальной установки {pNCuJiT + S) и двух фаз вблизи конца (36% от 2pNCujT). Мы можем также вычесть 0.18 из /3, так как первая половина фазы совмещается с начальной перемоткой.

Пример 5. Каскадное слияние с совмещением перемоток. Здесь, используя табл. 5.4.3-1 для Г = 5, получаем а я 0.897, Р я 0.800-2. Почти все несовмещенные операции перемотки встречаются непосредственно после начального распределения и после каждого двухпутевого слияния. После точного начального распределения самая длинная лента содержит примерно 1/д всех данных, где д есть отношение роста. После каждого двухпутевого слияния объем перемотки в случае шести лент