можно использовать ббльшие по размеру буфера, так что поиск потребуется выполнять реже. За счет этого часто компенсируется дополнительное время передачи, которое растет с уменьшением Р.

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

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

Последующий анализ, который должен продемонстрировать некоторые общие идеи, будет выполнен в предположении, что (i) на чтение или запись п символов требуется 72.5 + 0.005п мс; (ii) под рабочее пространство в оперативной памяти отводится объем, достаточный для хранения 100 ООО символов; (iii) для пересылки одного символа из буфера ввода в буфер вывода затрачивается в среднем 0.004 мс; (iv) совмещение чтения, записи и вычислений отсутствует; (v) размер буфера, используемого для вывода, необязательно равен размеру буфера, используемого для чтения данных на следующем проходе. Анализ задачи сортировки при этих простых предположениях будет полезен для понимания более сложных ситуаций.

Если вьшолняется Р-путевое слияние, можно разделить внутреннюю рабочую память на Р -f 1 буферных областей: Р - для ввода и 1 - для вывода; объем каждого буфера - В = 100000/(Р + 1) символов. Предположим, что в предназначенных для слияния файлах содержится в сумме L символов; значит, будет выполнено приблизительно L/B операций вывода и примерно столько же операций ввода. Следовательно, общее время слияния при таких предположениях будет равно (в миллисекундах) приблизительно

272.5 + 0.005l) + 0.004L = (0.00145Р + 0.01545)L. (2)

Иными словами, для Р-путевого слияния L символов необходимо примерно (аР + /3)Ь машинных циклов, где а я /3 - некоторые константы, зависящие от времени поиска, времени ожидания, времени вычислений и объема памяти. Эта формула приводит к интересному способу построения хороших схем слияния для дисков. Рассмотрим, например, рис. 92 и будем считать, что все начальные серии (изображенные квадратными "листьями") имеют длину Lq. Тогда каждое слияние в узлах 9 и 10 вьшолняется за (2а + /J)(2Lo) машинных циклов, слияние в узле 11 - за (За 4-/J)(4Lo) машинных циклов и окончательное слияние в узле 12 - за

4 I I 5

Рис. 92. Дерево с длиной внешнего пути 16 и длиной степенного пути 52.

(4а + p){8Lo) машинных циклов. Общее время слияния, следовательно, составляет {52a + 16/3)Lo машинных циклов. Коэффициент 16 нам хорошо известен: это просто длина внешнего пути дерева. Коэффициент 52 при а соответствует новому понятию, которое можно назвать длиной степенного пути дерева (degree path length). Эта длина равна взятой по всем листьям сумме степеней внутренних узлов, лежащих на пути от листа к корню. Например, на рис. 92 длина степенного пути равна (2 + 4) + (2 + 4) + (3 + 4) + (2 + 3 + 4) + (2 + 3 + 4) + (3 + 4) + (4) + (4) = 52.

Если Т - любое дерево, то пусть D(T) и Е{Т) обозначают соответственно длину степенного пути и длину внешнего пути этого дерева. Анализ сводится к следующей теореме.

Теорема Н. Если время, необходимое для выполнения Р-путевого слияния L символов, составляет (аР + P)L и если требуется слить S серий равной длины, то наилучшая схема слияния соответствует дереву Т, для которого aD{T) + РЕ{Т) минимально среди всех деревьев с S листьями.

(Эта теорема неявно содержалась в неопубликованной статье, которую Джордж А. Хаббард (George U. Hubbard) представил на Национальной конференции АСМ в 1963 году.)

Пусть аир - фиксированные константы. Будем говорить, что дерево опти-.мально, если оно имеет минимальное значение aD{T) + рЕ{Т) среди всех деревьев Т с тем же числом листьев. Нетрудно видеть, что все поддеревья оптимального дерева также оптимальны. Поэтому мы можем строить оптимальные деревья с п листьями, объединяя оптимальные деревья, у которых листьев меньше, чем п.

Теорема К. Пусть последовательность чисел Ат{п) определена при I < т < п такими правилами:

Ai{l)=0;

Ат{п) = min (A],{k)+Am-i{n-k)) при 2 < m < n;

1<к<п/т

Ai{n) = min [amn +/Зп + Am{n)) при n > 2.

2<m<n

(3) (4)

Тогда Ai{n) есть минимальное значение aD{T) + pE{T) среди всех деревьев Т с п листьями.

Доказательство. Из соотношения (4) следует, что Am (п) - минимальное значение

A\{ni)-\-----hi {пт) для всех положительных чисел ni,..., n„i, таких, что ni Н-----h

- п. Требуемый результат получается теперь индукцией по п.

Рекуррентные соотношения (3)-(5) можно использовать также для построения самих оптимальных деревьев. Пусть кт{п) - значение, для которого достигается минимум в определении Ат{п). Тогда можно построить оптимальное дерево с п листьями, объединяя т = ki{n) поддеревьев в корне. Поддеревья являются оптимальными деревьями с кт{п), кт-\{п - кт{п)), кт~2{п - кт{п) - km-i{n -кт{п))), ... листьями соответственно.

Эта конструкция при а = р = I проиллюстрирована в качестве примера в табл. 1. Краткие описания соответствующих оптимальных деревьев приводятся в правой части таблицы; элемент "4:9:9" для п = 22, например, означает, что оптимальное дерево Тгг с 22 листьями можно получить в результате объединения %, Тд я Тд (рис. 93). Оптимальное дерево не является однозначной структурой; например, элемент 5:8:9 был бы столь же хорошим, как и 4:9:9.

□ □□□□□□□□□□□□□□□

Рис. 93. Оптимальный способ слияния 22 начальных серий равной длины, если а = /3 в теореме Н. Эта схема позволяет минимизировать время поиска при предположениях, приведших к формуле (2).

Выражение (2) показывает, что всегда, когда используются Р + 1 буферов равных объемов, будет действительным соотношение а < р. Предельный случай, когда а = р, показанный в табл. 1 и на рис. 93, возникает тогда, когда необходимо минимизировать само время поиска безотносительно ко времени передачи.

Вернемся к нашей первоначальной задаче. Мы еще не выяснили, как получить начальные серии на первом месте; без совмещения чтения/записи/вычислений метод выбора с замещением теряет некоторые из своих преимуществ. Возможно, следует заполнить всю оперативную память, рассортировать данные в ней и вывести результат. Каждую из таких операций ввода и вывода можно выполнить с одним поиском. Или, возможно, лучше использовать, скажем, 20% оперативной памяти в качестве комбинированного буфера ввода-вывода и выполнить выбор с замещением. Это требует в пять раз больше поисков (дополнительно примерно 60 с или около того!), но позволяет уменьшить число начальных серий со 100 до 64; уменьшение будет еще более резким, если исходный файл уже почти упорядочен.

Если не использовать выбор с замещением, то оптимальное дерево для S = 100, а = 0.00145, р = 0.01545 [см. (2)] оказывается весьма прозаическим. Это просто 10-путевое слияние, выполняемое за два прохода по данным. Выделив 30 с на внутреннюю сортировку (скажем, 100 быстрых сортировок), получаем, что начальный распределительный проход выполняется примерно за 2.5 мин, а каждый проход ели-