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

Такую остроумную идею трудно до конца проанализировать, но в работе Т. О. Espelid, BIT 16 (1976), 133-142, показано, как распространить нашу аналогию с работой снегоочистителя на этот случай и получить соответствующую приближенную формулу. Как следует из выведенной формулы аппроксимации, длина серии будет равна примерно

2Р + {т

[2Р + {т-2)Ь\ -• [2Р + {2ш-3)ь)

если Ь - размер блока и m > 2. Эти данные довольно хорошо согласуются с проведенными практическими экспериментами. Такое увеличение длины нельзя считать достаточным для компенсации повышения сложности процесса. Но, с другой стороны, это может дать некоторые преимущества, когда существует возможность организовать довольно большое число буферов на второй фазе сортировки.

*Натуральный выбор. Другой путь увеличения длины серий, порождаемых выбором с замещением, был исследован в работе W. D. Frazer, С. К. Wong, САСМ 15 (1972), 910-913. Изложенная авторами идея состоит в том, чтобы следовать алгоритму R, кроме случая, когда в дерево включается новая запись, ключ которой меньше, чем LASTKEY. Тогда вывод направляется во внешний дополнительный буфер и считывается новая запись. Этот процесс продолжается до тех пор, пока в дополнительном буфере не окажется определенного количества записей Р. Тогда остаток текущей серии выводится из дерева, а элементы из дополнительного буфера используются в качестве исходных данных для следующей серии.

Рассмотренный метод должен порождать более длинные серии, чем метод выбора с замещением, поскольку он "обходит" вновь поступающие "мертвые" записи, вместо того чтобы позволять им заполнять дерево; но ему требуется дополнительное время на обмен с дополнительным буфером. Когда Р > Р, некоторые записи могут оказаться в этом буфере дважды, но при Р < Р такого случиться не может.

Фрэйзер и Уон, проведя обширные эмпирические испытания своего метода, заметили, что Р достаточно велико (скажем, Р > 32) и Р = Р, средняя длина серии для случайных данных оказывается равной еР, где е и 2.718 - основание натуральных логарифмов. Это явление, а также тот факт, что метод был получен в результате эволюции метода простого выбора с замещением, послужили авторам основанием для того, чтобы назвать свой метод натуральным выбором.

Можно доказать "натуральный" закон для длины серии, вновь воспользовавшись аналогией со снегоочистителем (см. рис. 64) и применив элементарный математический анализ. Пусть L обозначает длину пути, а x{t) - положение снегоочистителя в момент t при О < t < Т. Предположим, что в момент Т внешний буфер (резервуар) заполняется. В этот момент падение снега временно прекращается, пока снегоочиститель возвращается в исходное положение (счищая Р снежинок, оставшихся на его пути). Ситуация такая же, как и ранее, только "условия равновесия" другие: вместо Р снежинок на всей дороге мы имеем Р снежинок перед снегоочистителем и резервуар (за снегоочистителем), заполняющийся до уровня, равного Р = Р снежинок. В течение времени dt снегоочиститель продвигается на dx, если выводятся h{x, t) dx записей, где h{x, t) - толщина слоя снега в момент времени t в

<-L - X --H у Снег на входе

Рис. 67. Вводится и выводится равное количество снега; за время dt снегоочиститель перемещается на dx.

точке X = x{t), измеряемая в соответствующих единицах. Следовательно, h{x,t) = h{x, 0) + Kt для всех х. Так как число записей в памяти остается постоянным, то h{x, t) dx есть также число записей, вводимых перед снегоочистителем, а именно - Кdt{L - х), где К - скорость падения снега (рис. 67). Таким образом,

dx K{L - х)

dt h{x,t)

К счастью, оказывается, что h{x,t) - константа, равная КТ при всех х = x{t) и О < i < Т, так как снег падает равномерно в точку x{t) в течение T-t единиц времени после того, как снегоочиститель проходит эту точку, плюс t единиц времени перед тем, как он вернется. Иными словами, снегоочиститель все время видит перед собой одинаковый слой снега на протяжении всего пути, если допустить, что достигнут установившийся режим, т. е. этот путь всегда один и тот же. Следовательно, общее количество счищаемого снега (длина серии) составляет LKT, а количество снега в памяти есть количество снега, счищаемого после момента Т, а именно - KTiL - х{Т)). Решение.м уравнения (2) при условии, что х(0) = О, будет

x(t)=L(l-e-/). (3)

Следовательно, Р - LKTe~ - (длина серии)/е - как раз то, что и требовалось доказать.

В упр. 21-23 показано, что данный анализ можно распространить на произвольное Р; например, когда Р = 2Р, средняя длина серии оказывается равной е(е -в)Р, где в = (е - \/е - 4)/2. Это результат, который вряд ли можно было предвидеть заранее! В табл. 2 приводится зависимость между длиной серии и размером дополнительного буфера. С помощью этой таблицы можно оценить эффективность натурального выбора для конкретного компьютера в той или иной ситуации. Строки таблицы, соответствующие размеру дополнительного буфера < Р, получены с помощью несколько усовершенствованной методики, которая рассматривается в упр. 27.

Идеи преобразования серий с задержкой и натурального выбора можно скомбинировать, как описано в работе Т. С. Ting, Y. W. Wang, Сотр. J. 20 (1977), 298-301.

"Анализ выбора с замещением. Вернемся теперь к выбору с замещением без вспомогательного буфера. Аналогия со снегоочистителем дает довольно хорошую оценку средней длины серий, получаемых при выборе с замещением "в пределе" Тем не менее можно получить значительно более точную информацию об алгоритме R, используя результаты анализа серий в перестановках, который выполнен в разде-

Таблица 2

ДЛИНА СЕРИЙ ПРИ НАТУРАЛЬНОМ ВЫБОРЕ

Величина к -\- в определена в упр. 22 или (если = 0) в упр. 27.

ле 5.1.3. Для удобства будем считать, что входной файл является последовательностью произвольной длины независимых случайных чисел в диапазоне от О до 1. Пусть

gp{zuZ2,...,Zk)= ap{li,l2,---,lk)z[z2 ...zl

luh,-,lk>0

является производящей функцией для длины серии, которая получена при Р-путе-вом выборе с замещением, примененном к такому файлу, где ар(/i,/2,... есть вероятность того, что первая серия имеет длину /i, вторая - /2, к-я - /fc. Будем основываться на следующей "теореме независимости", так как она сводит наш анализ к случаю Р = 1.

Теорема К. gp{zi,z2, . , Zk) = gi{zi,Z2,... ,Zk).

Доказательство. Пусть исходные ключи суть Xi, Х2, Хз,.... Алгоритм R разделяет их на Р подпоследовательностей в соответствии с тем, в какой внешний узел дерева Они попадают. Подпоследовательность, содержащая Х„, определяется значениями Xi,..., Х„ 1. Таким образом, эти подпоследовательности являются независимыми последовательностями независимых случайных чисел, расположенных между О и 1. Кроме того, результат выбора С замещением в точности совпадает с результатом Р-путевого слияния, если его выполнить над этими подпоследовательностями. Некоторый элемент принадлежит j-й серии подпоследовательности тогда и только тогда, когда он принадлежит j-й серии, полученной при выборе с замещением (так как на шаге R4 ключи LASTKEY и KEY(Q) принадлежат одной подпоследовательности).

Иначе говоря, можно считать, что алгоритм R применяется к Р случайным независимым исходным файлам и что на шаге R4 считывается следующая запись из файла, соответствующего внешнему узлу Q. В этом смысле рассматриваемый алгоритм эквивалентен Р-путевому слиянию, при котором концы серий отмечаются "убыванием" элементов.

Таким образом, на выходе будут получены серии длиной (/i,...,/fc) тогда и только тогда, когда подпоследовательности состоят из серий длиной (/ц,... ,/ifc).