%% 428
\input style
\subsubchap{дИСКИ И БАРАБАНЫ}
дО СИХ ПОР МЫ РАССМАТРИВАЛИ ЛЕНТЫ КАК ЕДИНСТВЕННОЕ СРЕДСТВО ДЛЯ ВНЕШНЕЙ
СОРТИРОВКИ, ОДНАКО НЕРЕДКО В НАШЕМ РАСПОРЯЖЕНИИ ОКАЗЫВАЮТСЯ И ДРУГИЕ
ТИПЫ УСТРОЙСТВ МАССОВОЙ ПАМЯТИ С БОЛЕЕ ГИБКИМИ ВОЗМОЖНОСТЯМИ. хОТЯ ТАКИЕ
ЗАПОМИНАЮЩИЕ .УСТРОЙСТВА "БОЛЬШОГО ОБЎЕМА" ИЛИ "ЗАПОМИНАЮЩИЕ УСТРОЙСТВА С
ПРЯМЫМ ДОСТУПОМ" ВЕСЬМА МНОГООБРАЗНЫ, МОЖНО ВЫДЕЛИТЬ СЛЕДУЮЩИЕ ОБЩИЕ СВОЙСТВА:
\medskip
\item{i)} дЛЯ ДОСТУПА К ЛЮБОЙ ОПРЕДЕЛЕННОЙ ЧАСТИ ХРАНИМОЙ ИНФОРМАЦИИ НЕ
ТРЕБУЕТСЯ ОЧЕНЬ МНОГО ВРЕМЕНИ.

\item{ii)} бЛОКИ, СОДЕРЖАЩИЕ ПОСЛЕДОВАТЕЛЬНЫЕ СЛОВА, МОГУТ
БЫСТРО ПЕРЕДАВАТЬСЯ МЕЖДУ ВНУТРЕННЕЙ (ОПЕРАТИВНОЙ) И ВНЕШНЕЙ ПАМЯТЬЮ.
\medskip
\noindent мАГНИТНАЯ ЛЕНТА УДОВЛЕТВОРЯЕТ (ii), НО НЕ (i), ПОСКОЛЬКУ
ПЕРЕХОД ЛЕНТЫ ОТ ОДНОГО КОНЦА К ДРУГОМУ ЗАНИМАЕТ МНОГО ВРЕМЕНИ. нЕКОТОРЫЕ
УСТРОЙСТВА УДОВЛЕТВОРЯЮТ (i), НО НЕ (ii); ПРИМЕРОМ МОЖЕТ СЛУЖИТЬ ПАМЯТЬ
БОЛЬШОГО ОБЎЕМА НА ФЕРРИТОВЫХ СЕРДЕЧНИКАХ,
\picture{рИС. 89. пАКЕТ ДИСКОВ}
В КОТОРОЙ ВРЕМЯ ДОСТУПА К КАЖДОМУ СЛОВУ ПРИМЕРНО В ДЕСЯТЬ РАЗ ПРЕВЫШАЕТ
ВРЕМЯ ДОСТУПА К ВНУТРЕННЕЙ ПАМЯТИ.

кАЖДОЕ ВНЕШНЕЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО ИМЕЕТ СВОИ ХАРАКТЕРНЫЕ
ОСОБЕННОСТИ, КОТОРЫЕ СЛЕДУЕТ ТЩАТЕЛЬНО ИЗУЧИТЬ, ПРЕЖДЕ ЧЕМ ПИСАТЬ ДЛЯ НЕГО
БОЛЬШИЕ ПРОГРАММЫ; ОДНАКО ТЕХНОЛОГИЯ МЕНЯЕТСЯ ТАК БЫСТРО, ЧТО ЗДЕСЬ НЕ
УДАСТСЯ СКОЛЬКО-НИБУДЬ ПОДРОБНО ОБСУДИТЬ ВСЕ СУЩЕСТВУЮЩИЕ РАЗНОВИДНОСТИ
ОБОРУДОВАНИЯ. пОЭТОМУ МЫ РАССМОТРИМ ЛИШЬ НЕКОТОРЫЕ ТИПИЧНЫЕ ЗАПОМИНАЮЩИЕ
УСТРОЙСТВА И НА .НИХ ПРОИЛЛЮСТРИРУЕМ ПРОДУКТИВНЫЕ ПОДХОДЫ К ЗАДАЧЕ СОРТИРОВКИ.

оДНИМ ИЗ НАИБОЛЕЕ РАСПРОСТРАНЕННЫХ ТИПОВ ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВ,
УДОВЛЕТВОРЯЮЩИХ (i) И (ii), ЯВЛЯЕТСЯ ДИСКОВЫЙ
%% 429
ФАЙЛ ИЛИ МОДУЛЬ С ПАКЕТОМ ДИСКОВ (РИС. 89). дАННЫЕ ХРАНЯТСЯ НА
НЕСКОЛЬКИХ БЫСТРО ВРАЩАЮЩИХСЯ КРУГЛЫХ ДИСКАХ, ПОКРЫТЫХ МАГНИТНЫМ
МАТЕРИАЛОМ; ДЛЯ ЗАПИСИ ИЛИ ВЫБОРКИ ИНФОРМАЦИИ ИСПОЛЬЗУЕТСЯ ДЕРЖАТЕЛЬ
ГОЛОВОК В ВИДЕ ГРЕБЕШКА. СОДЕРЖАЩИЙ ОДНУ ИЛИ НЕСКОЛЬКО "ГОЛОВОК
ЧТЕНИЯ/ЗАПИСИ" ДЛЯ КАЖДОЙ ПОВЕРХНОСТИ ДИСКА. кАЖДАЯ ПОВЕРХНОСТЬ ДЕЛИТСЯ НА
КОНЦЕНТРИЧЕСКИЕ КОЛЬЦА, НАЗЫВАЕМЫЕ \emph{ДОРОЖКАМИ} ИЛИ \emph{ТРЕКАМИ},
ТАК ЧТО ЗА ВРЕМЯ ОДНОГО ОБОРОТА ДИСКА ПОД ГОЛОВКАМИ ЧТЕНИЯ/ЗАПИСИ ПРОХОДИТ
ЦЕЛАЯ ДОРОЖКА. дЕРЖАТЕЛЬ ГОЛОВОК МОЖЕТ ПЕРЕМЕЩАТЬСЯ В ДВУХ
НАПРАВЛЕНИЯХ---ВНУТРЬ ИЛИ НАРУЖУ, ПЕРЕДВИГАЯ ГОЛОВКИ ЧТЕНИЯ/ЗАПИСИ ОТ
ДОРОЖКИ К ДОРОЖКЕ, НО ЭТО ДВИЖЕНИЕ ТРЕБУЕТ ВРЕМЕНИ. мНОЖЕСТВО ДОРОЖЕК,
КОТОРЫЕ МОГУТ БЫТЬ ПРОЧИТАНЫ ИЛИ ЗАПИСАНЫ БЕЗ ПЕРЕМЕЩЕНИЯ ДЕРЖАТЕЛЯ
ГОЛОВОК, НАЗЫВАЕТСЯ \emph{ЦИЛИНДРОМ}. нАПРИМЕР, НА РИС.~89 ПОКАЗАН
ДИСКОВЫЙ ФАЙЛ, КОТОРЫЙ ИМЕЕТ ПО ОДНОЙ ГОЛОВКЕ ЧТЕНИЯ/ЗАПИСИ НА КАЖДУЮ
ПОВЕРХНОСТЬ; ПУНКТИРНЫМИ ЛИНИЯМИ ОБОЗНАЧЕН ОДИН ИЗ ЦИЛИНДРОВ, СОСТОЯЩИЙ
ИЗ ВСЕХ ДОРОЖЕК, ПРОСМАТРИВАЕМЫХ В НАСТОЯЩИЙ МОМЕНТ ГОЛОВКАМИ.

чТОБЫ СДЕЛАТЬ НАШИ РАССУЖДЕНИЯ БОЛЕЕ КОНКРЕТНЫМИ, РАССМОТРИМ
ГИПОТЕТИЧЕСКОЕ ДИСКОВОЕ УСТРОЙСТВО |MIXTEC|, ДЛЯ КОТОРОГО
$$
\eqalign{
\hbox{1 ДОРОЖКА}& =\hbox{5000 ЛИТЕР,}\cr
\hbox{1 ЦИЛИНДР}& =\hbox{20 ДОРОЖЕК,}\cr
\hbox{1 ДИСКОВОЕ УСТРОЙСТВО}&= \hbox{200 ЦИЛИНДРОВ.}\cr
}
$$
тАКОЕ ДИСКОВОЕ УСТРОЙСТВО СОДЕРЖИТ 20 МИЛЛИОНОВ ЛИТЕР, Т. Е. ЧУТЬ МЕНЬШЕ
ТОГО ОБЎЕМА ДАННЫХ, КОТОРЫЙ МОЖНО ЗАПИСАТЬ НА ОДНУ МАГНИТНУЮ ЛЕНТУ. нА
НЕКОТОРЫХ МАШИНАХ ДОРОЖКИ ВБЛИЗИ ЦЕНТРА СОДЕРЖАТ МЕНЬШЕ ЛИТЕР, ЧЕМ ДОРОЖКИ
БЛИЖЕ К КРАЮ. оТ ЭТОГО ПРОГРАММИРОВАНИЕ ЗНАЧИТЕЛЬНО УСЛОЖНЯЕТСЯ, НО
|MIXTEC|, К СЧАСТЬЮ, НЕ СОЗДАЕТ ТАКИХ ПРОБЛЕМ.

вРЕМЯ, НЕОБХОДИМОЕ ДЛЯ ЧТЕНИЯ ИЛИ ЗАПИСИ НА ДИСКОВЫЙ ФАЙЛ, ПРЕДСТАВЛЯЕТ,
ПО СУЩЕСТВУ, СУММУ ТРЕХ ВЕЛИЧИН:
\itemize
\li вРЕМЯ ПОИСКА (ВРЕМЯ, ЗАТРАЧИВАЕМОЕ НА ПЕРЕМЕЩЕНИЕ ДЕРЖАТЕЛЯ ГОЛОВОК
К НУЖНОМУ ЦИЛИНДРУ).
\li вРЕМЯ ОЖИДАНИЯ (ЗАДЕРЖКА, СВЯЗАННАЯ С ВРАЩЕНИЕМ ДИСКА, ПОКА ГОЛОВКА
ЧТЕНИЯ/ЗАПИСИ НЕ ДОСТИГНЕТ НУЖНОГО МЕСТА).
\li вРЕМЯ ПЕРЕДАЧИ (ЗАДЕРЖКА, СВЯЗАННАЯ С ВРАЩЕНИЕМ ДИСКА, ПОКА ДАННЫЕ
ПРОХОДЯТ ПОД ГОЛОВКАМИ).
\itemend

нА УСТРОЙСТВАХ |MIXTEC| ВРЕМЯ ПОИСКА ДЛЯ ПЕРЕХОДА ОТ ЦИЛИНДРА $i$ К
ЦИЛИНДРУ $j$ РАВНО $25+{1\over2}\vert i-j \vert$ МС. еСЛИ $i$ И
$j$---СЛУЧАЙНО ВЫБРАННЫЕ ЦЕЛЫЕ ЧИСЛА МЕЖДУ 1 И 200, ТО СРЕДНЕЕ ЗНАЧЕНИЕ
%%430
$\vert i-j\vert$ РАВНО $2 \left( {201\atop 3}\right)/200^2\approx 66.7$,
Т. Е. СРЕДНЕЕ ВРЕМЯ ПОИСКА
СОСТАВЛЯЕТ ПРИБЛИЗИТЕЛЬНО 60~МС. дИСКИ |MIXTEC| СОВЕРШАЮТ ОДИН ОБОРОТ ЗА
25 МС, ТАК ЧТО ВРЕМЯ ОЖИДАНИЯ РАВНО В СРЕДНЕМ 12.5 МС. вРЕМЯ ПЕРЕДАЧИ $n$
ЛИТЕР ЕСТЬ
$(n/5000)\times25\hbox{ МС}=5n\hbox{ МКС}$.
(эТО ПРИМЕРНО В $3{1\over3}$ РАЗА БЫСТРЕЕ, ЧЕМ СКОРОСТЬ ПЕРЕДАЧИ ДЛЯ ЛЕНТ
|MIXT|, ИСПОЛЬЗОВАННЫХ В ПРИМЕРАХ П.~5.4.6.)

тАКИМ ОБРАЗОМ, ОСНОВНЫЕ РАЗЛИЧИЯ МЕЖДУ ДИСКАМИ |MIXTEC| И ЛЕНТАМИ |MIXT|,
КАСАЮЩИЕСЯ СОРТИРОВКИ, СЛЕДУЮЩИЕ:
\medskip
\item{a)} нА ЛЕНТАХ ВОЗМОЖЕН ТОЛЬКО ПОСЛЕДОВАТЕЛЬНЫЙ ДОСТУП К ДАННЫМ.

\item{b)} оТДЕЛЬНАЯ ОПЕРАЦИЯ С ДИСКОМ, КАК ПРАВИЛО, СОПРЯЖЕНА СО
ЗНАЧИТЕЛЬНО БОЛЬШИМИ НАКЛАДНЫМИ РАСХОДАМИ (ВРЕМЯ ПОИСКА + ВРЕМЯ ОЖИДАНИЯ
В СРАВНЕНИИ СО СТАРТСТОПНЫМ ВРЕМЕНЕМ).
\item{c)} сКОРОСТЬ ПЕРЕДАЧИ У ДИСКА БОЛЬШЕ.
\medskip

иСПОЛЬЗУЯ ДЛЯ ЛЕНТ РАЗУМНЫЕ СХЕМЫ СЛИЯНИЯ, МЫ МОГЛИ ДО НЕКОТОРОЙ СТЕПЕНИ
СКОМПЕНСИРОВАТЬ НЕДОСТАТОК (a). тЕПЕРЬ У НАС ИНАЯ ЦЕЛЬ---НАМ НУЖНО НАЙТИ
ТАКИЕ РАЦИОНАЛЬНЫЕ АЛГОРИТМЫ СОРТИРОВКИ НА ДИСКАХ, В КОТОРЫХ
КОМПЕНСИРУЕТСЯ НЕДОСТАТОК (b).
\qsection кАК СОКРАТИТЬ ВРЕМЯ ОЖИДАНИЯ? рАССМОТРИМ .СНАЧАЛА
ЗАДАЧУ МИНИМИЗАЦИИ ЗАДЕРЖЕК, ВЫЗЫВАЕМЫХ ТЕМ, ЧТО В ТОТ МОМЕНТ, КОГДА МЫ
ХОТИМ НАЧАТЬ КОМАНДУ ВВОДА/ВЫВОДА, ДИСК НЕ ВСЕГДА НАХОДИТСЯ В ПОДХОДЯЩЕЙ
ПОЗИЦИИ. нЕЛЬЗЯ ЗАСТАВИТЬ ДИСК ВРАЩАТЬСЯ БЫСТРЕЕ, НО ВСЕ-ТАКИ МОЖНО
ПРИБЕГНУТЬ К РАЗНЫМ УЛОВКАМ, КОТОРЫЕ УМЕНЬШАТ ИЛИ ДАЖЕ ПОЛНОСТЬЮ
УСТРАНЯТ ВРЕМЯ ОЖИДАНИЯ. нЕСОМНЕННО, ПОМОЖЕТ ДОБАВЛЕНИЕ ЕЩЕ НЕСКОЛЬКИХ
ДЕРЖАТЕЛЕЙ ГОЛОВОК, НО ЭТО ВЕСЬМА ДОРОГОСТОЯЩАЯ МОДИФИКАЦИЯ ОБОРУДОВАНИЯ.
 вОТ НЕСКОЛЬКО "ПРОГРАММИСТСКИХ" ИДЕЙ.
\enumerate
\li еСЛИ МЫ ЧИТАЕМ ИЛИ ЗАПИСЫВАЕМ ЗА ОДИН РАЗ НЕСКОЛЬКО ДОРОЖЕК ОДНОГО
ЦИЛИНДРА, ТО ТЕМ САМЫМ УСТРАНЯЕМ ВРЕМЯ ОЖИДАНИЯ (И ВРЕМЯ ПОИСКА) ДЛЯ
ВСЕХ ДОРОЖЕК, КРОМЕ ПЕРВОЙ. вООБЩЕ ЗАЧАСТУЮ МОЖНО ТАКИМ ОБРАЗОМ
СИНХРОНИЗОВАТЬ ВЫЧИСЛЕНИЯ С ВРАЩЕНИЕМ ДИСКА, ЧТО ПРИ ВЫПОЛНЕНИИ
ПОСЛЕДОВАТЕЛЬНОСТИ КОМАНД ВВОДА/ВЫВОДА НЕ БУДЕТ ЗАДЕРЖЕК ИЗ-ЗА ОЖИДАНИЯ.

\li рАССМОТРИМ ЗАДАЧУ ЧТЕНИЯ ПОЛОВИНЫ ДОРОЖКИ ДАННЫХ (РИС.~90): ЕСЛИ
КОМАНДА ЧТЕНИЯ ВЫДАЕТСЯ, КОГДА ГОЛОВКА НАХОДИТСЯ В ТОЧКЕ $A$, ТО ЗАДЕРЖКА
НА ОЖИДАНИЕ ОТСУТСТВУЕТ, И ОБЩЕЕ ВРЕМЯ
ЧТЕНИЯ РАВНО ВРЕМЕНИ ПЕРЕДАЧИ, Т.Е. ${1\over2}\times25$ МС. еСЛИ
КОМАНДА НАЧИНАЕТСЯ, КОГДА ГОЛОВКА НАХОДИТСЯ В ТОЧКЕ $B$, ТО
ТРЕБУЕТСЯ ${1\over 4}$ ОБОРОТА ДЛЯ ОЖИДАНИЯ И $1\over2$ ДЛЯ ПЕРЕДАЧИ; В
ИТОГЕ ИМЕЕМ
%%431
${3\over4}\times25$ МС. нАИБОЛЕЕ ИНТЕРЕСЕН СЛУЧАЙ, КОГДА ГОЛОВКА
ПЕРВОНАЧАЛЬНО НАХОДИТСЯ В ТОЧКЕ $C$: ИМЕЯ СООТВЕТСТВУЮЩЕЕ ОБОРУДОВАНИЕ И
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ, НАМ \emph{НЕ} ПРИДЕТСЯ ТЕРЯТЬ $3\over4$ ОБОРОТА
НА ОЖИДАНИЕ. мОЖНО НЕМЕДЛЕННО НАЧАТЬ ЧТЕНИЕ ВО ВТОРУЮ ПОЛОВИНУ БУФЕРА
ВВОДА, ЗАТЕМ ПОСЛЕ ПАУЗЫ В ${1\over2}\times25$ МС .МОЖНО
ВОЗОБНОВИТЬ ЧТЕНИЕ В ПЕРВУЮ ПОЛОВИНУ БУФЕРА, ТАК ЧТО КОМАНДА . БУДЕТ
ЗАВЕРШЕНА, КОГДА МЫ СНОВА ПОПАДЕМ В ТОЧКУ $C$. пОСТУПАЯ
\picture{рИС. 90. аНАЛИЗ ВРЕМЕНИ ОЖИДАНИЯ ПРИ ЧТЕНИИ ПОЛОВИНЫ ДОРОЖКИ}
ТАКИМ ОБРАЗОМ, МОЖНО ГАРАНТИРОВАТЬ, ЧТО ОБЩЕЕ ВРЕМЯ НА
ОЖИДАНИЕ+ПЕРЕДАЧУ НИКОГДА НЕ ПРЕВЗОЙДЕТ ВРЕМЕНИ ОДНОГО ОБОРОТА НЕЗАВИСИМО ОТ
НАЧАЛЬНОГО ПОЛОЖЕНИЯ ДИСКА. сРЕДНЕЕ ВРЕМЯ ОЖИДАНИЯ УМЕНЬШАЕТСЯ ЭТОЙ
СХЕМОЙ С ПОЛОВИНЫ ОБОРОТА ДО ${1\over2}(1-x^2)$
ОБОРОТА, ЕСЛИ ЧИТАЕТСЯ ИЛИ ЗАПИСЫВАЕТСЯ ДОЛЯ $x$ ДОРОЖКИ ($0<x\le 1$).
еСЛИ ЧИТАЕТСЯ ИЛИ ЗАПИСЫВАЕТСЯ ЦЕЛАЯ ДОРОЖКА ($x=1$), ТО ЭТОТ МЕТОД
ПОЗВОЛЯЕТ ПОЛНОСТЬЮ УСТРАНИТЬ ОЖИДАНИЕ.

\section бАРАБАНЫ: СЛУЧАЙ, КОГДА ПОИСК НЕ НУЖЕН. нА НЕКОТОРЫХ
УСТРОЙСТВАХ ВНЕШНЕЙ ПАМЯТИ УСТАНОВЛЕНО ПО ОДНОЙ ГОЛОВКЕ ЧТЕНИЯ/ЗАПИСИ
ДЛЯ КАЖДОЙ ДОРОЖКИ, И ПОЭТОМУ ВРЕМЯ ПОИСКА ПОЛНОСТЬЮ УСТРАНЕНО. еСЛИ НА
ТАКОМ УСТРОЙСТВЕ ИСПОЛЬЗУЕТСЯ МЕТОД, ПРОДЕМОНСТРИРОВАННЫЙ НА РИС.~90, ТО
КАК ВРЕМЯ ПОИСКА, ТАК И ВРЕМЯ ОЖИДАНИЯ СВЕДЕНЫ К НУЛЮ, ПРИ УСЛОВИИ ЧТО МЫ
ВСЕГДА ЧИТАЕМ ИЛИ ЗАПИСЫВАЕМ ВСЮ ДОРОЖКУ ЦЕЛИКОМ. в ЭТОЙ ИДЕАЛЬНОЙ
СИТУАЦИИ ВРЕМЯ ПЕРЕДАЧИ ЯВЛЯЕТСЯ ЕДИНСТВЕННЫМ ОГРАНИЧИТЕЛЬНЫМ ФАКТОРОМ.

рАССМОТРИМ ВНОВЬ ПРИМЕР ИЗ П.~5.4.6, В КОТОРОМ СОРТИРУЮТСЯ 100000 ЗАПИСЕЙ
ПО 100 ЛИТЕР КАЖДАЯ С ВНУТРЕННЕЙ ПАМЯТЬЮ В 100000 ЛИТЕР. вЕСЬ ОБЎЕМ
СОРТИРУЕМЫХ ДАННЫХ ЗАНИМАЕТ ПОЛОВИНУ ДИСКА |MIXTEC|. оБЫЧНО НЕВОЗМОЖНО
ОДНОВРЕМЕННО ЧИТАТЬ И ПИСАТЬ НА ОДНОМ ДИСКОВОМ УСТРОЙСТВЕ; ПОЭТОМУ
ПРЕДПОЛОЖИМ, ЧТО ИМЕЮТСЯ ДВА ДИСКА, ТАК ЧТО ЧТЕНИЕ И ЗАПИСЬ МОЖНО СОВМЕСТИТЬ.
%%432
 пОКА БУДЕМ СЧИТАТЬ, ЧТО "ДИСКИ"---ЭТО ФАКТИЧЕСКИ \emph{БАРАБАНЫ},
СОДЕРЖАЩИЕ 4000 ДОРОЖЕК ПО 5000 ЛИТЕР КАЖДАЯ, И НИКАКОГО ВРЕМЕНИ
ПОИСКА НЕ ТРЕБУЕТСЯ.

кАКОЙ АЛГОРИТМ СОРТИРОВКИ СЛЕДУЕТ ИСПОЛЬЗОВАТЬ? еСТЕСТВЕННО ВЫБРАТЬ
МЕТОД СЛИЯНИЯ; ДРУГИЕ МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ НЕ СТОЛЬ ХОРОШИ В
ПРИМЕНЕНИИ К ДИСКАМ, ЗА ИСКЛЮЧЕНИЕМ. ВОЗМОЖНО, ПОРАЗРЯДНЫХ МЕТОДОВ, НО
РАССУЖДЕНИЯ В П.~5.4.7 ПОКАЗЫВАЮТ, ЧТО ПОРАЗРЯДНАЯ СОРТИРОВКА ОБЫЧНО
ХУЖЕ СЛИЯНИЯ, ЕСЛИ РЕЧЬ ИДЕТ НЕ О КАКИХ-НИБУДЬ ЧАСТНЫХ ПРИЛОЖЕНИЯХ.
(нЕТРУДНО ВИДЕТЬ, ЧТО. ТЕОРЕМА ДВОЙСТВЕННОСТИ, СФОРМУЛИРОВАННАЯ В ЭТОМ
ПУНКТЕ, ПРИМЕНИМА К ДИСКАМ ТОЧНО ТАК ЖЕ, КАК И К ЛЕНТАМ.)

чТОБЫ НАЧАТЬ СОРТИРОВКУ СЛИЯНИЕМ, МОЖНО ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ С
ДВУМЯ БУФЕРАМИ ВВОДА ПО 5000 ЛИТЕР И ДВУМЯ БУФЕРАМИ ВЫВОДА ПО 5000 ЛИТЕР,
ФАКТИЧЕСКИ МОЖНО СВЕСТИ ИХ К \emph{ТРЕМ} БУФЕРАМ ПО 5000 ЛИТЕР, ЕСЛИ
ЗАМЕЩАТЬ ЗАПИСИ В ТЕКУЩЕМ БУФЕРЕ ВВОДА НА ЗАПИСИ, ВЫВОДИМЫЕ ИЗ ДЕРЕВА
ВЫБОРА. оСТАЕТСЯ ЕЩЕ 85000 ЛИТЕР (850 ЗАПИСЕЙ) ДЛЯ ДЕРЕВА ВЫБОРА, ТАК ЧТО
ОДИН ПРОХОД ПО ДАННЫМ НАШЕГО ПРИМЕРА ПОЗВОЛИТ СФОРМИРОВАТЬ ОКОЛО 60
НАЧАЛЬНЫХ ОТРЕЗКОВ (СМ. ФОРМУЛУ (5.4.6--3)). эТОТ ПРОХОД ЗАНИМАЕТ ЛИШЬ
ОКОЛО 50~С, ЕСЛИ ПРЕДПОЛОЖИТЬ, ЧТО СКОРОСТЬ ВНУТРЕННЕЙ ОБРАБОТКИ
ДОСТАТОЧНО ВЫСОКА, ЧТОБЫ УСПЕТЬ ЗА ВВОДОМ/ВЫВОДОМ (КАЖДЫЕ 500~МКС В БУФЕР
ВЫВОДА ДОЛЖНА ПЕРЕДАВАТЬСЯ ЗАПИСЬ). еСЛИ ЖЕ СОРТИРУЕМЫЕ ИСХОДНЫЕ
ДАННЫЕ НАХОДЯТСЯ НА ЛЕНТЕ |MIXT|, А НЕ НА БАРАБАНЕ, ТО ЭТОТ ПРОХОД
БУДЕТ ВЫПОЛНЯТЬСЯ МЕДЛЕННЕЕ, И .ВРЕМЯ БУДЕТ ЗАВИСЕТЬ ОТ СКОРОСТИ ЛЕНТЫ.

нЕТРУДНО ВИДЕТЬ, ЧТО В СЛУЧАЕ ДВУХ БАРАБАНОВ И ПРИ ЧТЕНИИ/ЗАПИСИ ПОЛНЫМИ
ДОРОЖКАМИ ОБЩЕЕ ВРЕМЯ ПЕРЕДАЧИ ДЛЯ $P$-ПУТЕВОГО СЛИЯНИЯ УМЕНЬШАЕТСЯ С
УВЕЛИЧЕНИЕМ $P$. к СОЖАЛЕНИЮ, МЫ НЕ МОЖЕМ ВЫПОЛНИТЬ ОДНО ТОЛЬКО 60-ПУТЕВОЕ
СЛИЯНИЕ ВСЕХ НАЧАЛЬНЫХ ОТРЕЗКОВ, ТАК КАК В ПАМЯТИ НЕТ МЕСТА ДЛЯ 60
БУФЕРОВ. (еСЛИ РАЗМЕР БУФЕРОВ БУДЕТ МЕНЬШЕ 5000 ЛИТЕР, ТО
ПОЯВИТСЯ .НЕЖЕЛАТЕЛЬНОЕ ВРЕМЯ ОЖИДАНИЯ.) еСЛИ МЫ ВЫПОЛНЯЕМ
$P$-ПУТЕВОЕ СЛИЯНИЕ, ПЕРЕПИСЫВАЯ ВСЕ ДАННЫЕ С ОДНОГО БАРАБАНА НА
ДРУГОЙ ТАКИМ ОБРАЗОМ, ЧТО ЧТЕНИЕ И ЗАПИСЬ СОВМЕЩЕНЫ, ТО ЧИСЛО ПРОХОДОВ
СЛИЯНИЯ РАВНО $\lceil \log_P 60\rceil$; СЛЕДОВАТЕЛЬНО, МЫ МОЖЕМ ЗАКОНЧИТЬ
РАБОТУ ЗА ДВА ПРОХОДА, ЕСЛИ $8\le P \le 59$. с УМЕНЬШЕНИЕМ $P$
УМЕНЬШАЕТСЯ ОБЎЕМ ВНУТРЕННИХ ВЫЧИСЛЕНИЙ, ПОЭТОМУ ВЫБЕРЕМ $P=8$; ЕСЛИ БУДЕТ
ОБРАЗОВАНО 65 НАЧАЛЬНЫХ ОТРЕЗКОВ, МЫ ВЫБЕРЕМ $P=9$. еСЛИ БУДЕТ ОБРАЗОВАНО
82 ИЛИ БОЛЬШЕ НАЧАЛЬНЫХ ОТРЕЗКОВ, МЫ МОЖЕМ ВЗЯТЬ $P=10$, НО ТАК КАК
ИМЕЕТСЯ МЕСТО ТОЛЬКО ДЛЯ 18 БУФЕРОВ ВВОДА И ДВУХ БУФЕРОВ ВЫВОДА, ТО
ПОЯВИТСЯ ВОЗМОЖНОСТЬ ЗАДЕРЖЕК ПРИ СЛИЯНИИ (СМ. АЛГОРИТМ~5.4.6F); В ТАКОМ
СЛУЧАЕ, ВЕРОЯТНО, ЛУЧШЕ ВЫПОЛНИТЬ ДВА ЧАСТИЧНЫХ ПРОХОДА НАД НЕБОЛЬШОЙ
ДОЛЕЙ ДАННЫХ, СОКРАТИВ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ ДО 81 ИЛИ МЕНЬШЕ.
%%433
пРИ НАШИХ ПРЕДПОЛОЖЕНИЯХ КАЖДЫЙ ПРОХОД СЛИЯНИЯ ЗАЙМЕТ ОКОЛО 50~С, ТАК ЧТО
ВСЯ СОРТИРОВКА В ЭТОЙ ИДЕАЛЬНОЙ СИТУАЦИИ
БУДЕТ ЗАВЕРШЕНА ЗА $2{1\over2}$~МИН (ПЛЮС НЕСКОЛЬКО СЕКУНД НА
ИНИЦИАЛИЗАЦИЮ И ДРУГИЕ ВСПОМОГАТЕЛЬНЫЕ ДЕЙСТВИЯ). эТО В ШЕСТЬ
РАЗ БЫСТРЕЕ, ЧЕМ НАИЛУЧШАЯ ИЗ СОРТИРОВОК С ШЕСТЬЮ ЛЕНТАМИ, РАССМОТРЕННЫХ
В П.~5.4.6. пРИЧИНАМИ ЭТОГО УСКОРЕНИЯ ЯВЛЯЮТСЯ УВЕЛИЧЕННАЯ СКОРОСТЬ
ПЕРЕДАЧИ ДАННЫХ МЕЖДУ ВНЕШНЕЙ И ВНУТРЕННЕЙ ПАМЯТЬЮ (ОНА В $3{1\over2}$
РАЗА ВЫШЕ) , БОЛЕЕ ВЫСОКИЙ ПОРЯДОК СЛИЯНИЯ (МЫ НЕ МОЖЕМ ОСУЩЕСТВИТЬ
ВОСЬМИПУТЕВОЕ СЛИЯНИЕ
НА ЛЕНТАХ НЕ ИМЕЯ ДЕВЯТИ ИЛИ БОЛЬШЕГО ЧИСЛА ЛЕНТ) И ТО, ЧТО ВЫВОДНЫЕ
ДАННЫЕ ОСТАЮТСЯ НА ДИСКЕ (НЕТ НЕОБХОДИМОСТИ В ЗАКЛЮЧИТЕЛЬНОЙ ПЕРЕМОТКЕ И
Т. Д.). еСЛИ ТРЕБУЕТСЯ, ЧТОБЫ ИСХОДНЫЕ ДАННЫЕ И ОТСОРТИРОВАННЫЙ РЕЗУЛЬТАТ
БЫЛИ НА ЛЕНТАХ |MIXT|, А БАРАБАНЫ ИСПОЛЬЗУЮТСЯ ТОЛЬКО ДЛЯ СЛИЯНИЯ, ТО
ТАКАЯ СОРТИРОВКА ЗАЙМЕТ ОКОЛО 8.2 МИН.

еСЛИ ВМЕСТО ДВУХ БАРАБАНОВ ИМЕЕТСЯ ТОЛЬКО ОДИН, ТО ВРЕМЯ ВВОДА/ВЫВОДА
УВЕЛИЧИТСЯ ВДВОЕ, ПОСКОЛЬКУ ЧТЕНИЕ/ЗАПИСЬ ПРИДЕТСЯ ВЫПОЛНЯТЬ ПО
ОТДЕЛЬНОСТИ. (нА САМОМ ДЕЛЕ ОПЕРАЦИИ ВВОДА/ВЫВОДА ЗАЙМУТ В \emph{ТРИ РАЗА}
БОЛЬШЕ ВРЕМЕНИ, ПОСКОЛЬКУ
ЗАПИСЬ БУДЕТ-ИДТИ ПОВЕРХ ИСХОДНЫХ ДАННЫХ; В ТАКИХ СЛУЧАЯХ ЦЕЛЕСООБРАЗНО ЗА
КАЖДОЙ ОПЕРАЦИЕЙ ЗАПИСИ ВЫПОЛНЯТЬ ОПЕРАЦИЮ КОНТРОЛЬНОГО ЧТЕНИЯ, ЧТОБЫ НЕ
ПОТЕРЯТЬ НЕОБРАТИМО КАКИХ-НИБУДЬ ИСХОДНЫХ ДАННЫХ, ЕСЛИ ТОЛЬКО
ОБОРУДОВАНИЕ НЕ ОБЕСПЕЧИВАЕТ АВТОМАТИЧЕСКОЙ ПРОВЕРКИ ЗАПИСАННОЙ
ИНФОРМАЦИИ.) оДНАКО ЧАСТЬ ЭТОГО ДОПОЛНИТЕЛЬНОГО ВРЕМЕНИ МОЖНО ВОЗВРАТИТЬ,
ПОСКОЛЬКУ МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ ЧАСТИЧНЫЕ ПРОХОДЫ, ПРИ КОТОРЫХ ОДНИ ЗАПИСИ
ОБРАБАТЫВАЮТСЯ ЧАЩЕ ДРУГИХ. в СЛУЧАЕ ДВУХ БАРАБАНОВ ТРЕБУЕТСЯ, ЧТОБЫ ВСЕ
ДАННЫЕ ОБРАБАТЫВАЛИСЬ ЧЕТНОЕ ИЛИ>НЕЧЕТНОЕ ЧИСЛО РАЗ, НО В СЛУЧАЕ ОДНОГО
БАРАБАНА МОЖНО ИСПОЛЬЗОВАТЬ БОЛЕЕ ОБЩИЕ СХЕМЫ СЛИЯНИЯ.

мЫ ВИДЕЛИ В П.~5.4.4, ЧТО СХЕМЫ СЛИЯНИЯ МОЖНО ИЗОБРАЖАТЬ С ПОМОЩЬЮ
ДЕРЕВЬЕВ И ЧТО ВРЕМЯ ПЕРЕДАЧИ, СООТВЕТСТВУЮЩЕЕ СХЕМЕ СЛИЯНИЯ,
ПРОПОРЦИОНАЛЬНО ДЛИНЕ ВНЕШНЕГО ПУТИ ДЕРЕВА. в КАЧЕСТВЕ СХЕМ ЭФФЕКТИВНОГО
СЛИЯНИЯ НА ЛЕНТАХ МОЖНО ИСПОЛЬЗОВАТЬ ЛИШЬ ВПОЛНЕ ОПРЕДЕЛЕННЫЕ ДЕРЕВЬЯ
("$T$-lifo" ИЛИ "СИЛЬНЫЕ $T$-fifo"), ПОТОМУ ЧТО В ПРОЦЕССЕ СЛИЯНИЯ
НЕКОТОРЫЕ ОТРЕЗКИ ОКАЗЫВАЮТСЯ "СПРЯТАННЫМИ" В СЕРЕДИНЕ ЛЕНТЫ. нО \emph{ПРИ
ИСПОЛЬЗОВАНИИ ДИСКОВ ИЛИ БАРАБАНОВ ПРИГОДНЫ ЛЮБЫЕ ДЕРЕВЬЯ}, ЕСЛИ
ТОЛЬКО СТЕПЕНИ ИХ ВНУТРЕННИХ УЗЛОВ НЕ СЛИШКОМ ВЕЛИКИ (Т. Е. СОГЛАСУЮТСЯ
С НАЛИЧНЫМ ОБЎЕМОМ ВНУТРЕННЕЙ ПАМЯТИ).

сЛЕДОВАТЕЛЬНО, ВРЕМЯ ПЕРЕДАЧИ МОЖНО МИНИМИЗИРОВАТЬ, ЕСЛИ ВЫБРАТЬ ДЕРЕВО С
МИНИМАЛЬНОЙ ДЛИНОЙ ВНЕШНЕГО ПУТИ, ТАКОЕ, КАК ПОЛНОЕ $P$-АРНОЕ ДЕРЕВО, ГДЕ
$P$---САМОЕ БОЛЬШОЕ, КАКОЕ ВОЗМОЖНО. пО ФОРМУЛЕ (5.4.4--9) ДЛИНА ВНЕШНЕГО
ПУТИ ТАКОГО ДЕРЕВА
%% 434
С $S$ ВНЕШНИМИ УЗЛАМИ (ЛИСТЬЯМИ) РАВНА
$$
qS-\lfloor(P^q-S)/(P-1)\rfloor, \qquad q=\lceil\log_P S\rceil.
\eqno(1)
$$

оСОБЕННО ПРОСТО СТРОИТСЯ АЛГОРИТМ, КОТОРЫЙ ОСУЩЕСТВЛЯЕТ СЛИЯНИЕ В
СООТВЕТСТВИИ СО СХЕМОЙ ПОЛНОГО $P$-АРНОГО ДЕРЕВА. (сМ., НАПРИМЕР, РИС.~91,
НА КОТОРОМ ПОКАЗАН СЛУЧАЙ $P=3$, $S=6$.) сНАЧАЛА МЫ ДОБАВЛЯЕМ, ЕСЛИ
НЕОБХОДИМО, "ФИКТИВНЫЕ ОТРЕЗКИ", ЧТОБЫ СДЕЛАТЬ $S\equiv1 \pmod{P-1}$;
ЗАТЕМ ОБЎЕДИНЯЕМ ОТРЕЗКИ В СООТВЕТСТВИИ С ДИСЦИПЛИНОЙ "ПЕРВЫМ ВКЛЮЧАЕТСЯ ---
\picture{рИС. 92. пОЛНОЕ ТЕРНАРНОЕ ДЕРЕВО С ШЕСТЬЮ ЛИСТЬЯМИ...}
ПЕРВЫМ ИСКЛЮЧАЕТСЯ", СЛИВАЯ НА КАЖДОМ ЭТАПЕ $P$ САМЫХ "СТАРЫХ" ОТРЕЗКОВ В
НАЧАЛЕ ОЧЕРЕДИ В ОДИН ОТРЕЗОК, ПОМЕЩАЕМЫЙ В КОНЕЦ.

пОЛНЫЕ $P$-АРНЫЕ ДЕРЕВЬЯ ДАЮТ ОПТИМАЛЬНУЮ СХЕМУ, ЕСЛИ ВСЕ ОТРЕЗКИ ИМЕЮТ
РАВНУЮ ДЛИНУ, НО ЧАСТО РЕЗУЛЬТАТ МОЖЕТ БЫТЬ ЕЩЕ ЛУЧШЕ, ЕСЛИ НЕКОТОРЫЕ
ОТРЕЗКИ ДЛИННЕЕ ДРУГИХ. оПТИМАЛЬНУЮ СХЕМУ ДЛЯ ЭТОЙ ОБЩЕЙ СИТУАЦИИ МОЖНО
БЕЗ ТРУДА ПОСТРОИТЬ С ПОМОЩЬЮ МЕТОДА хАФФМЭНА (УПР. 2.3.4.5--10), КОТОРЫЙ
НА ЯЗЫКЕ СЛИЯНИЯ ФОРМУЛИРУЕТСЯ ТАК: "СНАЧАЛА ДОБАВЬТЕ
$(1-S)\bmod(P-1)$ ФИКТИВНЫХ ОТРЕЗКОВ ДЛИНЫ 0, ЗАТЕМ МНОГОКРАТНО СЛИВАЙТЕ
$P$ \emph{КРАТЧАЙШИХ} ИЗ ИМЕЮЩИХСЯ ОТРЕЗКОВ, ПОКА НЕ ОСТАНЕТСЯ
ОДИН ОТРЕЗОК". еСЛИ ВСЕ НАЧАЛЬНЫЕ ОТРЕЗКИ ИМЕЮТ ОДИНАКОВУЮ ДЛИНУ, ТО ЭТОТ
МЕТОД СВОДИТСЯ К ОПИСАННОЙ ВЫШЕ ДИСЦИПЛИНЕ.

в НАШЕМ ПРИМЕРЕ СО 100000, ЗАПИСЕЙ МЫ МОЖЕМ ВЫПОЛНЯТЬ 9-ПУТЕВОЕ СЛИЯНИЕ,
ТАК КАК В ПАМЯТИ ПОМЕСТЯТСЯ 18 БУФЕРОВ ВВОДА И ДВА БУФЕРА ВЫВОДА, И В
АЛГОРИТМЕ 5.4.6F БУДЕТ ДОСТИГНУТО ПОЛНОЕ СОВМЕЩЕНИЕ ВЫЧИСЛЕНИЙ. пОЛНОЕ
9-АРНОЕ ДЕРЕВО
С 60 ЛИСТЬЯМИ СООТВЕТСТВУЕТ СХЕМЕ СЛИЯНИЯ С $1{29\over30}$ ПРОХОДА, ЕСЛИ.
ВСЕ НАЧАЛЬНЫЕ ОТРЕЗКИ ИМЕЮТ ОДИНАКОВУЮ ДЛИНУ. оБЩЕЕ ВРЕМЯ СОРТИРОВКИ С
ОДНИМ БАРАБАНОМ И С ИСПОЛЬЗОВАНИЕМ "КОНТРОЛЬНОГО ЧТЕНИЯ" ПОСЛЕ КАЖДОЙ
ЗАПИСИ СТАНОВИТСЯ, ТАКИМ ОБРАЗОМ, РАВНЫМ 7.4 МИН. уВЕЛИЧИВАЯ $P$, МОЖНО
НЕМНОГО УМЕНЬШИТЬ ЭТО ВРЕМЯ, НО СИТУАЦИЯ ВЕСЬМА ЗАПУТАННАЯ, ПОСКОЛЬКУ НЕ
ИСКЛЮЧАЕТСЯ ЗАДЕРЖКА ЧТЕНИЯ, ТАК КАК БУФЕРЫ МОГУТ ОКАЗАТЬСЯ СЛИШКОМ
ПОЛНЫМИ ИЛИ СЛИШКОМ ПУСТЫМИ.

%%435
\section вЛИЯНИЕ ВРЕМЕНИ ПОИСКА. пРЕДЫДУЩЕЕ ОБСУЖДЕНИЕ ПОКАЗЫВАЕТ, ЧТО ДЛЯ
БАРАБАНОВ ОТНОСИТЕЛЬНО ЛЕГКО СКОНСТРУИРОВАТЬ "ОПТИМАЛЬНУЮ" СХЕМУ СЛИЯНИЯ,
 ПОСКОЛЬКУ ВРЕМЯ ПОИСКА И ВРЕМЯ ОЖИДАНИЯ МОЖНО СВЕСТИ НА НЕТ. нО ЕСЛИ
ИСПОЛЬЗУЮТСЯ ДИСКИ, ТО ПОИСК ИНФОРМАЦИИ ЗАНИМАЕТ БОЛЬШЕ ВРЕМЕНИ, ЧЕМ ЕЕ
ЧТЕНИЕ. пОЭТОМУ ВРЕМЯ ПОИСКА ОКАЗЫВАЕТ ЗНАЧИТЕЛЬНОЕ ВЛИЯНИЕ НА СТРАТЕГИЮ
СОРТИРОВКИ. уМЕНЬШЕНИЕ ПОРЯДКА СЛИЯНИЯ $P$ ДАЕТ ВОЗМОЖНОСТЬ .
ИСПОЛЬЗОВАТЬ БОЛЬШИЕ ПО РАЗМЕРУ БУФЕРЫ, ТАК ЧТО РЕЖЕ ТРЕБУЕТСЯ ПОИСК; ЗА
СЧЕТ ЭТОГО ЧАСТО КОМПЕНСИРУЕТСЯ ДОПОЛНИТЕЛЬНОЕ ВРЕМЯ ПЕРЕДАЧИ, КОТОРОЕ
РАСТЕТ С УМЕНЬШЕНИЕМ $P$.

вРЕМЯ ПОИСКА ЗАВИСИТ ОТ РАССТОЯНИЯ, ПРОХОДИМОГО ДЕРЖАТЕЛЕМ ГОЛОВОК, И
МОЖНО ПОПЫТАТЬСЯ ОРГАНИЗОВАТЬ РАБОТУ ТАКИМ ОБРАЗОМ, ЧТОБЫ ЭТО РАССТОЯНИЕ
БЫЛО МИНИМАЛЬНЫМ. бЫТЬ МОЖЕТ, РАЗУМНО СНАЧАЛА СОРТИРОВАТЬ ЗАПИСИ ВНУТРИ
ЦИЛИНДРОВ. оДНАКО ДОВОЛЬНО БОЛЬШОЕ СЛИЯНИЕ ТРЕБУЕТ БОЛЬШОГО КОЛИЧЕСТВА
ПЕРЕХОДОВ. МЕЖДУ ЦИЛИНДРАМИ (СМ., НАПРИМЕР, УПР.~2). кРОМЕ ТОГО, РЕЖИМ
МУЛЬТИПРОГРАММИРОВАНИЯ В СОВРЕМЕННЫХ ОПЕРАЦИОННЫХ СИСТЕМАХ ОЗНАЧАЕТ, ЧТО
ПОЛЬЗОВАТЕЛЬ ЛИШЬ В РЕДКИХ СЛУЧАЯХ МОЖЕТ ПО-НАСТОЯЩЕМУ КОНТРОЛИРОВАТЬ
ПОЛОЖЕНИЕ ДЕРЖАТЕЛЯ ГОЛОВОК; БЛЕСТЯЩИЕ СХЕМЫ, МИНИМИЗИРУЮЩИЕ ПОИСК,
ОБЫЧНО РАБОТАЮТ ТОЛЬКО ПО ВЫХОДНЫМ ДНЯМ! тАКИМ ОБРАЗОМ, ПРЕДПОЛОЖЕНИЕ О
ТОМ, ЧТО КАЖДАЯ КОМАНДА ДЛЯ ДИСКА ТРЕБУЕТ "СЛУЧАЙНОГО" ПОИСКА, ЧАСТО
ВПОЛНЕ ОПРАВДАНО.

нАША ЦЕЛЬ В ТОМ И СОСТОИТ, ЧТОБЫ НАЙТИ ТАКОЕ ДЕРЕВО (Т. Е. СХЕМУ СЛИЯНИЯ),
КОТОРОЕ ОБЕСПЕЧИВАЕТ НАИЛУЧШИЙ БАЛАНС МЕЖДУ ВРЕМЕНЕМ ПОИСКА И ВРЕМЕНЕМ
ПЕРЕДАЧИ; ДЛЯ ЭТОЙ ЦЕЛИ НАМ НУЖЕН НЕКОТОРЫЙ СПОСОБ, ПОЗВОЛЯЮЩИЙ ОЦЕНИТЬ
ДОСТОИНСТВА ЛЮБОГО КОНКРЕТНОГО ДЕРЕВА ПО ОТНОШЕНИЮ К КОНКРЕТНОЙ
КОНФИГУРАЦИИ ОБОРУДОВАНИЯ. рАССМОТРИМ, НАПРИМЕР, ДЕРЕВО НА РИС.~92;
МЫ ХОТИМ ОЦЕНИТЬ, СКОЛЬКО ВРЕМЕНИ ЗАЙМЕТ ВЫПОЛНЕНИЕ'СООТВЕТСТВУЮЩЕГО
СЛИЯНИЯ, ЧТОБЫ МОЖНО БЫЛО СРАВНИТЬ ЭТО ДЕРЕВО С ДРУГИМИ.

в ПОСЛЕДУЮЩИХ РАССУЖДЕНИЯХ МЫ СДЕЛАЕМ НЕКОТОРЫЕ ПРОСТЫЕ ПРЕДПОЛОЖЕНИЯ
ОТНОСИТЕЛЬНО СЛИЯНИЯ НА ДИСКАХ, ЧТОБЫ ПРОИЛЛЮСТРИРОВАТЬ НЕКОТОРЫЕ ОБЩИЕ
ИДЕИ. пРЕДПОЛОЖИМ, ЧТО (1) НА ЧТЕНИЕ ИЛИ ЗАПИСЬ $n$ ЛИТЕР ТРЕБУЕТСЯ
$72.5+0.005n$~МС; (2) ПОД РАБОЧЕЕ ПРОСТРАНСТВО ОТВОДИТСЯ 100000 ЛИТЕР
ВНУТРЕННЕЙ ПАМЯТИ; (3) ДЛЯ ПЕРЕСЫЛКИ ОДНОЙ ЛИТЕРЫ ИЗ БУФЕРА ВВОДА В
БУФЕР ВЫВОДА ЗАТРАЧИВАЕТСЯ В СРЕДНЕМ $0.004$~МС НА ВЫЧИСЛЕНИЕ; (4)
\emph{НЕТ СОВМЕЩЕНИЯ} ЧТЕНИЯ, ЗАПИСИ И ВЫЧИСЛЕНИЙ; (5) РАЗМЕР БУФЕРА,
 ИСПОЛЬЗУЕМОГО ДЛЯ ВЫВОДА, НЕ ОБЯЗАТЕЛЬНО ДОЛЖЕН БЫТЬ РАВЕН РАЗМЕРУ БУФЕРА,
 ИСПОЛЬЗУЕМОГО ДЛЯ ЧТЕНИЯ ДАННЫХ НА СЛЕДУЮЩЕМ ПРОХОДЕ. аНАЛИЗ ЗАДАЧИ
СОРТИРОВКИ ПРИ ЭТИХ ПРОСТЫХ ПРЕДПОЛОЖЕНИЯХ БУДЕТ ПОЛЕЗЕН ДЛЯ ПОНИМАНИЯ
БОЛЕЕ СЛОЖНЫХ СИТУАЦИЙ.

еСЛИ ВЫПОЛНЯЕТСЯ $P$-ПУТЕВОЕ СЛИЯНИЕ, ТО МЫ МОЖЕМ РАЗДЕЛИТЬ
%% 436
ВНУТРЕННЮЮ РАБОЧУЮ ПАМЯТЬ НА $P+1$ БУФЕРНЫХ ОБЛАСТЕЙ: $P$---ДЛЯ ВВОДА И
1---ДЛЯ ВЫВОДА; В КАЖДОМ БУФЕРЕ ПО $B=100000/(P+1)$ ЛИТЕР. пРЕДПОЛОЖИМ, ЧТО
ПРЕДНАЗНАЧЕННЫЕ ДЛЯ СЛИЯНИЯ ФАЙЛЫ СОДЕРЖАЛИ В СУММЕ $L$ ЛИТЕР; ТОГДА МЫ
ВЫПОЛНИМ ПРИБЛИЗИТЕЛЬНО $L/B$ ОПЕРАЦИЙ ВЫВОДА И ПРИМЕРНО СТОЛЬКО ЖЕ
ОПЕРАЦИЙ ВВОДА;
СЛЕДОВАТЕЛЬНО, ОБЩЕЕ ВРЕМЯ СЛИЯНИЯ ПРИ ТАКИХ ПРЕДПОЛОЖЕНИЯХ БУДЕТ РАВНО
(В МИЛЛИСЕКУНДАХ) ПРИБЛИЗИТЕЛЬНО
$$
2\left(72.5{L\over B}+0.005L\right)+0.004L=(0.00145P+0.011545)L.
\eqno(2)
$$

иНЫМИ СЛОВАМИ, $P$-ПУТЕВОЕ СЛИЯНИЕ $L$ ЛИТЕР ЗАНИМАЕТ ПРИМЕРНО
$(\alpha P+\beta)L$ ЕДИНИЦ ВРЕМЕНИ, ГДЕ $\alpha$ И~$\beta$---НЕКОТОРЫЕ
КОНСТАНТЫ,
ЗАВИСЯЩИЕ ОТ ВРЕМЕНИ ПОИСКА, ВРЕМЕНИ ОЖИДАНИЯ, ВРЕМЕНИ ВЫЧИСЛЕНИЙ И
РАЗМЕРА ПАМЯТИ. эТА ФОРМУЛА ПРИВОДИТ К ИНТЕРЕСНОМУ СПОСОБУ ПОСТРОЕНИЯ
ХОРОШИХ СХЕМ СЛИЯНИЯ ДЛЯ
\picture{рИС. 92. дЕРЕВО С ДЛИНОЙ ВНЕШНЕГО ПУТИ 16 ...}
ДИСКОВ. рАССМОТРИМ, НАПРИМЕР, РИС.~92 И БУДЕМ СЧИТАТЬ, ЧТО ВСЕ НАЧАЛЬНЫЕ
.ОТРЕЗКИ (ИЗОБРАЖЕННЫЕ КВАДРАТНЫМИ "ЛИСТЬЯМИ") ИМЕЮТ ДЛИНУ $L_0$.. тОГДА
КАЖДОЕ СЛИЯНИЕ В УЗЛАХ 9 И~10 ЗАНИМАЕТ $(2\alpha+\beta)(2L_0)$ ЕДИНИЦ
ВРЕМЕНИ, СЛИЯНИЕ В УЗЛЕ 11 ЗАНИМАЕТ $(3\alpha+\beta)(4L_0)$ ЕДИНИЦ И
ОКОНЧАТЕЛЬНОЕ СЛИЯНИЕ В УЗЛЕ 12 ЗАНИМАЕТ $(4\alpha+\beta)(8L_0)$ ЕДИНИЦ.
оБЩЕЕ ВРЕМЯ СЛИЯНИЯ, СЛЕДОВАТЕЛЬНО, СОСТАВЛЯЕТ $(52\alpha + 16\beta)L_0$
ЕДИНИЦ. кОЭФФИЦИЕНТ "16" НАМ ХОРОШО ИЗВЕСТЕН: ЭТО ПРОСТО ДЛИНА ВНЕШНЕГО
ПУТИ ДЕРЕВА. кОЭФФИЦИЕНТ "52" ПРИ $\alpha$ СООТВЕТСТВУЕТ НОВОМУ ПОНЯТИЮ,
КОТОРОЕ МЫ МОЖЕМ НАЗВАТЬ \dfn{ДЛИНОЙ СТЕПЕННОГО ПУТИ ДЕРЕВА}; ОНА РАВНА
СУММЕ, ВЗЯТОЙ ПО ВСЕМ ЛИСТЬЯМ, СТЕПЕНЕЙ ВНУТРЕННИХ УЗЛОВ, ЛЕЖАЩИХ НА
ПУТИ ОТ ЛИСТА К КОРНЮ. нАПРИМЕР, НА РИС.~92 ДЛИНА СТЕПЕННОГО ПУТИ РАВНА
$(2+4)+(2+4)+(3+4)+(2+3+4)+(2+3+4)+(3+4)+(4)+(4)=52$.

еСЛИ $\cJ$---ЛЮБОЕ ДЕРЕВО, ТО ПУСТЬ $D(\cJ)$, $E(\cJ)$
ОБОЗНАЧАЮТ СООТВЕТСТВЕННО ДЛИНУ СТЕПЕННОГО ПУТИ И ДЛИНУ ВНЕШНЕГО
ПУТИ ЭТОГО ДЕРЕВА. аНАЛИЗ СВОДИТСЯ К СЛЕДУЮЩЕЙ ТЕОРЕМЕ:

%% 437
\proclaim тЕОРЕМА H. еСЛИ ВРЕМЯ, ТРЕБУЕМОЕ ДЛЯ ВЫПОЛНЕНИЯ
$P$-ПУТЕВОГО СЛИЯНИЯ $L$ ЛИТЕР, ИМЕЕТ ВИД $(\alpha P+\beta)L$ И ЕСЛИ
ТРЕБУЕТСЯ СЛИТЬ $S$ ОТРЕЗКОВ РАВНОЙ ДЛИНЫ, ТО НАИЛУЧШАЯ СХЕМА СЛИЯНИЯ
СООТВЕТСТВУЕТ ДЕРЕВУ $\cJ$, ДЛЯ КОТОРОГО $\alpha D (\cJ)+\beta E(\cJ)$
МИНИМАЛЬНО СРЕДИ ВСЕХ ДЕРЕВЬЕВ С $S$ ЛИСТЬЯМИ.

\noindent (эТА ТЕОРЕМА НЕЯВНО СОДЕРЖАЛАСЬ В НЕОПУБЛИКОВАННОЙ СТАТЬЕ,
 КОТОРУЮ дЖОРДЖ а. хАББЭРД ПРЕДСТАВИЛ НА НАЦИОНАЛЬНУЮ КОНФЕРЕНЦИЮ ACM В
1963 Г.)

пУСТЬ $\alpha$ И $\beta$---ФИКСИРОВАННЫЕ КОНСТАНТЫ; БУДЕМ ГОВОРИТЬ, ЧТО
ДЕРЕВО \dfn{ОПТИМАЛЬНО}, ЕСЛИ ОНО ИМЕЕТ МИНИМАЛЬНОЕ ЗНАЧЕНИЕ $\alpha
D(\cJ)+\beta E (\cJ)$ СРЕДИ ВСЕХ ДЕРЕВЬЕВ $\cJ$ С ТЕМ ЖЕ ЧИСЛОМ
ЛИСТЬЕВ. нЕТРУДНО ВИДЕТЬ, ЧТО \emph{ВСЕ ПОДДЕРЕВЬЯ ОПТИМАЛЬНОГО ДЕРЕВА
ТАКЖЕ ОПТИМАЛЬНЫ}. пОЭТОМУ МЫ МОЖЕМ СТРОИТЬ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ С $n$
ЛИСТЬЯМИ, ОБЎЕДИНЯЯ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ, У КОТОРЫХ МЕНЬШЕ ЧЕМ $n$ ЛИСТЬЕВ.

\proclaim тЕОРЕМА K. пУСТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ЧИСЕЛ $A_m(n)$ ОПРЕДЕЛЕНА
ПРИ $1\le m\le n$ ПРАВИЛАМИ
$$
\eqalignno{
A_1(1)&=0; & (3) \cr
A_m(n)&=\min_{1\le k\le n/m} (A_1(k)+A_{m-1}(n-k)
\rem{ПРИ $2\le m\le n$;} & (4) \cr
A_1(n)&=\min_{2\le m\le n} ((\alpha mn+\beta n+A_m(n))
\rem{ПРИ $n\ge 2$.} & (5)\cr
}
$$
тОГДА  $A_1(n)$ ЕСТЬ МИНИМАЛЬНОЕ ЗНАЧЕНИЕ
$\alpha D (\cJ) +\beta E(\cJ)$ СРЕДИ ВСЕХ ДЕРЕВЬЕВ $\cJ$ С $n$ ЛИСТЬЯМИ.

\proof иЗ СООТНОШЕНИЯ (4) СЛЕДУЕТ, ЧТО $A_m(n)$ ЕСТЬ МИНИМАЛЬНОЕ ЗНАЧЕНИЕ
$A_1(n_1)+\cdots+A_1(n_m)$ ПО ВСЕМ ПОЛОЖИТЕЛЬНЫМ ЧИСЛАМ
$n_1$, \dots, $n_m$, ТАКИМ, ЧТО
$n_1+\cdots+n_m=n$. тРЕБУЕМЫЙ РЕЗУЛЬТАТ ПОЛУЧАЕТСЯ ТЕПЕРЬ ИНДУКЦИЕЙ
ПО~$n$.
\proofend

рЕКУРРЕНТНЫЕ СООТНОШЕНИЯ (3), (4), (5) МОЖНО ИСПОЛЬЗОВАТЬ ТАКЖЕ ДЛЯ
ПОСТРОЕНИЯ САМИХ ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ. пУСТЬ $k_m(n)$---ЗНАЧЕНИЕ, ДЛЯ
КОТОРОГО ДОСТИГАЕТСЯ МИНИМУМ В ОПРЕДЕЛЕНИИ $A_m(П)$. тОГДА МОЖНО
ПОСТРОИТЬ ОПТИМАЛЬНОЕ ДЕРЕВО С $n$ ЛИСТЬЯМИ, ОБЎЕДИНЯЯ $m=k_1(n)$
ПОДДЕРЕВЬЕВ В КОРНЕ; ПОДДЕРЕВЬЯ ЯВЛЯЮТСЯ ОПТИМАЛЬНЫМИ ДЕРЕВЬЯМИ С $k_m(n)$,
 $k_{m-1}(n-k_m(n))$, $k_{m-2}(n-k_m(n)-k_{m-1}(n-k_m(n)))$, \dots
ЛИСТЬЯМИ СООТВЕТСТВЕННО.

эТА КОНСТРУКЦИЯ ПРИ $\alpha=\beta=1$ ПРОИЛЛЮСТРИРОВАНА В КАЧЕСТВЕ ПРИМЕРА
В ТАБЛ.~1. кОМПАКТНЫЕ ОПИСАНИЯ СООТВЕТСТВУЮЩИХ ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ
ИМЕЮТСЯ В ПРАВОЙ ЧАСТИ ТАБЛИЦЫ; ЭЛЕМЕНТ "4:9:9" ДЛЯ $n=22$, НАПРИМЕР,
ОЗНАЧАЕТ, ЧТО ОПТИМАЛЬНОЕ ДЕРЕВО $\cJ_22$ С 22 ЛИСТЬЯМИ МОЖНО ПОЛУЧИТЬ В
РЕЗУЛЬТАТЕ ОБЎЕДИНЕНИЯ $\cJ_4$, $\cJ_9$ И~$\cJ_9$ (РИС.~93). оПТИМАЛЬНЫЕ
ДЕРЕВЬЯ НЕ ЕДИНСТВЕННЫ;
НАПРИМЕР, ЭЛЕМЕНТ 5:8:9 БЫЛ БЫ СТОЛЬ ЖЕ ХОРОШИМ, КАК И 4:9:9.
%% 438
\bye