Таблица 1

ХАРАКТЕРИСТИКИ ОПТИМАЛЬНОГО ДЕРЕВА Лш(гг), кш{п), КОГДА а0 = 1

яния - за почти 5 мин; в итоге имеем 12.4 мин. Если использовать выбор с замещением, то оптимальное дерево для 5 = 64 оказывается одинаково неинтересным (два прохода 8-путевого слияния); начальный распределительный проход осуществляется примерно за 3.5 мин, каждый проход слияния - примерно за 4.5 мин, а оценка общего времени составляет 12.6 мин. Не забудьте, что в обоих этих методах фактически полностью исключается совмещение чтения/записи/вычислений с тем, чтобы иметь большие буфера (для уменьшения времени поиска). Ни одна из этих оценок не включает время, которое может потребоваться для операций контрольного чтения.

На практике последний проход слияния отличается от остатшных; например, выводные данные часто редактируются и/или записьшаются на ленту. В таких случаях дерево, изображающее схему слияния, следует выбирать с использованием иного критерия оптимальности в корневом узле.

*Подробности об оптимальных деревьях. В теоремах Н и К интересно рассмотреть предельный случай, когда = О, несмотря на то что на практике обычно возникает соотношение между параметрами вида О < а < . Какое дерево с п листьями имеет наименьшую возможную длину степенного пути? Любопытно, что в этом случае наилучшим оказывается 3-путевое слияние.

Теорема L. Длина степенного пути дерева с п листьями никогда не будет меньше, чем

, Г37п + 2(п-3«), если2-3«-1 <п<3«; " 137п + 4(п-3»), если 39 < п < 2 • 39.

Тернарные деревья Тп, определенные правилами Tl -\ I, 72= (), Тп =

□ □

имеют минимальную длину степенного пути.

Доказательство. Обратите внимание на то, что /(п) - выпуклая функция, т. е.

/(п + 1)-/(п) >/(п)-/(п-1) при всех п> 2. (8)

Это свойство существенно в соответствии со.следующей леммой, которая двойственна результату упр. 2.3.4.5-17.

Лемма С. Функция д{п), определенная на положительных целых числах, удовлетворяет условию

nnnJgik)+gin-k))g{\ n/2\)+g{\n/2]), п>2, (9)

тогда и только тогда, когда она выпуклая.

Доказательство. Если д{п + 1) - д{п) < д{п) - д{п - 1) при некотором п > 2, то имеем д{п -Ь 1) -Ь д{п - 1) < д{п) -Ь д{п), что противоречит (9). Обратно, если (8) выполняется для д и если \ <к < п - к, то в силу выпуклости д{к-\-1) + д{п - к - 1) < д{к) + д{п-к). I

Последнюю часть доказательства леммы С можно обобщить для любого т>2 и показать, что

min {g{ni) + + д{пт))

niH-----НПт=П

Ш ,...,Ппг >1

= 9{\п1т\) + д{[{п+1)1т\) + ... + д([(п + m - l)/mj), (10)

если д выпукла. Пусть

frnin) = /(KmJ) + / (L(n + l)/mj) + ... + / (L(n + m - l)/mj). (11)

Доказательство теоремы L будет полным, если убедиться, что fz{n) -Ь Зп = /(п) и fm{n) + тп > f{n) при всех т>2 (см. упр. 11).

Было бы очень хорошо, если бы оптимальные деревья всегда характеризовались так же четко, как в теореме L. Но результаты для а = р, которые приведены в табл. 1, показывают, что функция Ai{n) не всегда выпукла. На самом деле данные, приведенные в табл. 1, достаточны, чтобы опровергнуть большинство простых предположений об оптимальных деревьях! Мы, однако, можем спасти часть теоремы L для общего случая. М. Шлюмбергер (М. Schlumberger) и Ж. Вуйлемен (J. Vuillemin) показали, что высоких порядков слияния всегда можно избежать.

Теорема М. Если даны а и /3, как в теореме Н, то существует оптимальное дерево, в котором степень любого узла не превосходит

(12)

Доказательство. Пусть rii,..., Пт - положительные целые числа, такие, что щ +

+ Пт = П, .Цщ) + + А{Пт) = Лт{п) Я Щ < < Пт, И ПредПОЛОЖИМ, ЧТО

т > d{a,/3) + 1. Пусть к - значение, при котором достигается минимум в (12); покажем, что

ап{т - к) + рп + Ат-к{п) < апт + рп + Л„(п), (13)

и, следовательно, минимум в (4) всегда достигается при некотором т < d{a,/3). По определению, поскольку т > к + 2, мы должны иметь

Ат-к{п) < Ai{ni + ---+nk+l) + Ai{nk+2) + --- + Ai{nm)

< а(п1 + - + Пк+1){к+1)+р{п1 + -- + nk+i) + Ai{ni) + -- + Ai(n„) = {a{k + l)+l3){ni+---+nk+i) + Am{n)

< {а{к+1)+р){к+1)п/т + Ат{п).

Отсюда легко выводится (13). (Тщательный анализ этого доказательства показывает, что оценка (12) является "наилучшей из возможных" в том смысле, что некоторые оптимальные деревья должны иметь узлы степени d{a,p); см. упр. 13.)

Для построения в теореме К требуется 0{N) ячеек памяти и 0{N\ogN) шагов для вычисления Ат{п) при l<m<n<7V;B теореме М показано, что необходимо только 0{N) ячеек и 0{N) шагов. Шлюмбергер и Вуйлемен открыли еще несколько очень интересных свойств оптимальных деревьев [Acta Informatica 3 (1973), 25-36]. Величина асимптотического выражения для Ai{n) выводится, как продемонстрировано в упр. 9.

*Еще один способ распределения буферов. В работе David Е. Ferguson, САСМ 14 (1971), 476-478, показано, что можно уменьшить время поиска, если не делать все буфера одного размера. Та же мысль и примерно в то же время пришла в голову еще нескольким авторам [S. J. Waters, Сотр. J. 14 (1971), 109-112; Ewing S. Walker, Software Age 4 (August-September, 1970), 16-17].

Предположим, что мы выполняем 4-путевое слияние серий равной длины Lq, располагая оперативной памятью объемом М символов. Если разделить память на равные буфера размером В = М/5, то придется выполнить около Lq/B операций поиска дл*я каждого входного файла и ALq/B операций поиска для выходного, что в сумме дает 8Lo/В = 40Lo /М операций поиска. Но если использовать четыре буфера ввода размером М/6 и один буфер вывода размером М/3, то потребуется всего лишь около 4 X (6Lo/M) -ь 4 X (3-Lo/M) = 36Lo/M операций поиска! Время передачи в обоих случаях одно и то же, так что мы ничего не потеряем от этого изменения.

В общем случае предположим, что необходимо слить рассортированные файлы длиной L\,... ,Lp в рассортированный файл длиной Lp+i = Li + + Lp, и предположим, что для к-го файла используется буфер объемом В к. Тогда

Bi + --- + Bp + Bp+i = М, (14)

где М - общий объем наличной оперативной памяти. Число операций поиска будет приблизительно равно