\input style
\chapnotrue\chapno=5\subchno=4\subsubchno=5

\subsubchap{яРАКТИЧЕСКИЕ АСПЕКТЫ СЛИЯНИЯ НА ЛЕНТАХ} % 5.4.6
чДЕСЬ ВСПЛЫВАЮТ РАЗНЫЕ МЕЛОЧИ. яОСЛЕ ТОГО КАК МЫ ОБСУДИЛИ РАЗЛИЧНЫЕ
СЕМЕЙСТВА СХЕМ СЛИЯНИЯ, САМОЕ ВРЕМЯ ПОСМОТРЕТЬ, КАК ОНИ ОТОБРАЖАЮТСЯ НА
РЕАЛЬНЫЕ КОНФИГУРАЦИИ ¤ть И МАГНИТНЫХ ЛЕНТ, И СРАВНИТЬ РАЗУМНЫМ ОБРАЗОМ
ЭТИ СХЕМЫ. шЗУЧЕНИЕ ВНУТРЕННЕЙ СОРТИРОВКИ ПОКАЗАЛО, ЧТО НЕВОЗМОЖНО
АДЕКВАТНО ОЦЕНИТЬ ЭФФЕКТИВНОСТЬ МЕТОДА СОРТИРОВКИ, ПРОСТО ПОДСЧИТЫВАЯ
ЧИСЛО ВЫПОЛНЯЕМЫХ ИМ СРАВНЕНИЙ; ПОДОБНО ЭТОМУ, МЫ НЕ МОЖЕМ ПРАВИЛЬНО
ОЦЕНИТЬ МЕТОД ВНЕШНЕЙ СОРТИРОВКИ, ПРОСТО ВЫЯСНЯЯ ЧИСЛО ВЫПОЛНЯЕМЫХ ИМ
ПРОХОДОВ ПО ДАННЫМ.

т ЭТОМ ПУНКТЕ МЫ РАССМОТРИМ ХАРАКТЕРИСТИКИ ТИПИЧНЫХ ЛЕНТОЧНЫХ УСТРОЙСТВ И
ИХ ВЛИЯНИЕ НА НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ И СЛИЯНИЕ. т ЧАСТНОСТИ, ИЗУЧИМ
НЕСКОЛЬКО СХЕМ РАСПРЕДЕЛЕНИЯ БУФЕРОВ И ИХ ВОЗДЕЙСТВИЕ НА ВРЕМЯ СЧЕТА.
сУДЕТ ТАКЖЕ ВКРАТЦЕ РАССМОТРЕНА КОНСТРУКЦИЯ ПРОГРАММ-ГЕНЕРАТОРОВ СОРТИРОВКИ.

\section ъАК РАБОТАЕТ ЛЕНТА. т ХАРАКТЕРИСТИКАХ ЛЕНТОЧНЫХ УСТРОЙСТВ,
 ПРОИЗВОДИМЫХ РАЗНЫМИ ИЗГОТОВИТЕЛЯМИ, ИМЕЮТСЯ ЗНАЧИТЕЛЬНЫЕ РАЗЛИЧИЯ.
юПРЕДЕЛИМ ДЛЯ УДОБСТВА ГИПОТЕТИЧЕСКОЕ ЛЕНТОЧНОЕ УСТРОЙСТВО~\MIXT,
ДОСТАТОЧНО ТИПИЧНОЕ ДЛЯ ОБОРУДОВАНИЯ ТОГО ВРЕМЕНИ, КОГДА БЫЛА НАПИСАНА ЭТА
КНИГА. шЗУЧИВ, КАК ПОСТРОИТЬ АЛГОРИТМ СОРТИРОВКИ ДЛЯ ЛЕНТ~\MIXT, ВЫ ЛУЧШЕ
ПОЙМЕТЕ, КАК ОБРАЩАТЬСЯ С ДРУГИМИ КОНКРЕТНЫМИ ЛЕНТОЧНЫМИ УСТРОЙСТВАМИ.

\MIXT{} ЧИТАЕТ ИЛИ ЗАПИСЫВАЕТ 800~ЛИТЕР НА ДЮЙМ ЛЕНТЫ СО СКОРОСТЬЮ 75~ДЮЙМОВ
В СЕКУНДУ. ¤ТО ОЗНАЧАЕТ, ЧТО ОДНА ЛИТЕРА
ЧИТАЕТСЯ ИЛИ ЗАПИСЫВАЕТСЯ В ТЕЧЕНИЕ~1/60~МС, Т.~Е.~$16{2\over3}$~МКС,         
ЕСЛИ ЛЕНТА НАХОДИТСЯ В АКТИВНОМ СОСТОЯНИИ. [ЁЕАЛЬНЫЕ ЛЕНТОПРОТЯЖНЫЕ
УСТРОЙСТВА, ШИРОКО РАСПРОСТРАНЕННЫЕ В НАСТОЯЩЕЕ ВРЕМЯ, ИМЕЮТ ПЛОТНОСТЬ В
ДИАПАЗОНЕ ОТ~200 ДО~1600 ЛИТЕР НА
ДЮЙМ И СКОРОСТЬ В ДИАПАЗОНЕ ОТ~$37{1\over2}$ ДО~$150$~ДЮЙМОВ В СЕКУНДУ,
ТАК ЧТО ИХ ЭФФЕКТИВНАЯ СКОРОСТЬ В СРАВНЕНИИ С \MIXT{} ИЗМЕНЯЕТСЯ В
ДИАПАЗОНЕ ОТ~$1\over8$ ДО~4. ё ПРАКТИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ БОЛЬШОЙ ОБоЕМ
СОРТИРОВКИ ВЫПОЛНЯЕТСЯ В КОММЕРЧЕСКИХ СИСТЕМАХ НА ОТНОСИТЕЛЬНО НЕБОЛЬШОМ
И НЕДОРОГОМ ОБОРУДОВАНИИ, КОТОРОЕ МЕДЛЕННЕЕ, ЧЕМ РАССМАТРИВАЕМОЕ ЗДЕСЬ.
ё ДРУГОЙ СТОРОНЫ, ЛЕНТОПРОТЯЖНЫЕ УСТРОЙСТВА ВСКОРЕ МОГУТ РЕЗКО
ИЗМЕНИТЬСЯ, ЧТО СДЕЛАЕТ НАСТОЯЩИЕ ПРЕДПОЛОЖЕНИЯ УСТАРЕВШИМИ. эАША
ОСНОВНАЯ ЦЕЛЬ СОСТОИТ НЕ В ПОЛУЧЕНИИ КОНКРЕТНЫХ ОТВЕТОВ, А В ТОМ,
ЧТОБЫ НАУЧИТЬСЯ РАЗУМНО СОЧЕТАТЬ ТЕОРИЮ С ПРАКТИКОЙ.]

юДНО ИЗ ВАЖНЫХ СООБРАЖЕНИЙ, КОТОРОЕ НАДО ИМЕТЬ В ВИДУ, СОСТОИТ В ТОМ, ЧТО
ЛЕНТЫ ИМЕЮТ КОНЕЧНУЮ ДЛИНУ. ъАЖДАЯ БОБИНА
%%379
СОДЕРЖИТ 2400~ФУТОВ ЛЕНТЫ ИЛИ МЕНЬШЕ; СЛЕДОВАТЕЛЬНО, НА ОДНОЙ БОБИНЕ
ЛЕНТЫ \MIXT{} ЕСТЬ МЕСТО ДЛЯ САМОЕ БОЛЬШЕЕ ПРИМЕРНО $23\,000\,000$~ЛИТЕР, И,
ЧТОБЫ ПРОЧЕСТЬ ИХ ВСЕ, ТРЕБУЕТСЯ ОКОЛО $23\,000\,000/3\,600\,000\approx 6.4$~МИН.
хСЛИ ТРЕБУЕТСЯ СОРТИРОВАТЬ БОЛЬШИЙ ФАЙЛ, ТО ОБЫЧНО ЛУЧШЕ ВСЕГО
СОРТИРОВАТЬ ЗА ОДИН РАЗ ОДНУ ПОЛНУЮ БОБИНУ И ЗАТЕМ СЛИТЬ ОТДЕЛЬНЫЕ
ОТСОРТИРОВАННЫЕ БОБИНЫ С ЦЕЛЬЮ ИЗБЕЖАТЬ ИЗБЫТОЧНОЙ РАБОТЫ ПО
УСТАНОВКЕ ЛЕНТ. ¤ТО ОЗНАЧАЕТ, ЧТО ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ~$S$,
РЕАЛЬНО ПРИСУТСТВУЮЩИХ В СХЕМАХ СЛИЯНИЯ, КОТОРЫЕ МЫ ИЗУЧАЛИ, НИКОГДА НЕ
БУДЕТ ОЧЕНЬ БОЛЬШИМ. ьЫ НИКОГДА НЕ СТОЛКНЕМСЯ СО
\picture{ЁИС.~79.  ьАГНИТНАЯ ЛЕНТА С БЛОКАМИ ПЕРЕМЕННОЙ ДЛИНЫ.}
СЛУЧАЕМ~$S>5000$ ДАЖЕ ПРИ ОЧЕНЬ МАЛЕНЬКОЙ ВНУТРЕННЕЙ ПАМЯТИ, ПРОИЗВОДЯЩЕЙ
НАЧАЛЬНЫЕ ОТРЕЗКИ ДЛИНОЙ ТОЛЬКО В 5000~ЛИТЕР. ёЛЕДОВАТЕЛЬНО, ФОРМУЛЫ,
ДАЮЩИЕ АСИМПТОТИЧЕСКУЮ ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ ПРИ~$S\to\infty$, ИМЕЮТ
ГЛАВНЫМ ОБРАЗОМ АКАДЕМИЧЕСКИЙ ИНТЕРЕС.

фАННЫЕ ХРАНЯТСЯ НА ЛЕНТЕ В ВИДЕ \emph{БЛОКОВ} (РИС.~79), И КАЖДАЯ
ИНСТРУКЦИЯ ЧТЕНИЯ/ЗАПИСИ ПЕРЕДАЕТ ОДИН БЛОК. сЛОКИ ЧАСТО НАЗЫВАЮТСЯ
"ЗАПИСЯМИ", НО МЫ БУДЕМ ИЗБЕГАТЬ ЭТОГО ТЕРМИНА, ЧТОБЫ НЕ ПУТАТЬ ЕГО С
"ЗАПИСЯМИ" ФАЙЛА, КОТОРЫЕ УЧАСТВУЮТ В СОРТИРОВКЕ. фЛЯ МНОГИХ РАННИХ
ПРОГРАММ СОРТИРОВКИ, НАПИСАННЫХ В 50-Х ГОДАХ, ЭТО РАЗЛИЧИЕ БЫЛО
НЕОБЯЗАТЕЛЬНЫМ, ТАК КАК В ОДНОМ БЛОКЕ ХРАНИЛАСЬ ОДНА ЗАПИСЬ; НО МЫ УВИДИМ,
ЧТО ОБоЕДИНЕНИЕ НЕСКОЛЬКИХ ЗАПИСЕЙ В ОДНОМ БЛОКЕ НА ЛЕНТЕ ОБЫЧНО ДАЕТ
ОПРЕДЕЛЕННЫЕ ПРЕИМУЩЕСТВА.

ёОСЕДНИЕ БЛОКИ РАЗДЕЛЯЮТСЯ \emph{МЕЖБЛОЧНЫМИ ПРОМЕЖУТКАМИ} ДЛИНОЙ ПО
480~ЛИТЕР, ЧТО ПОЗВОЛЯЕТ ЛЕНТЕ ОСТАНОВИТЬСЯ ИЛИ РАЗОГНАТЬСЯ МЕЖДУ
ОТДЕЛЬНЫМИ КОМАНДАМИ ЧТЕНИЯ ИЛИ ЗАПИСИ. ьЕЖБЛОЧНЫЕ ПРОМЕЖУТКИ ПРИВОДЯТ К
УМЕНЬШЕНИЮ ЧИСЛА ЛИТЕР НА ОДНОЙ БОБИНЕ, ЛЕНТЫ, ЗАВИСЯЩЕМУ ОТ ЧИСЛА ЛИТЕР В
ОДНОМ БЛОКЕ (РИС.~80); В ТОЙ ЖЕ СТЕПЕНИ УМЕНЬШАЕТСЯ КОЛИЧЕСТВО ЛИТЕР,
ПЕРЕДАВАЕМЫХ ЗА СЕКУНДУ, ТАК КАК ЛЕНТА ДВИЖЕТСЯ С ПОСТОЯННОЙ СКОРОСТЬЮ.

ьНОГИЕ "УСТАРЕВШИЕ" МОДЕЛИ ¤ть ИМЕЮТ ФИКСИРОВАННЫЕ И ВЕСЬМА МАЛЫЕ РАЗМЕРЫ
БЛОКА. эАПРИМЕР, \MIX, КАК ОНА ОПИСАНА В ГЛ.~1, ВСЕГДА ЧИТАЕТ И ПИШЕТ
БЛОКИ ПО 100~СЛОВ, ТАКИМ ОБРАЗОМ, ЭТО СОСТАВЛЯЕТ ПРИМЕРНО 500~ЛИТЕР НА
БЛОК И 480~ЛИТЕР НА
%%380
ПРОМЕЖУТОК, Т.~Е.\ ПОЧТИ ПОЛОВИНА ЛЕНТЫ ПРОПАДАЕТ! ёЕЙЧАС БОЛЬШАЯ ЧАСТЬ
МАШИН ДОПУСКАЮТ ПЕРЕМЕННЫЙ РАЗМЕР БЛОКА, И ПОЭТОМУ НИЖЕ МЫ ОБСУДИМ
ПРОБЛЕМУ ВЫБОРА ПОДХОДЯЩЕГО РАЗМЕРА БЛОКА.
\picture{ЁИС.~80. ўИСЛО ЛИТЕР НА ОДНОЙ БОБИНЕ ЛЕНТЫ \MIXT{} КАК ФУНКЦИЯ ОТ
РАЗМЕРА БЛОКА.}

т КОНЦЕ ОПЕРАЦИИ ЧТЕНИЯ ИЛИ ЗАПИСИ ЛЕНТА ПРОХОДИТ С ПОЛНОЙ СКОРОСТЬЮ
ОКОЛО 66~ПЕРВЫХ ЛИТЕР МЕЖБЛОЧНОГО ПРОМЕЖУТКА. хСЛИ В ЭТО ВРЕМЯ БУДЕТ
ИНИЦИИРОВАНА СЛЕДУЮЩАЯ ОПЕРАЦИЯ ДЛЯ ЭТОЙ ЖЕ ЛЕНТЫ, ТО ДВИЖЕНИЕ ЛЕНТЫ
ПРОДОЛЖИТСЯ БЕЗ ПЕРЕРЫВА. эО ЕСЛИ СЛЕДУЮЩАЯ ОПЕРАЦИЯ НЕ НАЧНЕТСЯ
ДОСТАТОЧНО БЫСТРО,
\picture{
ЁИС.~81. ъАК ВЫЧИСЛИТЬ ВРЕМЯ СТАРТСТОПНОЙ ЗАДЕРЖКИ.
(юНО ДОБАВЛЯЕТСЯ КО ВРЕМЕНИ, ИСПОЛЬЗУЕМОМУ ПРИ ЧТЕНИИ ИЛИ ЗАПИСИ БЛОКОВ И
ПРОМЕЖУТКОВ.)
}
ТО ЛЕНТА ОСТАНОВИТСЯ И К ТОМУ ЖЕ ПОТРЕБУЕТСЯ НЕКОТОРОЕ ВРЕМЯ, ЧТОБЫ
РАЗОГНАТЬ ЕЕ ДО ПОЛНОЙ СКОРОСТИ В СЛЕДУЮЩЕЙ ОПЕРАЦИИ. ёУММАРНАЯ
СТАРТСТОПНАЯ ЗАДЕРЖКА СОСТАВЛЯЕТ 5~МС, 2~ДЛЯ ОСТАНОВКИ И~3 ДЛЯ РАЗГОНА
(РИС.~81). ЄАКИМ ОБРАЗОМ, ЕСЛИ МЫ НЕ
%%381
ПОДДЕРЖИВАЕМ НЕПРЕРЫВНОГО, БЕЗОСТАНОВОЧНОГО ДВИЖЕНИЯ ЛЕНТЫ С ПОЛНОЙ
СКОРОСТЬЮ, ТО ЭФФЕКТ ВО ВРЕМЕНИ СЧЕТА БУДЕТ, В СУЩНОСТИ, ТАКОЙ ЖЕ, КАК
ЕСЛИ БЫ В МЕЖБЛОЧНОМ ПРОМЕЖУТКЕ БЫЛО 780~ЛИТЕР ВМЕСТО~480.

ЁАССМОТРИМ ТЕПЕРЬ ОПЕРАЦИЮ \emph{ПЕРЕМОТКИ.} ъ СОЖАЛЕНИЮ, ОБЫЧНО ТРУДНО
ТОЧНО ОХАРАКТЕРИЗОВАТЬ ВРЕМЯ, ТРЕБУЕМОЕ ДЛЯ ПЕРЕМОТКИ ЛЕНТЫ НА ЗАДАННОЕ
ЧИСЛО ЛИТЕР~$n$. эА НЕКОТОРЫХ МАШИНАХ ИМЕЕТСЯ "БЫСТРАЯ ПЕРЕМОТКА", КОТОРАЯ
ПРИМЕНЯЕТСЯ, ТОЛЬКО ЕСЛИ $n$~ПРЕВЫШАЕТ ЧИСЛО ПОРЯДКА 5~МИЛЛИОНОВ; ДЛЯ
МЕНЬШИХ ЗНАЧЕНИЙ~$n$ ПЕРЕМОТКА ПРОИСХОДИТ С НОРМАЛЬНОЙ СКОРОСТЬЮ ЧТЕНИЯ/ЗАПИСИ.
\picture{
 ЁИС.~82. яРИБЛИЗИТЕЛЬНОЕ ВРЕМЯ СЧЕТА ПРИ ДВУХ ОБЫЧНО ИСПОЛЬЗУЕМЫХ МЕТОДАХ
 ПЕРЕМОТКИ.
}
эА ДРУГИХ МАШИНАХ ИМЕЕТСЯ СПЕЦИАЛЬНЫЙ МОТОР, ИСПОЛЬЗУЕМЫЙ ВО ВСЕХ
ОПЕРАЦИЯХ ПЕРЕМОТКИ; ОН ПОСТЕПЕННО УСКОРЯЕТ БОБИНУ ЛЕНТЫ ДО ОПРЕДЕЛЕННОГО
ЧИСЛА ОБОРОТОВ В МИНУТУ, А ЗАТЕМ ТОРМОЗИТ ЕЕ, КОГДА ПОДХОДИТ ВРЕМЯ
ОСТАНОВКИ; ДЕЙСТВИТЕЛЬНАЯ СКОРОСТЬ ЛЕНТЫ В ЭТОМ СЛУЧАЕ ЗАВИСИТ ОТ
ЗАПОЛНЕННОСТИ БОБИНЫ. ьЫ ПРИМЕМ ДЛЯ ПРОСТОТЫ, ЧТО \MIXT{} ТРЕБУЕТ
$\max (30, n/150)$~МС ДЛЯ ПЕРЕМОТКИ НА $n$~ЛИТЕРНЫХ ПОЗИЦИЙ (ВКЛЮЧАЯ ПРОМЕЖУТКИ),
Т.~Е.\ ПРИМЕРНО ДВЕ ПЯТЫХ ТОГО, ЧТО ТРЕБУЕТСЯ ДЛЯ ИХ ЧТЕНИЯ/ЗАПИСИ. ¤ТО
ДОСТАТОЧНО ХОРОШЕЕ ПРИБЛИЖЕНИЕ К ПОВЕДЕНИЮ МНОГИХ РЕАЛЬНЫХ УСТРОЙСТВ, ГДЕ
ОТНОШЕНИЕ ВРЕМЕНИ ЧТЕНИЯ/ЗАПИСИ КО ВРЕМЕНИ ПЕРЕМОТКИ ОБЫЧНО ЗАКЛЮЧЕНО
МЕЖДУ~2 И~3, НО ОНО НЕ ДАЕТ АДЕКВАТНОЙ МОДЕЛИ ЭФФЕКТА КОМБИНИРОВАННОЙ
НОРМАЛЬНОЙ И БЫСТРОЙ ПЕРЕМОТКИ, ИМЕЮЩЕЙСЯ НА МНОГИХ ДРУГИХ МАШИНАХ (РИС.~82).

яРИ ПЕРВОНАЧАЛЬНОЙ УСТАНОВКЕ И/ИЛИ ПЕРЕМОТКЕ К НАЧАЛУ ЛЕНТА, ПОМЕЩАЕТСЯ В
ТОЧКУ ЗАГРУЗКИ, И ДЛЯ ЛЮБОЙ ОПЕРАЦИИ ЧТЕНИЯ ИЛИ ЗАПИСИ, НАЧИНАЮЩЕЙСЯ ИЗ
ЭТОГО ПОЛОЖЕНИЯ, ТРЕБУЕТСЯ ДОПОЛНИТЕЛЬНО 110~МС. хСЛИ ЛЕНТА НЕ НАХОДИТСЯ В
ТОЧКЕ ЗАГРУЗКИ, ОНА МОЖЕТ БЫТЬ ПРОЧИТАНА В ОБРАТНОМ НАПРАВЛЕНИИ; 32~МС
%%382
ДОБАВЛЯЕТСЯ КО ВРЕМЕНИ ЛЮБОЙ ОБРАТНОЙ ОПЕРАЦИИ, СЛЕДУЮЩЕЙ ЗА ПРЯМОЙ, ИЛИ
ЛЮБОЙ ПРЯМОЙ ОПЕРАЦИИ, СЛЕДУЮЩЕЙ ЗА ОБРАТНОЙ.

эАКОНЕЦ, СЛЕДУЕТ РАССМОТРЕТЬ ВОЗМОЖНОСТЬ ОДНОВРЕМЕННОГО ВВОДА И ВЫВОДА.
ўАСТО ПО ЭКОНОМИЧЕСКИМ ПРИЧИНАМ НЕСКОЛЬКО ЛЕНТОЧНЫХ УСТРОЙСТВ
ПРИСОЕДИНЯЮТСЯ К ОДНОМУ \emph{ЛЕНТОЧНОМУ КОНТРОЛЛЕРУ} (УСТРОЙСТВУ
УПРАВЛЕНИЯ ЛЕНТАМИ), КОТОРЫЙ МОЖЕТ ОДНОВРЕМЕННО РАБОТАТЬ ТОЛЬКО С ОДНОЙ
ИЛИ ДВУМЯ ЛЕНТАМИ, ПОСКОЛЬКУ ЧИСЛО ЛИНИЙ ПЕРЕДАЧИ ДАННЫХ МЕЖДУ НИМ И
¤ть ОГРАНИЧЕННО. шНОГДА КОНТРОЛЛЕРЫ НЕ СПОСОБНЫ РАБОТАТЬ БОЛЕЕ ЧЕМ С ОДНОЙ
ЛЕНТОЙ ОДНОВРЕМЕННО. юДНАКО ЧАСТО ОНИ МОГУТ ЧИТАТЬ ОДНУ ЛЕНТУ ВО ВРЕМЯ
ЗАПИСИ ДРУГОЙ. эЕСКОЛЬКО РЕЖЕ ВСТРЕЧАЮТСЯ КОНТРОЛЛЕРЫ, КОТОРЫЕ МОГУТ
ЧИТАТЬ ОДНОВРЕМЕННО С ДВУХ УСТРОЙСТВ, И АВТОР НИКОГДА НЕ ВИДЕЛ КОНТРОЛЛЕРА,
 КОТОРЫЙ МОГ БЫ ПИСАТЬ НА ДВА УСТРОЙСТВА ОДНОВРЕМЕННО. яЕРЕМОТКА---ЭТО
ОСОБЫЙ СЛУЧАЙ: ЧЕРЕЗ 30~МС ПОСЛЕ НАЧАЛА ПЕРЕМОТКИ ЛЕНТОЧНОЕ УСТРОЙСТВО
\MIXT{} "ОТКЛЮЧАЕТСЯ" ОТ СВОЕГО КОНТРОЛЛЕРА, КОТОРЫЙ ПОСЛЕ ЭТОГО
СПОСОБЕН ВЫПОЛНЯТЬ ОПЕРАЦИИ С ДРУГИМИ УСТРОЙСТВАМИ. ЄАКИМ ОБРАЗОМ, ОЧЕНЬ
БОЛЬШОЕ ЧИСЛО ЛЕНТОЧНЫХ УСТРОЙСТВ МОГУТ ОДНОВРЕМЕННО ОСУЩЕСТВЛЯТЬ ПЕРЕМОТКУ.

яОЧТИ ВСЕ МАШИНЫ ДОПУСКАЮТ ВЫПОЛНЕНИЕ ВВОДА/ВЫВОДА ПАРАЛЛЕЛЬНО С
ВЫЧИСЛЕНИЯМИ, ХОТЯ МНОГИЕ ¤ть, КОГДА ПРОИСХОДИТ ВВОД/ВЫВОД, РАБОТАЮТ
НА~20--40\% МЕДЛЕННЕЕ ИЗ-ЗА "РАЗДЕЛЕНИЯ ЦИКЛОВ ПАМЯТИ".

\section ёНОВА О СЛИЯНИИ. юБРАТИМСЯ ВНОВЬ К ПРОЦЕССУ $P\hbox{-ПУТЕВОГО}$
СЛИЯНИЯ С УПОРОМ НА ФУНКЦИОНИРОВАНИЕ УСТРОЙСТВ ВВОДА И ВЫВОДА. сУДЕМ
СЧИТАТЬ, ЧТО ДЛЯ ВВОДНЫХ И ВЫВОДНОГО ФАЙЛОВ ИСПОЛЬЗУЕТСЯ $P+1$~ЛЕНТОЧНЫХ
УСТРОЙСТВ. эАША ЦЕЛЬ---МАКСИМАЛЬНО СОВМЕСТИТЬ ОПЕРАЦИИ ВВОДА/ВЫВОДА ДРУГ С
ДРУГОМ И СО СЧЕТОМ ПО ПРОГРАММЕ ТАК, ЧТОБЫ МИНИМИЗИРОВАТЬ ОБЩЕЕ ВРЕМЯ СЛИЯНИЯ.

яОУЧИТЕЛЬНО РАССМОТРЕТЬ СЛЕДУЮЩИЙ ЧАСТНЫЙ СЛУЧАЙ, В КОТОРОМ НА ВОЗМОЖНУЮ
СТЕПЕНЬ ОДНОВРЕМЕННОСТИ НАЛОЖЕНЫ СЕРЬЕЗНЫЕ ОГРАНИЧЕНИЯ. яРЕДПОЛОЖИМ, ЧТО
{\medskip\narrower
\item{a)}~МОЖНО ЗАПИСЫВАТЬ НЕ БОЛЕЕ ЧЕМ НА ОДНУ ЛЕНТУ ОДНОВРЕМЕННО;

\item{b)}~МОЖНО ЧИТАТЬ НЕ БОЛЕЕ ЧЕМ С ОДНОЙ ЛЕНТЫ ОДНОВРЕМЕННО;

\item{c)}~ЧТЕНИЕ, ЗАПИСЬ И ВЫЧИСЛЕНИЯ МОГУТ ПРОИСХОДИТЬ ОДНОВРЕМЕННО,
ТОЛЬКО ЕСЛИ ОПЕРАЦИИ ЧТЕНИЯ И ЗАПИСИ БЫЛИ НАЧАТЫ ОДНОВРЕМЕННО.
\medskip}
\noindent юКАЗЫВАЕТСЯ, ЧТО ДАЖЕ ПРИ ТАКИХ ОГРАНИЧЕНИЯХ ДОСТАТОЧНО ИМЕТЬ
$2P$~БУФЕРОВ ВВОДА И 2~БУФЕРА ВЫВОДА, ЧТОБЫ ПОДДЕРЖИВАТЬ, В СУЩНОСТИ,
МАКСИМАЛЬНУЮ СКОРОСТЬ ДВИЖЕНИЯ ЛЕНТ, ЕСЛИ ТОЛЬКО МЫ ИМЕЕМ ДЕЛО НЕ С ОЧЕНЬ
МЕДЛЕННОЙ ¤ть. чАМЕТИМ, ЧТО~(a) НЕ ЯВЛЯЕТСЯ НА САМОМ ДЕЛЕ ОГРАНИЧЕНИЕМ,
ТАК КАК ИМЕЕТСЯ ТОЛЬКО ОДНА ВЫВОДНАЯ ЛЕНТА. ъРОМЕ ТОГО, ОБоЕМ ВВОДА РАВЕН
%%383
ОБоЕМУ ВЫВОДА, ТАК ЧТО ЧИТАЕТСЯ В СРЕДНЕМ ТОЛЬКО ОДНА ЛЕНТА В ЛЮБОЙ ДАННЫЙ
МОМЕНТ ВРЕМЕНИ; ЕСЛИ УСЛОВИЕ~(b) НЕ ВЫПОЛНЯЕТСЯ, ТО ОБЯЗАТЕЛЬНО ДОЛЖНЫ
БЫТЬ ПЕРИОДЫ, КОГДА ВООБЩЕ НЕ ПРОИСХОДИТ ВВОДА. ёЛЕДОВАТЕЛЬНО, ДЛЯ ТОГО
ЧТОБЫ МИНИМИЗИРОВАТЬ ВРЕМЯ СЛИЯНИЯ, ДОСТАТОЧНО ПОДДЕРЖИВАТЬ
ВЫВОДНУЮ ЛЕНТУ В СОСТОЯНИИ РАБОТЫ.

тАЖНЫЙ МЕТОД, НАЗЫВАЕМЫЙ ПРЕДСКАЗАНИЕМ ИЛИ \emph{ПРОГНОЗИРОВАНИЕМ}
(forecasting), ДАЕТ ЖЕЛАЕМЫЙ ЭФФЕКТ. тО ВРЕМЯ ВЫПОЛНЕНИЯ
$P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ ОБЫЧНО ИМЕЕТСЯ~$P$ "ТЕКУЩИХ БУФЕРОВ ВВОДА",
КОТОРЫЕ ИСПОЛЬЗУЮТСЯ КАК ИСТОЧНИКИ ДАННЫХ; НЕКОТОРЫЕ ИЗ НИХ ЗАПОЛНЕНЫ
БОЛЬШЕ ДРУГИХ В ЗАВИСИМОСТИ ОТ ТОГО, КАКАЯ ЧАСТЬ ДАННЫХ В НИХ УЖЕ
ПРОСМОТРЕНА. хСЛИ ВСЕ ОНИ ОПУСТОШАТСЯ ПРИМЕРНО В ОДНО И ТО ЖЕ ВРЕМЯ, ТО,
ПРЕЖДЕ ЧЕМ ПРОДОЛЖИТЬ РАБОТУ, НАМ ПРИДЕТСЯ ВЫПОЛНИТЬ МНОГО ЧТЕНИЙ, ЕСЛИ
ТОЛЬКО МЫ НЕ ПРЕДПРИМЕМ НУЖНЫХ МЕР ЗАРАНЕЕ. ъ СЧАСТЬЮ, ВСЕГДА МОЖНО
СКАЗАТЬ, КАКОЙ БУФЕР ПЕРВЫМ СТАНЕТ ПУСТЫМ, ПРОСТА ПОСМОТРЕВ НА
\emph{ПОСЛЕДНЮЮ} ЗАПИСЬ В КАЖДОМ БУФЕРЕ. сУФЕР, ПОСЛЕДНЯЯ ЗАПИСЬ
КОТОРОГО ИМЕЕТ НАИМЕНЬШИЙ КЛЮЧ, ОБЯЗАТЕЛЬНО БУДЕТ ПЕРВЫМ ПУСТЫМ БУФЕРОМ
НЕЗАВИСИМО ОТ ЗНАЧЕНИЙ КАКИХ-ЛИБО ДРУГИХ КЛЮЧЕЙ, ТАК ЧТО МЫ ВСЕГДА ЗНАЕМ,
КАКОЙ ФАЙЛ ПОСЛУЖИТ ПРИЧИНОЙ НАШЕЙ СЛЕДУЮЩЕЙ КОМАНДЫ ВВОДА. рЛГОРИТМ~F
РАСКРЫВАЕТ ЭТОТ ПРИНЦИП В ДЕТАЛЯХ.

\alg F.(яРОГНОЗИРОВАНИЕ С ПЛАВАЮЩИМИ БУФЕРАМИ.) ¤ТОТ АЛГОРИТМ УПРАВЛЯЕТ
БУФЕРИЗАЦИЕЙ ВО ВРЕМЯ $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ ДЛИННЫХ ВВОДНЫХ ФАЙЛОВ
ПРИ~$P\ge 2$. фОПУСТИМ, ЧТО ВВОДНЫЕ ЛЕНТЫ И ФАЙЛЫ ЗАНУМЕРОВАНЫ~1, 2,~\dots,
 $P$. т АЛГОРИТМЕ ИСПОЛЬЗУЮТСЯ $2P$~БУФЕРОВ ВВОДА~$|I|[1]$,~\dots,
$|I|[2P]$, ДВА БУФЕРА ВЫВОДА~$|O|[0]$ И~$|O|[1]$ И СЛЕДУЮЩИЕ
ВСПОМОГАТЕЛЬНЫЕ МАССИВЫ:
\descrtable{
$|A|[j]$, $1\le j \le 2P$: & $0$ ЕСЛИ В БУФЕР~$|I|[j]$ МОЖНО ВВОДИТЬ ДАННЫЕ; \hfill\penalty -10000
                             $1$ В ПРОТИВНОМ СЛУЧАЕ. \cr
$|B|[i]$, $1\le i \le P$:  & сУФЕР, СОДЕРЖАЩИЙ ПОСЛЕДНИЙ ПРОЧИТАННЫЙ БЛОК ИЗ ФАЙЛА~$i$.\cr
$|C|[i]$, $1\le i \le P$:  & сУФЕР, ИСПОЛЬЗУЕМЫЙ В НАСТОЯЩИЙ МОМЕНТ ДЛЯ ВВОДА ИЗ ФАЙЛА~$i$.\cr
$|L|[i]$, $1\le i \le P$:  & яОСЛЕДНИЙ КЛЮЧ, ПРОЧИТАННЫЙ ИЗ ФАЙЛА~$i$.\cr
$|S|[j]$, $1\le j \le 2P$: & сУФЕР, КОТОРЫЙ СЛЕДУЕТ ИСПОЛЬЗОВАТЬ, КОГДА $|I|[j]$~ОПУСТОШИТСЯ. \cr
}
т ОПИСЫВАЕМОМ ВИДЕ АЛГОРИТМ НИКОГДА НЕ ОСТАНОВИТСЯ; ПОДХОДЯЩИЙ СПОСОБ
ЕГО "ВЫКЛЮЧЕНИЯ" ОБСУЖДАЕТСЯ НИЖЕ.

\st[эАЧАЛЬНАЯ УСТАНОВКА.] яРОЧИТАТЬ ПЕРВЫЙ БЛОК С ЛЕНТЫ~$i$ В
БУФЕР~$|I|[i]$, УСТАНОВИТЬ~$|A|[i]\asg 1$, $|A|[P+i] \asg 0$, $|B|[i]\asg
i$, $|C|[i]\asg i$ И УСТАНОВИТЬ~$|L|[i]$ РАВНЫМ КЛЮЧУ ПОСЛЕДНЕЙ
ЗАПИСИ В~$|I|[i]$ ПРИ~$1\le i \le P$. чАТЕМ НАЙТИ~$m$, ТАКОЕ,
%% 384
ЧТО~$L(m)=\min \set{|L|[1],~\ldots, |L|[P]}$, И УСТАНОВИТЬ~$t\asg 0$,
$k\asg P+1$. эАЧАТЬ ЧИТАТЬ С ЛЕНТЫ ОТ В БУФЕР~$|I|[k]$.

\st[ёЛИЯНИЕ.] ёЛИВАТЬ ЗАПИСИ ИЗ БУФЕРОВ~$|I|[|C|[1]]$,~\dots,
$|I|[|C|[P]]$ В~$|O|[t]$, ПОКА БУФЕР~$|O|[t]$ НЕ ЗАПОЛНИТСЯ. хСЛИ ВО ВРЕМЯ
ЭТОГО ПРОЦЕССА КАКОЙ-НИБУДЬ БУФЕР ВВОДА, СКАЖЕМ~$|I|[|C|[i]]$,
СТАНЕТ ПУСТЫМ, А~$|O|[t]$ ЕЩЕ НЕ ЗАПОЛНЕН, ТО УСТАНОВИТЬ~$|A|[|C|[i]]\asg 0$,
$|C|[i]\asg |S|[|C|[i]]$ И ПРОДОЛЖАТЬ СЛИЯНИЕ.

\st[тВОД/ВЫВОД ЗАВЕРШЕН.] цДАТЬ, ПОКА НЕ ЗАВЕРШИТСЯ ПРЕДЫДУЩАЯ ОПЕРАЦИЯ
ЧТЕНИЯ (ИЛИ ЧТЕНИЯ/ЗАПИСИ). чАТЕМ УСТАНОВИТЬ~$|A|[k]\asg 1$,
$|S|[|B|[m]]\asg k$, $|B|[m]\asg k$ И УСТАНОВИТЬ~$|L|[m]$ РАВНЫМ КЛЮЧУ
ПОСЛЕДНЕЙ ЗАПИСИ В~$|I|[k]$.

\st[яРОГНОЗИРОВАНИЕ.] эАЙТИ~$m$, ТАКОЕ, ЧТО~$|L|[m]=\min\set{|L|[1],
~\ldots, |L|[P]}$, И НАЙТИ~$k$, ТАКОЕ, ЧТО~$|A|[k]=0$.

\st[ўТЕНИЕ/ЗАПИСЬ.] эАЧАТЬ ЧИТАТЬ С ЛЕНТЫ~$m$ В БУФЕР~$|I|[k]$ И ПИСАТЬ ИЗ
БУФЕРА~$|O|[t]$ НА ВЫВОДНУЮ ЛЕНТУ, ЗАТЕМ ПОЛОЖИТЬ~$t\asg 1-t$ И ВЕРНУТЬСЯ
К~\stp{2}.
\algend
\picture{ЁИС.~83. яРОГНОЗИРОВАНИЕ С ПЛАВАЮЩИМИ БУФЕРАМИ.}

яРИМЕР НА РИС.~84 ПОКАЗЫВАЕТ, КАК РАБОТАЕТ МЕТОД ПРОГНОЗИРОВАНИЯ
ПРИ~$P=2$ В ПРЕДПОЛОЖЕНИИ, ЧТО КАЖДЫЙ БЛОК НА ЛЕНТЕ СОДЕРЖИТ ТОЛЬКО ДВЕ
ЗАПИСИ. чДЕСЬ ПРЕДСТАВЛЕНО СОДЕРЖИМОЕ БУФЕРОВ ВВОДА ВО ВСЕ МОМЕНТЫ, КОГДА
МЫ ДОСТИГАЕМ НАЧАЛА ШАГА~F2. рЛГОРИТМ~F, В СУЩНОСТИ, ОБРАЗУЕТ
$P$~\emph{ОЧЕРЕДЕЙ БУФЕРОВ,} ГДЕ $|C|[i]$~УКАЗЫВАЕТ НА НАЧАЛО
$i\hbox{-Й}$~ОЧЕРЕДИ, $|B|[i]$---НА ЕЕ КОНЕЦ, $|S|[j]$~УКАЗЫВАЕТ НА
ПРЕЕМНИКА БУФЕРА~$I[j]$; ЭТИМ УКАЗАНИЯМ НА  РИС.~84 СООТВЕТСТВУЮТ СТРЕЛКИ.
ёТРОКА~1 ОТРАЖАЕТ СОСТОЯНИЕ ДЕЛ ПОСЛЕ НАЧАЛЬНОЙ УСТАНОВКИ. фЛЯ КАЖДОГО
ВВОДНОГО ФАЙЛА ЕСТЬ ОДИН БУФЕР, И ЕЩЕ ОДИН БЛОК ЧИТАЕТСЯ ИЗ ФАЙЛА~1
(ТАК КАК~$03<05$). ёТРОКА~2 ПОКАЗЫВАЕТ ПОЛОЖЕНИЕ ВЕЩЕЙ ПОСЛЕ ТОГО, КАК
СЛИТ ПЕРВЫЙ БЛОК: МЫ ВЫВОДИМ БЛОК, СОДЕРЖАЩИЙ "\boxit{\hbox{$01\ 02$}}",
%%385
И ВВОДИМ СЛЕДУЮЩИЙ БЛОК ИЗ ФАЙЛА~2 (ТАК КАК~$05<09$). чАМЕТИМ, ЧТО В
СТРОКЕ~3 ТРИ ИЗ ЧЕТЫРЕХ БУФЕРОВ ВВОДА, ПО СУТИ ДЕЛА, ПРЕДОСТАВЛЕНЫ ФАЙЛУ~2,
ТАК КАК МЫ ЧИТАЕМ ИЗ ЭТОГО ФАЙЛА И В ЕГО ОЧЕРЕДИ УЖЕ ЕСТЬ ПОЛНЫЙ БУФЕР И
ЧАСТИЧНО ЗАПОЛНЕННЫЙ БУФЕР. ¤ТОТ МЕХАНИЗМ "ПЛАВАЮЩИХ БУФЕРОВ" ЯВЛЯЕТСЯ
ВАЖНОЙ ЧЕРТОЙ АЛГОРИТМА~F, ТАК КАК МЫ НЕ СМОГЛИ БЫ ПРОДОЛЖИТЬ РАБОТУ В
СТРОКЕ~4, ЕСЛИ БЫ В СТРОКЕ~3 ВЫБРАЛИ ДЛЯ ВВОДА ФАЙЛ~1 ВМЕСТО ФАЙЛА~2.
\picture{ЁИС.~84. юЧЕРЕДИ БУФЕРОВ В СООТВЕТСТВИИ С АЛГОРИТМОМ~F.}

ўТОБЫ ДОКАЗАТЬ ПРАВИЛЬНОСТЬ АЛГОРИТМА~F, МЫ ДОЛЖНЫ УСТАНОВИТЬ ДВА ФАКТА:
{\medskip\narrower
\item{i)}~ВСЕГДА ИМЕЕТСЯ СВОБОДНЫЙ БУФЕР (Т.~Е.\ МЫ ВСЕГДА МОЖЕМ НАЙТИ~$k$
НА ШАГЕ~F4);

\item{ii)}~ЕСЛИ БУФЕР ВВОДА ИСЧЕРПЫВАЕТСЯ ВО ВРЕМЯ СЛИЯНИЯ, ТО ЕГО
ПРЕЕМНИК УЖЕ ПРИСУТСТВУЕТ В ПАМЯТИ (Т.~Е.\ $|S|[|C|[i]$ В ШАГЕ~F2 ИМЕЕТ
ОСМЫСЛЕННОЕ ЗНАЧЕНИЕ).
\medskip}

\noindent фОПУСТИМ, ЧТО (i)~НЕ ИМЕЕТ МЕСТА, Т.~Е.\ ВСЕ БУФЕРЫ ЗАНЯТЫ
В НЕКОТОРЫЙ МОМЕНТ, КОГДА МЫ ДОСТИГАЕМ ШАГА~F4. ъАЖДЫЙ РАЗ, КОГДА МЫ
ПРИХОДИМ К ЭТОМУ ШАГУ, СУММАРНЫЙ ОБоЕМ НЕОБРАБОТАННЫХ ДАННЫХ ВО ВСЕХ
БУФЕРАХ СОСТАВЛЯЕТ РОВНО $P$~ЕМКОСТЕЙ БУФЕРА, Т.~Е.\ ДАННЫХ РОВНО СТОЛЬКО,
ЧТОБЫ, ПЕРЕМЕСТИВ ИХ, ЗАПОЛНИТЬ $P$~БУФЕРОВ, ИБО ДАННЫЕ ВВОДЯТСЯ И
ВЫВОДЯТСЯ С ОДИНАКОВОЙ СКОРОСТЬЮ. эЕКОТОРЫЕ БУФЕРЫ ЗАПОЛНЕНЫ ЛИШЬ ЧАСТИЧНО,
 ОДНАКО ДЛЯ КАЖДОГО ФАЙЛА ЧАСТИЧНО ЗАПОЛНЕН САМОЕ БОЛЬШЕЕ ОДИН БУФЕР,
ТАК ЧТО ВСЕГО ТАКИХ БУФЕРОВ НЕ БОЛЕЕ~$P$. яО ПРЕДПОЛОЖЕНИЮ ВСЕ
$2P$~БУФЕРОВ ЗАНЯТЫ, ТАК ЧТО ПО МЕНЬШЕЙ МЕРЕ~$P$ ИЗ НИХ
%% 386
ДОЛЖНЫ БЫТЬ ЗАПОЛНЕНЫ ЦЕЛИКОМ. ¤ТО МОЖЕТ СЛУЧИТЬСЯ, ТОЛЬКО ЕСЛИ
$P$~БУФЕРОВ ПОЛНЫ И $P$~ПУСТЫ, ИНАЧЕ МЫ БЫ ИМЕЛИ СЛИШКОМ МНОГО ДАННЫХ. эО
САМОЕ БОЛЬШЕЕ ОДИН БУФЕР МОЖЕТ БЫТЬ ОДНОВРЕМЕННО ПУСТ И ЗАНЯТ;
СЛЕДОВАТЕЛЬНО, (i)~Нe МОЖЕТ НЕ ВЫПОЛНЯТЬСЯ.

фОПУСТИМ, ЧТО~(ii) НЕ ИМЕЕТ МЕСТА, Т.~Е.\ ДЛЯ НЕКОТОРОГО ФАЙЛА В ПАМЯТИ
НЕТ НЕОБРАБОТАННЫХ ЗАПИСЕЙ, НО ТЕКУЩИЙ БУФЕР ВЫВОДА ЕЩЕ НЕ ПОЛОН. ёОГЛАСНО
ПРИНЦИПУ ПРОГНОЗИРОВАНИЯ, НУЖНО ИМЕТЬ НЕ БОЛЕЕ ОДНОГО БЛОКА ДАННЫХ ДЛЯ
ВСЕХ ОСТАЛЬНЫХ ФАЙЛОВ, ТАК КАК МЫ НЕ ЧИТАЕМ БЛОК ИЗ ФАЙЛА, ЕСЛИ ЭТОТ БЛОК
НЕ ПОТРЕБУЕТСЯ ПРЕЖДЕ, ЧЕМ БУДУТ ИСЧЕРПАНЫ БУФЕРЫ КАКОГО-НИБУДЬ
ДРУГОГО ФАЙЛА. ЄАКИМ ОБРАЗОМ, ОБЩЕЕ ЧИСЛО НЕОБРАБОТАННЫХ
ЗАПИСЕЙ СОСТАВЛЯЕТ САМОЕ БОЛЬШЕЕ $P-1$~БЛОКОВ; ДОБАВЛЕНИЕ НЕПОЛНОГО БУФЕРА
ВЫВОДА ДАЕТ МЕНЕЕ $P$~БУФЕРНЫХ ЕМКОСТЕЙ ДАННЫХ В ПАМЯТИ; ПОЛУЧИЛИ ПРОТИВОРЕЧИЕ.

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

юДИН ИЗ СПОСОБОВ ИЗЯЩНО ЗАВЕРШИТЬ АЛГОРИТМ~F СОСТОИТ В ТОМ, ЧТОБЫ
ПРИСВОИТЬ~$|L|[m]$ ЗНАЧЕНИЕ~$\infty$ НА ШАГЕ~F3, ЕСЛИ ТОЛЬКО ЧТО
ПРОЧИТАННЫЙ БЛОК БЫЛ ПОСЛЕДНИМ В ОТРЕЗКЕ. (ъОНЕЦ ОТРЕЗКА ВСЕГДА
УКАЗЫВАЕТСЯ НЕКОТОРЫМ ОСОБЫЕ ОБРАЗОМ.) яОСЛЕ ТОГО КАК БУДУТ ПРОЧИТАНЫ ВСЕ
ДАННЫЕ ВО ВСЕХ ФАЙЛАХ, МЫ В КОНЦЕ КОНЦОВ ОБНАРУЖИМ НА ШАГЕ~F4, ЧТО ВСЕ~$L$
РАВНЫ~$\infty$;
ТОГДА ОБЫЧНО МОЖНО НАЧАТЬ ЧТЕНИЕ ПЕРВЫХ БЛОКОВ СЛЕДУЮЩИХ ОТРЕЗКОВ В КАЖДОМ
ФАЙЛЕ, ВЫПОЛНЯЯ НАЧАЛЬНУЮ УСТАНОВКУ ДЛЯ СЛЕДУЮЩЕЙ ФАЗЫ СЛИЯНИЯ ПО МЕРЕ
ВЫВОДА ПОСЛЕДНИХ $P+1$~БЛОКОВ.

ЄАКИМ ОБРАЗОМ, МОЖНО ПОДДЕРЖИВАТЬ ПОЛНУЮ СКОРОСТЬ РАБОТЫ ВЫВОДНОЙ ЛЕНТЫ,
ЧИТАЯ В ЛЮБОЕ ВРЕМЯ НЕ БОЛЕЕ ОДНОЙ ЛЕНТЫ. шСКЛЮЧЕНИЕ ИЗ ЭТОГО ПРАВИЛА
ВСТРЕЧАЕТСЯ НА ШАГЕ~F1, ГДЕ БЫЛО БЫ ПОЛЕЗНО ЧИТАТЬ СРАЗУ НЕСКОЛЬКО ЛЕНТ,
ЧТОБЫ ОБЕСПЕЧИТЬ ВОЗМОЖНОСТЬ НАЧАТЬ РАБОТУ; НО ОБЫЧНО ШАГ~F1 МОЖНО
УСТРОИТЬ ТАК, ЧТОБЫ ОН СОВМЕЩАЛСЯ С ПРЕДЫДУЩЕЙ ЧАСТЬЮ ВЫЧИСЛЕНИЙ.

шДЕЯ ПРОСМОТРА ПОСЛЕДНЕЙ ЗАПИСИ КАЖДОГО БЛОКА С ЦЕЛЬЮ ПРЕДСКАЗАНИЯ, КАКОЙ
БУФЕР ПЕРВЫМ СТАНЕТ ПУСТЫМ, БЫЛА ВЫСКАЗАНА В 1953~Г.\ Ї.~¤.~уОЛЬБЕРТОН.
ёАМ МЕТОД ВПЕРВЫЕ БЫЛ ОПУБЛИКОВАН ¤.~X.~ЇРЭНДОМ [{\sl JACM,\/} {\bf 3}
(1956), 144--145, 165]. хГО ДОВОЛЬНО СЛОЖНЫЙ АЛГОРИТМ ИСПОЛЬЗОВАЛ
$3P$~БУФЕРОВ ВВОДА, И КАЖДОМУ ФАЙЛУ ВВОДА ПРЕДНАЗНАЧАЛОСЬ ПО ТРИ БУФЕРА;
АЛГОРИТМ~F УЛУЧШАЕТ ПОЛОЖЕНИЕ, ИСПОЛЬЗУЯ "ПЛАВАЮЩИЕ БУФЕРЫ" И ПОЗВОЛЯЯ
ЛЮБОМУ ОДНОМУ ФАЙЛУ ПОТРЕБОВАТЬ СРАЗУ ДАЖЕ $P+1$~БУФЕРОВ ВВОДА, ХОТЯ ВСЕГО
ТРЕБУЕТСЯ НЕ БОЛЕЕ $2P$~БУФЕРОВ.

ёЛИЯНИЕ С МЕНЕЕ ЧЕМ $2P$~БУФЕРАМИ ОБСУЖДАЕТСЯ В КОНЦЕ ЭТОГО ПУНКТА.
эЕКОТОРЫЕ ¤ть ИМЕЮТ ВОЗМОЖНОСТЬ "ЧТЕНИЯ ВРАЗБРОС---ЗАПИСИ
%%387
СО СБОРКОЙ", ЧТО ПОЗВОЛЯЕТ ОСУЩЕСТВЛЯТЬ ВВОД/ВЫВОД ИЗ
НЕПОСЛЕДОВАТЕЛЬНЫХ ЯЧЕЕК ПАМЯТИ; ИСПОЛЬЗОВАНИЕ ТАКОЙ ВОЗМОЖНОСТИ ВЫХОДИТ
ЗА РАМКИ ЭТОЙ КНИГИ.

\section ёРАВНИТЕЛЬНОЕ ПОВЕДЕНИЕ СХЕМ СЛИЯНИЯ. шСПОЛЬЗУЕМ ТЕПЕРЬ
НАШИ ЗНАНИЯ О ЛЕНТАХ И СЛИЯНИИ, ЧТОБЫ СРАВНИТЬ ЭФФЕКТИВНОСТЬ РАЗЛИЧНЫХ
СХЕМ СЛИЯНИЯ, ИЗУЧЕННЫХ НАМИ В П.~5.4.2--5.4.5. сУДЕТ ВЕСЬМА ПОУЧИТЕЛЬНО
РАЗРАБОТАТЬ ДЕТАЛИ КАЖДОГО МЕТОДА В ПРИМЕНЕНИИ К КОНКРЕТНОМУ
"БЕСПРИСТРАСТНОМУ" ПРИМЕРУ. ЁАССМОТРИМ ПОЭТОМУ ЗАДАЧУ СОРТИРОВКИ ФАЙЛА,
КАЖДАЯ ЗАПИСЬ КОТОРОГО СОДЕРЖИТ 100~ЛИТЕР, ПРИЧЕМ В ПАМЯТИ ДЛЯ ЗАПИСИ
ДАННЫХ ДОСТУПНО 100000~ЛИТЕРНЫХ ПОЗИЦИЙ (НЕ СЧИТАЯ МЕСТА ДЛЯ ПРОГРАММЫ,
ЕЕ ВСПОМОГАТЕЛЬНЫХ ПЕРЕМЕННЫХ И СРАВНИТЕЛЬНО НЕБОЛЬШОГО ПРОСТРАНСТВА,
НЕОБХОДИМОГО ДЛЯ ССЫЛОК В ДЕРЕВЕ ВЫБОРА). шСХОДНЫЕ ДАННЫЕ РАСПОЛОЖЕНЫ НА
ЛЕНТЕ В СЛУЧАЙНОМ ПОРЯДКЕ БЛОКАМИ ПО 5000~ЛИТЕР КАЖДЫЙ, И РЕЗУЛЬТАТ
ДОЛЖЕН ПОЛУЧИТЬСЯ В ТОМ ЖЕ ФОРМАТЕ. фЛЯ РАБОТЫ ИМЕЕТСЯ ПЯТЬ РАБОЧИХ ЛЕНТ
В ДОБАВЛЕНИЕ К УСТРОЙСТВУ, НА КОТОРОМ НАХОДИТСЯ ВВОДНАЯ ЛЕНТА.

юБЩЕЕ ЧИСЛО СОРТИРУЕМЫХ ЗАПИСЕЙ~100000, НО ЭТА ИНФОРМАЦИЯ АЛГОРИТМУ
СОРТИРОВКИ ЗАРАНЕЕ НЕ ИЗВЕСТНА.

т СХЕМУ~A (ЗДЕСЬ И ДАЛЕЕ СМ.~ВКЛАДКУ) СВЕДЕНЫ ТЕ ДЕЙСТВИЯ, КОТОРЫЕ
ПРОИСХОДЯТ, КОГДА К НАШИМ ДАННЫМ ПРИМЕНЯЕТСЯ ДЕСЯТЬ РАЗЛИЧНЫХ СХЕМ
СЛИЯНИЯ. юБРАТИВШИСЬ К ЭТОЙ ВАЖНОЙ ИЛЛЮСТРАЦИИ, ОЧЕНЬ ПОЛЕЗНО ВООБРАЗИТЬ,
ЧТО ВЫ НАБЛЮДАЕТЕ ЗА ТЕМ, КАК ПРОИСХОДИТ РЕАЛЬНАЯ СОРТИРОВКА:
МЕДЛЕННО ПРОСМАТРИВАЙТЕ КАЖДУЮ СТРОКУ СЛЕВА НАПРАВО, МЫСЛЕННО
ПРЕДСТАВЛЯЯ СЕБЕ ШЕСТЬ ЛЕНТ, ОСУЩЕСТВЛЯЮЩИХ ЧТЕНИЕ, ЗАПИСЬ, ПЕРЕМОТКУ
И/ИЛИ ОБРАТНОЕ ЧТЕНИЕ, КАК УКАЗАНО НА ДИАГРАММЕ. т ТЕЧЕНИЕ
$P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ ВВОДНЫЕ ЛЕНТЫ БУДУТ НАХОДИТЬСЯ В ДВИЖЕНИИ В
$P$~РАЗ РЕЖЕ, ЧЕМ ВЫВОДНАЯ ЛЕНТА. чАМЕТИМ, ЧТО В СХЕМЕ~A ПРЕДПОЛАГАЕТСЯ,
ЧТО, КОГДА ПЕРВОНАЧАЛЬНАЯ ВВОДНАЯ ЛЕНТА ПОЛНОСТЬЮ ПРОЧИТАНА (И ПЕРЕМОТАНА,
ЧТОБЫ ЕЕ УБРАТЬ), УМЕЛЫЙ ОПЕРАТОР СНИМАЕТ ЕЕ И ЗАМЕНЯЕТ РАБОЧЕЙ ЛЕНТОЙ ЗА
30~С. т ПРИМЕРАХ~2, 3 И~4 ЭТО И ЕСТЬ "ВРЕМЯ КРИТИЧЕСКОГО ПУТИ", КОГДА ¤ть
В БЕЗДЕЙСТВИИ ОЖИДАЕТ ОПЕРАТОРА. эО В ОСТАЛЬНЫХ ПРИМЕРАХ ОПЕРАЦИЯ СНЯТИЯ И
УСТАНОВКИ ЛЕНТ СОВМЕЩЕНА С ДРУГОЙ РАБОТОЙ. (эА СХЕМЕ~A ПО ГОРИЗОНТАЛИ
УКАЗАНО ВРЕМЯ В МИН.)

\def\example #1. #2.{{\bf яРИМЕР~#1. #2.}}
\example 1. ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. эАПОМНИМ ОПИСАНИЕ
ЗАДАЧИ: ЗАПИСИ ИМЕЮТ ДЛИНУ В 100~ЛИТЕР, ВНУТРЕННЕЙ ПАМЯТИ ДОСТАТОЧНО ДЛЯ
ОДНОВРЕМЕННОГО ХРАНЕНИЯ 1000~ЗАПИСЕЙ И КАЖДЫЙ БЛОК ВВОДНОЙ ЛЕНТЫ СОДЕРЖИТ
5000~ЛИТЕР (50~ЗАПИСЕЙ). тСЕГО ИМЕЕТСЯ $100\,000$~ЗАПИСЕЙ
(Т.~Е.\ $10\,000\,000$~ЛИТЕР, ИЛИ 2000~БЛОКОВ).
%%  388

ьЫ НИЧЕМ НЕ СВЯЗАНЫ В ВЫБОРЕ РАЗМЕРА БЛОКОВ ДЛЯ ПРОМЕЖУТОЧНЫХ ФАЙЛОВ.
°ЕСТИЛЕНТОЧНОЕ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ ИСПОЛЬЗУЕТ ТРЕХПУТЕВОЕ СЛИЯНИЕ,
ТАК ЧТО ТЕХНИКА АЛГОРИТМА F ТРЕБУЕТ 8~БУФЕРОВ; МОЖНО, СЛЕДОВАТЕЛЬНО,
ИСПОЛЬЗОВАТЬ БЛОКИ, СОДЕРЖАЩИЕ КАЖДЫЙ ПО $1000/8=125$~ЗАПИСЕЙ (ИЛИ 12500~ЛИТЕР).

яРОХОД НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ МОЖЕТ ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ
(П.~5.4.1), И, ЧТОБЫ ПОДДЕРЖИВАТЬ НЕПРЕРЫВНУЮ РАБОТУ ЛЕНТ, БУДЕМ
ИСПОЛЬЗОВАТЬ ДВА БУФЕРА ВВОДА ПО 50~ЗАПИСЕЙ КАЖДЫЙ, ПЛЮС ДВА БУФЕРА
ВЫВОДА ПО 125~ЗАПИСЕЙ КАЖДЫЙ. ¤ТО ОСТАВЛЯЕТ ДЛЯ ДЕРЕВА ВЫБОРА МЕСТО В
650~ЗАПИСЕЙ. сОЛЬШАЯ ЧАСТЬ НАЧАЛЬНЫХ ОТРЕЗКОВ БУДЕТ, СЛЕДОВАТЕЛЬНО, ИМЕТЬ
ДЛИНУ ОКОЛО 1300~ЗАПИСЕЙ (10 ИЛИ 11~БЛОКОВ); НА СХЕМЕ~A
ПОЛУЧИЛОСЬ 78~НАЧАЛЬНЫХ ОТРЕЗКОВ, ПРИЧЕМ ПОСЛЕДНИЙ ОТРЕЗОК КОРОТКИЙ.

яЕРВЫЙ ПРОХОД СЛИЯНИЯ, КАК ПОКАЗАНО, СЛИВАЕТ ДЕВЯТЬ ОТРЕЗКОВ НА ЛЕНТУ~4,
А НЕ ЧЕРЕДУЕТ ЛЕНТЫ~4, 5 И~6. ¤ТО ДАЕТ ВОЗМОЖНОСТЬ ВЫПОЛНЯТЬ ПОЛЕЗНУЮ
РАБОТУ В ТО ВРЕМЯ, КОГДА ОПЕРАТОР ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ УСТАНАВЛИВАЕТ
РАБОЧУЮ ЛЕНТУ НА УСТРОЙСТВО~6; ТАК КАК ОБЩЕЕ ЧИСЛО ОТРЕЗКОВ~$S$ ИЗВЕСТНО
СРАЗУ ПОСЛЕ ЗАВЕРШЕНИЯ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ, ТО АЛГОРИТМ ЗНАЕТ, ЧТО НА
ЛЕНТУ~4 ДОЛЖНО БЫТЬ СЛИТО $\ceil{S/9}$~ОТРЕЗКОВ, ЗАТЕМ $\ceil{(S-3)/9}$---НА
ЛЕНТУ~5, ЗАТЕМ $\ceil{(S-6)/9}$---НА ЛЕНТУ~6.

тСЯ ПРОЦЕДУРА СОРТИРОВКИ В ЭТОМ ПРИМЕРЕ МОЖЕТ БЫТЬ СЛЕДУЮЩИМ ОБРАЗОМ
ИЗОБРАЖЕНА С ИСПОЛЬЗОВАНИЕМ ОБОЗНАЧЕНИЙ, ВВЕДЕННЫХ В П.~5.4.2:
$$\def\emp{\hbox{---}}
\matrix{
1^{26} & 1^{26} & 1^{26} & \emp & \emp & \emp \cr
\emp   & \emp   & \emp   & 3^9  & 3^9  & 3^8  \cr
9^3    & 9^3    & 9^26^1 & \emp & \emp & \emp \cr
\emp   & \emp   & \emp   & 27^1 & 27^1 & 24^1 \cr
78^1   & \emp   & \emp   & \emp & \emp & \emp \cr
}
$$

\example 2. ьНОГОФАЗНОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. тТОРОЙ ПРИМЕР НА
СХЕМЕ~A ИЛЛЮСТРИРУЕТ МНОГОФАЗНОЕ СЛИЯНИЕ В СООТВЕТСТВИИ С
АЛГОРИТМОМ~5.4.2D. т ЭТОМ СЛУЧАЕ МЫ ВЫПОЛНЯЕМ ПЯТИПУТЕВОЕ СЛИЯНИЕ,
ПОЭТОМУ ПАМЯТЬ РАЗБИТА НА 12~БУФЕРОВ ПО 83~ЗАПИСИ КАЖДЫЙ.
т ТЕЧЕНИЕ ПЕРВОНАЧАЛЬНОГО ВЫБОРА С ЗАМЕЩЕНИЕМ МУ ИМЕЕМ ДВА БУФЕРА ВВОДА В
50~ЗАПИСЕЙ И ДВА БУФЕРА ВЫВОДА В 83~ЗАПИСИ, ЧТО ОСТАВЛЯЕТ 734~ЗАПИСИ В
ДЕРЕВЕ; ТАКИМ ОБРАЗОМ, НАЧАЛЬНЫЕ ОТРЕЗКИ В ЭТОТ РАЗ БУДУТ ИМЕТЬ
ДЛИНУ ОКОЛО 1468~ЗАПИСЕЙ (17 ИЛИ 18~БЛОКОВ). т ДАННОЙ СИТУАЦИИ ПОЛУЧЕНО
$S=70$~НАЧАЛЬНЫХ ОТРЕЗКОВ, ПРИЧЕМ ДЛИНЫ ДВУХ ПОСЛЕДНИХ В
ДЕЙСТВИТЕЛЬНОСТИ РАВНЫ ТОЛЬКО ЧЕТЫРЕМ БЛОКАМ И  ОДНОМУ БЛОКУ
СООТВЕТСТВЕННО. ёХЕМУ СЛИЯНИЯ МОЖНО ИЗОБРАЗИТЬ ТАК:
%%389
$$\def\emp{\hbox{---}}
\matrix{
0^{13}1^{18} & 0^{13}1^{17} & 0^{13}1^{15} & 0^{12}1^{12} & 0^81^1 & \emp \cr
1^{15}       & 1^{14}       & 1^{12}       & 1^8          & \emp   & 0^8 1^4 2^1 5^3 \cr
1^7          & 1^6          & 1^4          & \emp         & 4^8    & 1^4 2^1 5^3 \cr
1^3          & 1^2          & \emp         & 8^4          & 4^4    & 2^1 5^3 \cr
1^1          & \emp         & 16^1 19^1    & 8^2          & 4^2    & 5^2 \cr
\emp         & 34^1         & 19^1         & 8^1          & 4^1    & 5^1 \cr
70^1         & \emp         & \emp         & \emp         & \emp   & \emp \cr
}
$$
єДИВИТЕЛЬНО, ЧТО МНОГОФАЗНОЕ СЛИЯНИЕ ЗАНИМАЕТ НА 25~С
\emph{БОЛЬШЕ} ВРЕМЕНИ, ЧЕМ ЗНАЧИТЕЛЬНО БОЛЕЕ ПРОСТОЕ СБАЛАНСИРОВАННОЕ
СЛИЯНИЕ! ¤ТО ОБоЯСНЯЕТСЯ ДВУМЯ ОСНОВНЫМИ ПРИЧИНАМИ:

\enumerate
\li ¤ТОТ СЛУЧАЙ ОСОБЕННО УДАЧЕН ДЛЯ СБАЛАНСИРОВАННОГО СЛИЯНИЯ, ТАК
КАК~$S=78$ ОЧЕНЬ БЛИЗКО К ТОЧНОЙ СТЕПЕНИ~3. хСЛИ БЫ БЫЛО ПОЛУЧЕНО
82~НАЧАЛЬНЫХ ОТРЕЗКА, ТО СБАЛАНСИРОВАННОЕ СЛИЯНИЕ ЗАНЯЛО БЫ ЕЩЕ ОДИН ПРОХОД.

\li яРИ МНОГОФАЗНОМ СЛИЯНИИ ТЕРЯЕТСЯ 30~c ВО ВРЕМЯ ЗАМЕНЫ ВВОДНОЙ ЛЕНТЫ И
В ЦЕЛОМ СВЫШЕ 5~МИН ПРОХОДИТ В ОЖИДАНИИ ЗАВЕРШЕНИЯ ОПЕРАЦИЙ ПЕРЕМОТКИ. т
ПРОТИВОПОЛОЖНОСТЬ ЭТОМУ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ ТРЕБОВАЛО СРАВНИТЕЛЬНО
НЕБОЛЬШОГО ВРЕМЕНИ ПЕРЕМОТКИ. тО ВТОРОЙ ФАЗЕ МНОГОФАЗНОГО
СЛИЯНИЯ СЭКОНОМЛЕНО 13~С, ТАК КАК 8~ФИКТИВНЫХ ОТРЕЗКОВ НА ЛЕНТЕ~6 МОЖНО
СЧИТАТЬ ПРИСУТСТВУЮЩИМИ ДАЖЕ ВО ВРЕМЯ ПЕРЕМОТКИ ЭТОЙ ЛЕНТЫ, НО ДАЛЬШЕ НЕ
ПРОИСХОДИТ НИКАКОГО СОВМЕЩЕНИЯ ПЕРЕМОТКИ. ЄАКИМ ОБРАЗОМ, МНОГОФАЗНЫЙ
МЕТОД ПРОИГРЫВАЕТ, НЕСМОТРЯ НА ТО, ЧТО ОН ТРЕБУЕТ ЗНАЧИТЕЛЬНО МЕНЬШЕГО
ВРЕМЕНИ ЧТЕНИЯ/ЗАПИСИ.
\enumend

\example 3. ъАСКАДНОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. ¤ТОТ СЛУЧАЙ АНАЛОГИЧЕН
ПРЕДЫДУЩЕМУ, ТОЛЬКО ИСПОЛЬЗУЕТ АЛГОРИТМ~5.4.3ё. ёЛИЯНИЕ ИЗОБРАЖАЕТСЯ ТАК:
$$\def\emp{\hbox{---}}
\matrix{
1^{14}  & 1^{15} & 1^{12}  & 1^{14} & 1^{15} & \emp \cr
1^5     & 1^9    & \emp    & 1^{14} & 1^{15} & 1^3 2^3 3^6 \cr
5^1 6^3 & 5^3    & 5^3 6^2 & \emp   & 1^1    & 2^2 \cr
\emp    & 12^1   & 6^1     & 18^1   & 18^1   & 16^1 \cr
70^1    & \emp   & \emp    & \emp   & \emp   & \emp\cr
}
$$
(яРОСМАТРИВАЯ СХЕМУ~A, НЕ ЗАБЫВАЙТЕ ПРЕДСТАВЛЯТЬ КАЖДЫЙ ПРИМЕР В ДЕЙСТВИИ.)

\example 4. ьНОГОФАЗНОЕ СЛИЯНИЕ С РАСЩЕПЛЕНИЕМ ЛЕНТ. ¤ТА ПРОЦЕДУРА,
ОПИСАННАЯ В КОНЦЕ П.~5.4.2, ПОЗВОЛЯЕТ СОВМЕСТИТЬ БОЛЬШУЮ ЧАСТЬ ВРЕМЕНИ
ПЕРЕМОТКИ. юНА ИСПОЛЬЗУЕТ ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ, ТАК ЧТО МЫ ДЕЛИМ ПАМЯТЬ
НА ДЕСЯТЬ БУФЕРОВ ПО 100~ЗАПИСЕЙ; В ДЕРЕВЕ ВЫБОРА ИМЕЕТСЯ 700~ЗАПИСЕЙ, И
В РЕЗУЛЬТАТЕ
%%390
ОКАЗЫВАЕТСЯ, ЧТО ОБРАЗОВАНО 72~НАЧАЛЬНЫХ ОТРЕЗКА. яОСЛЕДНИЙ ОТРЕЗОК ВНОВЬ
ОЧЕНЬ КОРОТКИЙ. шСПОЛЬЗОВАНА СХЕМА РАСПРЕДЕЛЕНИЯ, АНАЛОГИЧНАЯ
АЛГОРИТМУ~5.4.2D, ЗА НЕЙ СЛЕДУЕТ ПРОСТОЙ, НО ДО НЕКОТОРОЙ СТЕПЕНИ
СПЕЦИАЛЬНЫЙ МЕТОД РАЗМЕЩЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ:
$$\def\emp{\hbox{---}}
\matrix{
1^{21}     & 1^{19}     & 1^{15}       & 1^8       & \emp            & 0^2 1^9 \cr
0^2 1^{17} & 0^2 1^{15} & 0^2 1^{11}   & 0^2 1^4   & \emp            & 0^2 1^9 4^4 \cr
1^{13}     & 1^{11}     & 1^7          & \emp      & 0^2 4^4         & 0^2 1^9 4^4 \cr
1^{10}     & 1^8        & 1^4          & \emp      & 0^2 4^4 3^2 4^1 & 1^8 4^4 \cr
1^6        & 1^4        & \emp         & 4^4       & 0^2 4^4 3^2 4^1 & 1^4 4^4 \cr
1^5        & 1^3        & \emp         & 4^4 3^1   & 0^1 4^4 3^2 4^1 & 1^3 4^4 \cr
1^2        & \emp       & 3^1 7^2      & 4^4 3^1   & 4^2 3^2 4^1     & 4^4 \cr
1^1        & \emp       & 3^1 7^2 13^1 & 4^3 3^1   & 4^1 3^2 4^1     & 4^3 \cr
\emp       & 13^1       & 3^1 7^2 13^1 & 4^2 3^1   & 3^2 4^1         & 4^2 \cr
\emp       & 13^1 14^1  & 7^2 13^1     & 4^1 3^1   & 3^1 4^1         & 4^1 \cr
18^1       & 13^1 14^1  & 7^1 13^1     & 3^1       & 4^1             & \emp \cr
18^1       & 14^1       & 13^1         & \emp      & \emp            & 27^1 \cr
\emp       & \emp       & \emp         & 72^1      & \emp            & \emp \cr
}
$$
ёРЕДИ ВСЕХ ПРИМЕРОВ НА СХЕМЕ~A, КОТОРЫЕ НЕ ЧИТАЮТ В ОБРАТНОМ НАПРАВЛЕНИИ,
В ЭТОМ, КАК ОКАЗЫВАЕТСЯ, НАИЛУЧШЕЕ ВРЕМЯ ВЫПОЛНЕНИЯ. ЄАК КАК $S$~НИКОГДА
НЕ БЫВАЕТ ОЧЕНЬ БОЛЬШИМ, МОЖНО РАЗРАБОТАТЬ БОЛЕЕ СЛОЖНЫЙ АЛГОРИТМ, КОТОРЫЙ
РАЗМЕЩАЕТ ФИКТИВНЫЕ ОТРЕЗКИ ЕЩЕ ЛУЧШЕ (СМ.~УПР.~5.4.2-26).

\example 5. ъАСКАДНОЕ СЛИЯНИЕ С СОВМЕЩЕНИЕМ ПЕРЕМОТОК. ¤ТА
ПРОЦЕДУРА РАБОТАЕТ ПОЧТИ ТАК ЖЕ БЫСТРО, КАК ПРЕДЫДУЩАЯ, ХОТЯ УПРАВЛЯЮЩИЙ
ЕЮ АЛГОРИТМ БОЛЕЕ ПРОСТ. ьЫ ИСПОЛЬЗУЕМ ДЛЯ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ МЕТОД
КАСКАДНОЙ СОРТИРОВКИ, КАК В АЛГОРИТМЕ~5.4.3C, НО С~$T=5$, А НЕ~$T=6$.
чАТЕМ ИСПОЛЬЗОВАНИЕ ЛЕНТ В КАЖДОЙ ФАЗЕ КАЖДОГО "КАСКАДА" ЧЕРЕДУЕТСЯ ТАКИМ
ОБРАЗОМ, ЧТО МЫ ОБЫЧНО НЕ ПИШЕМ НА ЛЕНТУ, ПОКА ОНА ПОЧТИ НАВЕРНЯКА НЕ
ОКАЖЕТСЯ ПЕРЕМОТАННОЙ. ъОРОЧЕ ГОВОРЯ, СХЕМА ТАКОВА:
$$\def\emp{\hbox{---}}
\matrix{
1^{21} & 1^{22} & 1^{19} & 1^{10} & \emp        & \emp \cr
1^4    & 1^7    & \emp   & \emp   & 1^2 2^2 3^5 & 4^{10} \cr
7^2    & \emp   & 8^3    & 7^2 8^2& \emp        & 4^1 \cr
\emp   & 26^1   & \emp   & 8^1    & 22^1        & 16^1 \cr
72^1   & \emp   & \emp   & \emp   & \emp        & \emp \cr
}
$$

\example 6. ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. ¤ТОТ ПРИМЕР ПОХОЖ
НА ПРИМЕР~1, НО ВСЕ ПЕРЕМОТКИ УСТРАНЕНЫ:
%% 391
$$\def\emp{\hbox{---}}
\matrix{
A_1^{26} & A_1^{26} & A_1^{26}    & \emp     & \emp     & \emp \cr
\emp     & \emp     & \emp        & D_3^9    & D_3^9    & D_3^8 \cr
A_9^3    & A_9^3    & A_9^2 A_6^1 & \emp     & \emp     & \emp \cr
\emp     & \emp     & \emp        & D_{24}^1 & D_{27}^1 & D_{27}^1 \cr
A_{78}^1 & \emp     & \emp        & \emp     & \emp     & \emp \cr
}
$$
ЄАК КАК В ПРИМЕРЕ~1 БЫЛО СРАВНИТЕЛЬНО МАЛО ПЕРЕМОТОК, ТО ЭТА СХЕМА НЕ
НАМНОГО ЛУЧШЕ, ЧЕМ В СЛУЧАЕ ПРЯМОГО ЧТЕНИЯ. ЇАКТИЧЕСКИ ОНА ОКАЗЫВАЕТСЯ
НЕСКОЛЬКО МЕДЛЕННЕЙ МНОГОФАЗНОЙ СХЕМЫ С РАСЩЕПЛЕНИЕМ ЛЕНТ, НЕСМОТРЯ НА
УДАЧНОЕ ЗНАЧЕНИЕ~$S=78$.

\example 7. ьНОГОФАЗНОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. т ЭТОМ ПРИМЕРЕ
ИСПОЛЬЗУЕТСЯ ТОЛЬКО ПЯТЬ ЛЕНТ ИЗ ШЕСТИ, ЧТОБЫ УСТРАНИТЬ ВРЕМЯ ПЕРЕМОТКИ
И СМЕНЫ ВВОДНОЙ ЛЕНТЫ. ЄАКИМ ОБРАЗОМ, ИСПОЛЬЗУЕТСЯ ТОЛЬКО ЧЕТЫРЕХПУТЕВОЕ
СЛИЯНИЕ И ТАКАЯ ЖЕ СТРУКТУРА БУФЕРОВ, КАК В ПРИМЕРАХ~4 И~5. шСПОЛЬЗУЕТСЯ
РАСПРЕДЕЛЕНИЕ, АНАЛОГИЧНОЕ АЛГОРИТМУ~5.4.2D, НО НАПРАВЛЕНИЕ
ОТРЕЗКОВ ЧЕРЕДУЕТСЯ, И ЛЕНТА~1 ЗАФИКСИРОВАНА, КАК КОНЕЧНАЯ ВЫВОДНАЯ ЛЕНТА.
яЕРВЫМ ЗАПИСЫВАЕТСЯ ВОЗРАСТАЮЩИЙ ОТРЕЗОК НА ЛЕНТУ~1;
ЗАТЕМ УБЫВАЮЩИЕ ОТРЕЗКИ НА ЛЕНТЫ~2, 3, 4; ЗАТЕМ ВОЗРАСТАЮЩИЕ ОТРЕЗКИ НА~2,
3, 4; ЗАТЕМ УБЫВАЮЩИЕ НА~1, 2, 3 И~Т.~Д. тСЯКИЙ РАЗ, КАК МЫ ПЕРЕКЛЮЧАЕМ
НАПРАВЛЕНИЕ, ВЫБОР С ЗАМЕЩЕНИЕМ ОБЫЧНО ДАЕТ БОЛЕЕ КОРОТКИЙ ОТРЕЗОК,
ПОЭТОМУ ОКАЗАЛОСЬ ОБРАЗОВАНО 77~НАЧАЛЬНЫХ ОТРЕЗКОВ ВМЕСТО~72 В
ПРИМЕРАХ~4 И~5.

¤ТА ПРОЦЕДУРА В РЕЗУЛЬТАТЕ ДАЕТ РАСПРЕДЕЛЕНИЕ $(22, 21, 19, 15)$~ОТРЕЗКОВ,
А БЛИЖАЙШЕЕ ТОЧНОЕ РАСПРЕДЕЛЕНИЕ---$(29, 56, 52, 44)$. єПРАЖНЕНИЕ~5.4.4-5
ПОКАЗЫВАЕТ, КАК ПОСТРОИТЬ СТРОКИ ЧИСЕЛ СЛИЯНИЯ, КОТОРЫЕ МОГУТ БЫТЬ
ИСПОЛЬЗОВАНЫ ДЛЯ РАЗМЕЩЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ "ОПТИМАЛЬНЫМ" ОБРАЗОМ;
ТАКАЯ ПРОЦЕДУРА ВОЗМОЖНА НА ПРАКТИКЕ, ПОСКОЛЬКУ КОНЕЧНОСТЬ
БОБИНЫ ГАРАНТИРУЕТ, ЧТО $S$~НИКОГДА НЕ БУДЕТ СЛИШКОМ БОЛЬШИМ.
яОЭТОМУ ПРИМЕР НА СХЕМЕ~A БЫЛ ПОСТРОЕН С ИСПОЛЬЗОВАНИЕМ ТАКОГО МЕТОДА
РАЗМЕЩЕНИЯ ФИКТИВНЫХ ОТРЕЗКОВ (СМ.~УПР.~7). юН ОКАЗАЛСЯ САМЫМ БЫСТРЫМ ИЗ
ВСЕХ ПРЕДСТАВЛЕННЫХ ПРИМЕРОВ.

\example 8. ъАСКАДНОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. ъАК И В ПРИМЕРЕ~7,
ЗДЕСЬ УЧАСТВУЕТ ТОЛЬКО ПЯТЬ ЛЕНТ. ¤ТА ПРОЦЕДУРА СЛЕДУЕТ АЛГОРИТМУ~5.4.3C,
 ИСПОЛЬЗУЯ ПЕРЕМОТКУ И ПРЯМОЕ ЧТЕНИЕ, ЧТОБЫ ИЗБЕЖАТЬ ОДНОПУТЕВОГО СЛИЯНИЯ
(ТАК КАК ПЕРЕМОТКА БОЛЕЕ ЧЕМ В ДВА РАЗА БЫСТРЕЕ ЧТЕНИЯ НА УСТРОЙСТВАХ \MIXT).
ЁАСПРЕДЕЛЕНИЕ, СЛЕДОВАТЕЛЬНО, ТО ЖЕ, ЧТО И В ПРИМЕРЕ~6.
шСПОЛЬЗУЯ СИМВОЛ~$\downarrow$ ДЛЯ ОБОЗНАЧЕНИЯ ПЕРЕМОТКИ, ИЗОБРАЗИМ
ЭТУ СХЕМУ ТАК:
%%392
$$\def\emp{\hbox{---}}\def\da{\downarrow}
\matrix{
A_1^{21}  & A_1^{22} & A_1^{19} & A_1^{10}                & \emp\cr
A_1^4\da  & A_1^7\da & \emp     & \hbox{}_1^2 D_2^2 D_3^5 & D_4^{10} \cr
A_8 A_7^2 & A_5^2    & A_9^4    & \emp                    & D_4^1\da \cr
\emp      & D_{17}   & A_9\da   & D_{25}                  & D_{21} \cr
}
$$

\example 9. юСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ОБРАТНЫМ ЧТЕНИЕМ. юСЦИЛЛИРУЮЩАЯ
СОРТИРОВКА С~$T=5$ (АЛГОРИТМ~5.4.5B) МОЖЕТ ИСПОЛЬЗОВАТЬ РАСПРЕДЕЛЕНИЕ
БУФЕРОВ, КАК В ПРИМЕРАХ~4, 5, 7 И~8, ТАК КАК ОНА ВЫПОЛНЯЕТ ЧЕТЫРЕХПУТЕВОЕ
СЛИЯНИЕ. юДНАКО ВЫБОР С ЗАМЕЩЕНИЕМ ДЕЙСТВУЕТ ЗДЕСЬ ИНАЧЕ, ПОСКОЛЬКУ
НЕПОСРЕДСТВЕННО ПЕРЕД ВХОДОМ В КАЖДУЮ ФАЗУ СЛИЯНИЯ ВЫВОДИТСЯ ОТРЕЗОК
ДЛИНЫ~700 (А НЕ ПРИМЕРНО~1400), ЧТОБЫ ОЧИСТИТЬ ВНУТРЕННЮЮ
ПАМЯТЬ. ёЛЕДОВАТЕЛЬНО, ЗДЕСЬ ПОРОЖДАЕТСЯ 85~ОТРЕЗКОВ ВМЕСТО~72.
эЕКОТОРЫЕ КЛЮЧЕВЫЕ ШАГИ ЭТОГО ПРОЦЕССА ТАКОВЫ:
$$\def\emp{\hbox{---}}
\matrix{
\emp    & A_1            & A_1 A_1          & A_1 A_1          & A_1 A_1 \cr
D_4     & \emp           & A_1              & A_1              & A_1 \cr
\multispan{5}\dotfill\cr
D_4 D_4 & D_4 D_4        & D_4 D_4          & D_4              & \emp \cr
D_4     & D_4            & D_4              & \emp             & A_{16} \cr
\multispan{5}\dotfill\cr
D_4     & A_{16} D_4 D_4 & A_{16} D_4       & A_{16} D_4 A_1   & A_{16} \cr
D_4     & A_{16} D_4 D_4 & A_{16} D_4 D_1   & A_{16} D_4       & A_{16} \cr
\emp    & A_{16} D_4     & A_{16} D_4       & A_{16}           & A_{16} A_{13} \cr
\emp    & A_{16} D_4     & A_{16}           & A_{16} A_4       & A_{16} A_{13} \cr
\emp    & A_{16}         & A_{16} A_4       & A_{16} A_4       & A_{16} A_{13} \cr
D_{37}  & \emp           & A_{16}\downarrow & A_{16}\downarrow & A_{16}\downarrow \cr
\emp    & A_{85}         & \emp             & \emp             & \emp \cr
}
$$

\example 10. юСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ПРЯМЫМ ЧТЕНИЕМ.
т ПОСЛЕДНЕМ ПРИМЕРЕ ВЫБОР С ЗАМЕЩЕНИЕМ НЕ ИСПОЛЬЗУЕТСЯ, ТАК КАК ВСЕ
НАЧАЛЬНЫЕ ОТРЕЗКИ ДОЛЖНЫ БЫТЬ ОДНОЙ ДЛИНЫ. ёЛЕДОВАТЕЛЬНО, БУДЕТ
ПРОИСХОДИТЬ ВНУТРЕННЯЯ СОРТИРОВКА 1000~ЗАПИСЕЙ (ПОЛНОЙ ЕМКОСТИ ПАМЯТИ)
КАЖДЫЙ РАЗ, КОГДА ТРЕБУЕТСЯ НАЧАЛЬНЫЙ ОТРЕЗОК; ЭТО ДАЕТ~$S=100$. тОТ
НЕКОТОРЫЕ КЛЮЧЕВЫЕ ШАГИ ПРОЦЕССА:
%%393
$$\def\emp{\hbox{---}}
\matrix{
A_1            & A_1     & A_1     & A_1     & A_1 \cr
\emp           & \emp    & \emp    & \emp    & A_1 A_4 \cr
\multispan{5} \dotfill\cr
A_1            & A_1     & A_1     & A_1     & A_1 A_4 \cr
\emp           & \emp    & \emp    & A_1 A_4 & A_1 A_4\cr
\emp           & \emp    & \emp    & A_1 A_4 & A_1 A_4 \cr
\multispan{5} \dotfill\cr
A_1            & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 \cr
A_1 A_4        & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 \cr
A_1 A_4 A_{16} & \emp    & \emp    & \emp    & \emp \cr
\multispan{5} \dotfill\cr
\emp           & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 A_{16} A_{64} \cr
A_4            & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 A_{16} A_{64} \cr
A_4 A_{16}     & \emp    & \emp    & \emp    & A_1 A_4 A_{16} A_{64} \cr
A_4 A_{16}     & A_4     & \emp    & \emp    & A_1 A_4 A_{16} A_{64} \cr
\emp           & \emp    & \emp    & A_{36}  & A_1 A_4 A_{16} A_{64} \cr
A_{100}        & \emp    & \emp    & \emp    & \emp \cr
}
$$
¤ТА ПРОГРАММА ОКАЗЫВАЕТСЯ САМОЙ МЕДЛЕННОЙ ИЗ ВСЕХ ЧАСТИЧНО ИЗ-ЗА ТОГО, ЧТО
ОНА НЕ ИСПОЛЬЗУЕТ ВЫБОР С ЗАМЕЩЕНИЕМ, НО БОЛЬШЕЙ ЧАСТЬЮ ВСЛЕДСТВИЕ ЕЕ
ВЕСЬМА НЕСКЛАДНОГО КОНЦА (ДВУХПУТЕВОЕ СЛИЯНИЕ).

\section юЦЕНКА ВРЕМЕНИ ВЫПОЛНЕНИЯ. яОСМОТРИМ ТЕПЕРЬ, КАК
ВЫЧИСЛИТЬ ПРИБЛИЗИТЕЛЬНОЕ ВРЕМЯ ВЫПОЛНЕНИЯ МЕТОДА СОРТИРОВКИ,
ИСПОЛЬЗУЮЩЕГО ЛЕНТЫ \MIXT. ьОЖНО ЛИ ПРЕДСКАЗАТЬ РЕЗУЛЬТАТЫ,
ИЗОБРАЖЕННЫЕ НА СХЕМЕ~A, НЕ ВЫПОЛНЯЯ ДЕТАЛЬНОГО МОДЕЛИРОВАНИЯ?

юДИН СПОСОБ, КОТОРЫЙ ТРАДИЦИОННО ИСПОЛЬЗОВАЛСЯ ДЛЯ СРАВНЕНИЯ РАЗЛИЧНЫХ
СХЕМ СЛИЯНИЯ, СОСТОИТ В ТОМ, ЧТОБЫ НАЛОЖИТЬ ДРУГ НА ДРУГА ГРАФИКИ,
ПОДОБНЫЕ ПРЕДСТАВЛЕННЫМ НА РИС.~70, 74 И~78. ¤ТИ ГРАФИКИ ИЗОБРАЖАЮТ
ЭФФЕКТИВНОЕ ЧИСЛО ПРОХОДОВ ПО ДАННЫМ КАК ФУНКЦИЮ ОТ ЧИСЛА НАЧАЛЬНЫХ
ОТРЕЗКОВ В ПРЕДПОЛОЖЕНИИ, ЧТО ВСЕ НАЧАЛЬНЫЕ ОТРЕЗКИ ИМЕЮТ ПРИМЕРНО
РАВНУЮ ДЛИНУ (РИС.~85). эО ЭТО \emph{НЕ} ДАЕТ ОЧЕНЬ РЕАЛИСТИЧНОГО
СРАВНЕНИЯ, ПОТОМУ ЧТО, КАК МЫ ВИДЕЛИ, РАЗНЫЕ МЕТОДЫ ПРИВОДЯТ К
РАЗЛИЧНОМУ ЧИСЛУ НАЧАЛЬНЫХ ОТРЕЗКОВ; КРОМЕ ТОГО, ИМЕЮТСЯ
РАЗЛИЧНЫЕ "НАКЛАДНЫЕ РАСХОДЫ", ЗАВИСЯЩИЕ ОТ ОТНОСИТЕЛЬНОЙ ЧАСТОТЫ
МЕЖБЛОЧНЫХ ПРОМЕЖУТКОВ; ЗНАЧИТЕЛЬНОЕ ВОЗДЕЙСТВИЕ ОКАЗЫВАЕТ ТАКЖЕ ВРЕМЯ
ПЕРЕМОТКИ. тСЕ ЭТИ ЗАВИСЯЩИЕ ОТ МАШИНЫ ОСОБЕННОСТИ ДЕЛАЮТ НЕВОЗМОЖНЫМ
ПОДГОТОВИТЬ НА МАШИННО-НЕЗАВИСИМОЙ ОСНОВЕ
%%394
СХЕМЫ, ОСУЩЕСТВЛЯЮЩИЕ ИСТИННОЕ СРАВНЕНИЕ МЕТОДОВ. ё ДРУГОЙ СТОРОНЫ, ИЗ
РИС.~85 ВСЕ ЖЕ ЯВСТВУЕТ, ЧТО, ЗА ИСКЛЮЧЕНИЕМ СБАЛАНСИРОВАННОГО СЛИЯНИЯ,
ЭФФЕКТИВНОЕ ЧИСЛО ПРОХОДОВ МОЖЕТ БЫТЬ ДОСТАТОЧНО ХОРОШО АППРОКСИМИРОВАНО
ПЛАВНЫМИ КРИВЫМИ ВИДА~$\alpha \ln S+\beta$. ёЛЕДОВАТЕЛЬНО, МЫ МОЖЕМ.
НЕПЛОХО СРАВНИВАТЬ МЕТОДЫ В ЛЮБОЙ ПРАКТИЧЕСКОЙ СИТУАЦИИ, ИЗУЧИВ ФОРМУЛЫ,
АППРОКСИМИРУЮЩИЕ ВРЕМЯ ВЫПОЛНЕНИЯ. ъОНЕЧНО, НАША ЦЕЛЬ---НАЙТИ ФОРМУЛЫ
ПРОСТЫЕ, НО ДОСТАТОЧНО РЕАЛИСТИЧНЫЕ.
\picture{ЁИС.~85. эЕСКОЛЬКО ОБМАНЧИВЫЙ СПОСОБ СРАВНЕНИЯ СХЕМ СЛИЯНИЯ.}

яОПЫТАЕМСЯ ТЕПЕРЬ ВЫВЕСТИ ТАКИЕ ФОРМУЛЫ В ТЕРМИНАХ СЛЕДУЮЩИХ ПАРАМЕТРОВ:
$$\descralign{
         N=&ЧИСЛО СОРТИРУЕМЫХ ЗАПИСЕЙ;\cr
         C=&ЧИСЛО ЛИТЕР В ЗАПИСИ; \cr
         M=& ЧИСЛО ДОСТУПНЫХ ЛИТЕРНЫХ ПОЗИЦИЙ ВНУТРЕННЕЙ ПАМЯТИ (ПРЕДПОЛАГАЕМОЕ КРАТНЫМ~$C$);\cr
      \tau=&ВРЕМЯ В СЕКУНДАХ, НУЖНОЕ ДЛЯ ТОГО, ЧТОБЫ ПРОЧИТАТЬ ИЛИ ЗАПИСАТЬ ОДНУ ЛИТЕРУ; \cr
%% 395
  \rho\tau=&ВРЕМЯ В СЕКУНДАХ ДЛЯ ПЕРЕМОТКИ ОДНОЙ ЛИТЕРЫ; \cr
\sigma\tau=&ВРЕМЯ В СЕКУНДАХ СТАРТСТОПНОЙ ЗАДЕРЖКИ; \cr
    \gamma=&ЧИСЛО ЛИТЕР В МЕЖБЛОЧНОМ ПРОМЕЖУТКЕ;\cr
    \delta=&ВРЕМЯ В СЕКУНДАХ, НУЖНОЕ ОПЕРАТОРУ ДЛЯ СНЯТИЯ И ЗАМЕНЫ ВВОДНОЙ ЛЕНТЫ; \cr
       B_i=&ЧИСЛО ЛИТЕР В БЛОКЕ НЕОТСОРТИРОВАННОГО ВВОДА; \cr
       B_o=&ЧИСЛО ЛИТЕР В БЛОКЕ ОТСОРТИРОВАННОГО ВЫВОДА.\cr
}
$$
фЛЯ \MIXT{} ИМЕЕМ $\tau=1/60\,000$, $\rho=2/5$, $\sigma=300$, $\gamma=480$.
т ПРИМЕРЕ, РАССМОТРЕННОМ ВЫШЕ, $N=100\,000$, $C=100$, $M=100\,000$,
 $B_i=B_o=5000$, $\delta=30$. юБЫЧНО ИМЕННО ЭТИ ХАРАКТЕРИСТИКИ МАШИНЫ И
ДАННЫХ РЕШАЮЩИМ ОБРАЗОМ ВЛИЯЮТ НА ВРЕМЯ СОРТИРОВКИ (ХОТЯ ВРЕМЯ ПЕРЕМОТКИ
ЧАСТО ЗАДАЕТСЯ БОЛЕЕ СЛОЖНЫМ ВЫРАЖЕНИЕМ, ЧЕМ ПРОСТО
КОЭФФИЦИЕНТОМ~$\rho$). шМЕЯ УКАЗАННЫЕ ПАРАМЕТРЫ И СХЕМУ СЛИЯНИЯ, ВЫЧИСЛИМ
ЕЩЕ НЕКОТОРЫЕ ВЕЛИЧИНЫ:
$$\descralign{
                         P=&МАКСИМАЛЬНЫЙ ПОРЯДОК СЛИЯНИЯ В СХЕМЕ; \cr
                        P'=&ЧИСЛО ЗАПИСЕЙ В ДЕРЕВЕ ВЫБОРА С ЗАМЕЩЕНИЕМ;\cr
                         S=&ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ;\cr
     \pi=\alpha\ln S+\beta=&ПРИБЛИЗИТЕЛЬНОЕ СРЕДНЕЕ ЧИСЛО ЧТЕНИЙ И ЗАПИСЕЙ КАЖДОЙ
                            ЛИТЕРЫ, НЕ СЧИТАЯ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ И
                            ОКОНЧАТЕЛЬНОГО СЛИЯНИЯ;\cr
  \pi'=\alpha'\ln S+\beta'=&ПРИБЛИЗИТЕЛЬНОЕ СРЕДНЕЕ ЧИСЛО ПЕРЕМОТОК КАЖДОЙ
                            ЛИТЕРЫ ВО ВРЕМЯ ПРОМЕЖУТОЧНЫХ ФАЗ СЛИЯНИЯ;\cr
                         B=&ЧИСЛО ЛИТЕР В БЛОКЕ В ПРОМЕЖУТОЧНЫХ ФАЗАХ СЛИЯНИЯ;\cr
\omega_i, \omega, \omega_o=&"КОЭФФИЦИЕНТЫ НАКЛАДНЫХ РАСХОДОВ"---ЭФФЕКТИВНЫЕ
                            ВРЕМЕНА, ТРЕБУЕМЫЕ ДЛЯ ЧТЕНИЯ ИЛИ ЗАПИСИ ОДНОЙ
                            ЛИТЕРЫ (С УЧЕТОМ ПРОМЕЖУТКОВ И СТАРТСТОПНОГО
                            ВРЕМЕНИ), ДЕЛЕННЫЕ НА ВРЕМЯ~$\tau$.\cr
}
$$

т ПРИМЕРАХ СХЕМЫ~A РАЗМЕРЫ БЛОКОВ И БУФЕРОВ ВЫБРАНЫ В СООТВЕТСТВИИ С ФОРМУЛОЙ
$$
B=\floor{{M\over C(2P+2)}}C,
\eqno(1)
$$
ТАК ЧТОБЫ БЛОКИ МОГЛИ БЫТЬ САМЫМИ БОЛЬШИМИ, КАКИЕ ВОЗМОЖНЫ ПРИ УСЛОВИИ
СОВМЕСТИМОСТИ СО СХЕМОЙ БУФЕРИЗАЦИИ АЛГОРИТМА~F. (ўТОБЫ ИЗБЕЖАТЬ ЗАБОТ ВО
ВРЕМЯ ПОСЛЕДНЕГО ПРОХОДА, ВЕЛИЧИНА~$P$ ДОЛЖНА БЫТЬ ДОСТАТОЧНО МАЛОЙ,
ЧТОБЫ~(1) ОБЕСПЕЧИЛО~$B\ge B_o$.) ЁАЗМЕР ДЕРЕВА ВО ВРЕМЯ ВЫБОРА С
ЗАМЕЩЕНИЕМ БУДЕТ, СЛЕДОВАТЕЛЬНО,
$$
P'=(M-2B_i-2B)/C.
\eqno(2)
$$
фЛЯ СЛУЧАЙНЫХ ДАННЫХ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ МОЖНО ОЦЕНИТЬ,
%%396
ИСПОЛЬЗУЯ РЕЗУЛЬТАТЫ П.~5.4.1, ФОРМУЛОЙ
$$
S\approx \ceil{{N\over 2P'}+{7\over 6}}.
\eqno(3)
$$
яРЕДПОЛАГАЯ, ЧТО~$B_i<B$ И ЧТО ВВОДНАЯ ЛЕНТА ВО ВРЕМЯ РАСПРЕДЕЛЕНИЯ
МОЖЕТ РАБОТАТЬ С ПОЛНОЙ СКОРОСТЬЮ (СМ.~НИЖЕ), РАСПРЕДЕЛЕНИЕ НАЧАЛЬНЫХ
ОТРЕЗКОВ ЗАЙМЕТ ПРИМЕРНО~$NC\omega_i\tau$~С, ГДЕ
$$
\omega_i=(B_i+\gamma)/B_i.
\eqno(4)
$$
тО ВРЕМЯ СЛИЯНИЯ СХЕМА БУФЕРИЗАЦИИ ДОПУСКАЕТ СОВМЕЩЕНИЕ ЧТЕНИЯ, ЗАПИСИ И
ВЫЧИСЛЕНИЙ, НО ЧАСТОЕ ПЕРЕКЛЮЧЕНИЕ ВВОДНЫХ ЛЕНТ ОЗНАЧАЕТ, ЧТО МЫ ДОЛЖНЫ
УЧЕСТЬ СТАРТСТОПНОЕ ВРЕМЯ; ПОЭТОМУ ПОЛОЖИМ
$$
\omega=(B+\gamma+\sigma)/B
\eqno(5)
$$
И ВРЕМЯ СЛИЯНИЯ ОЦЕНИМ ФОРМУЛОЙ
$$
(\pi+\rho\pi')NC\omega\tau.
\eqno(6)
$$
¤ТА ФОРМУЛА СЛЕГКА ПРЕУВЕЛИЧИВАЕТ ВРЕМЯ ПЕРЕМОТКИ, ТАК КАК
$\omega$~ВКЛЮЧАЕТ СТАРТСТОПНОЕ ВРЕМЯ, НО ДРУГИЕ СООБРАЖЕНИЯ (ТАКИЕ, КАК
ВЗАИМНАЯ БЛОКИРОВКА ПЕРЕМОТОК И ПОТЕРИ НА ЧТЕНИЕ С ТОЧКИ ЗАГРУЗКИ) ОБЫЧНО
КОМПЕНСИРУЕТ ЭТО. юКОНЧАТЕЛЬНЫЙ ПРОХОД СЛИЯНИЯ В ПРЕДПОЛОЖЕНИИ~$B_o\le B$
ОГРАНИЧИВАЕТСЯ КОЭФФИЦИЕНТОМ НАКЛАДНЫХ РАСХОДОВ
$$
\omega_o=(B_o+\gamma)/B_o.
\eqno(7)
$$
ьЫ МОЖЕМ ОЦЕНИТЬ ВРЕМЯ ВЫПОЛНЕНИЯ ПОСЛЕДНЕГО СЛИЯНИЯ И ПЕРЕМОТКИ КАК
$$
NC(1+\rho)\omega_o\tau;
$$
НА ПРАКТИКЕ ОНО МОГЛО БЫ БЫТЬ НЕСКОЛЬКО БОЛЬШЕ ИЗ-ЗА НАЛИЧИЯ НЕРАВНЫХ
БЛОКОВ (ВВОД И ВЫВОД НЕ СИНХРОНИЗОВАНЫ, КАК В АЛГОРИТМЕ~F), НО ЭТО ВРЕМЯ
БУДЕТ В ОСНОВНОМ ОДИНАКОВО ДЛЯ ВСЕХ СХЕМ СЛИЯНИЯ.

яРЕЖДЕ ЧЕМ ПЕРЕХОДИТЬ К БОЛЕЕ СПЕЦИФИЧЕСКИМ ФОРМУЛАМ ДЛЯ ОТДЕЛЬНЫХ СХЕМ,
ПОПРОБУЕМ ОБОСНОВАТЬ ДВА ИЗ СДЕЛАННЫХ ВЫШЕ ПРЕДПОЛОЖЕНИЯ.
{\medskip\narrower
\item{a)}~\emph{ьОЖЕТ ЛИ ВЫБОР С ЗАМЕЩЕНИЕМ УСПЕТЬ ЗА ВВОДНОЙ ЛЕНТОЙ?} т
ПРИМЕРЕ НА СХЕМЕ~A, ВЕРОЯТНО, МОЖЕТ, ТАК КАК ДЛЯ ВЫБОРА НОВОЙ ЗАПИСИ
ТРЕБУЕТСЯ ОКОЛО ДЕСЯТИ ИТЕРАЦИЙ ВНУТРЕННЕГО ЦИКЛА АЛГОРИТМА~5.4.1R, И МЫ
ИМЕЕМ ВРЕМЯ~$C\omega_i\tau>1667$~МКС, ЗА КОТОРОЕ СЛЕДУЕТ ВЫПОЛНИТЬ ЭТИ
ИТЕРАЦИИ. ЄЩАТЕЛЬНО ЗАПРОГРАММИРОВАВ ЦИКЛ ВЫБОРА С ЗАМЕЩЕНИЕМ, МЫ МОЖЕМ
ДОСТИГНУТЬ ЭТОГО НА МНОГИХ (НО НЕ НА ВСЕХ) МАШИНАХ. чАМЕТИМ, ЧТО ПРИ
СЛИЯНИИ ПОЛОЖЕНИЕ НЕСКОЛЬКО МЕНЕЕ КРИТИЧЕСКОЕ:
%%397
ВРЕМЯ ВЫЧИСЛЕНИЯ ДЛЯ ОДНОЙ ЗАПИСИ ПОЧТИ ВСЕГДА МЕНЬШЕ ВРЕМЕНИ РАБОТЫ ЛЕНТЫ
ПРИ $P\hbox{-ПУТЕВОМ}$ СЛИЯНИИ, ТАК КАК $P$ НЕ ОЧЕНЬ ВЕЛИКО.

\item{b)}~\emph{фОЛЖНЫ, ЛИ МЫ НА САМОМ ДЕЛЕ ВЫБИРАТЬ В КАЧЕСТВЕ~$B$
МАКСИМАЛЬНО ВОЗМОЖНЫЙ РАЗМЕР БУФЕРА, КАК В~(1)?} сОЛЬШОЙ РАЗМЕР БУФЕРА
СОКРАЩАЕТ ОТНОШЕНИЕ ИЗДЕРЖЕК~$\omega$ В~(5), НО ОН ТАКЖЕ УВЕЛИЧИВАЕТ ЧИСЛО
НАЧАЛЬНЫХ ОТРЕЗКОВ~$S$, ТАК КАК $P'$~УМЕНЬШАЕТСЯ. эЕПОСРЕДСТВЕННО НЕ
ЯСНО, КАКОЙ ФАКТОР БОЛЕЕ ВАЖЕН, ЁАССМАТРИВАЯ ВРЕМЯ СЛИЯНИЯ КАК ФУНКЦИЮ
ОТ~$x=CP'$, МОЖНО ВЫРАЗИТЬ ЕГО В ВИДЕ
$$
\left(\theta_1\ln \left({N\over x}+{7\over 6}\right)+\theta_2\right)
\left({\theta_3-x\over \theta_4-x}\right)
\eqno(8)
$$
ДЛЯ НЕКОТОРЫХ ПОДХОДЯЩИХ КОНСТАНТ~$\theta_1$, $\theta_2$, $\theta_3$,
$\theta_4$, ПРИЧЕМ~$\theta_3>\theta_4$. фИФФЕРЕНЦИРОВАНИЕ ПО~$x$
ПОКАЗЫВАЕТ, ЧТО ЕСТЬ НЕКОТОРОЕ~$N_0$, ТАКОЕ, ЧТО ДЛЯ ВСЕХ~$N\ge N_0$
НЕВЫГОДНО УВЕЛИЧИВАТЬ~$x$ ЗА СЧЕТ РАЗМЕРА БУФЕРА. т ПРИМЕРАХ, ПРИВЕДЕННЫХ
НА СХЕМЕ~A, $N_0$~ОКАЗАЛОСЬ, ГРУБО ГОВОРЯ, РАВНЫМ~$10\,000$; ПРИ
СОРТИРОВКЕ БОЛЕЕ $10\,000$~ЗАПИСЕЙ БОЛЬШОЙ РАЗМЕР БУФЕРА ПРЕДПОЧТИТЕЛЬНЕЕ.

чАМЕТИМ, ОДНАКО, ЧТО ПРИ СБАЛАНСИРОВАННОМ СЛИЯНИИ ЧИСЛО ПРОХОДОВ РЕЗКО
ИЗМЕНЯЕТСЯ, КОГДА $S$~ПРОХОДИТ ЧЕРЕЗ СТЕПЕНЬ~$P$. хСЛИ ЗАРАНЕЕ ИЗВЕСТНО
ПРИБЛИЖЕННОЕ ЗНАЧЕНИЕ~$N$, ТО РАЗМЕР БУФЕРА СЛЕДУЕТ ВЫБРАТЬ ТАК, ЧТОБЫ~$S$
С БОЛЬШОЙ ВЕРОЯТНОСТЬЮ ОКАЗАЛОСЬ НЕМНОГО МЕНЬШЕ СТЕПЕНИ~$P$. эАПРИМЕР,
РАЗМЕР БУФЕРА ДЛЯ ПЕРВОЙ СТРОКИ СХЕМЫ~A БЫЛ РАВЕН~$12\,500$, ТАК
КАК~$S=78$. ¤ТО БЫЛО ВПОЛНЕ УДОВЛЕТВОРИТЕЛЬНО, НО ЕСЛИ БЫ $S$~ОКАЗАЛОСЬ
РАВНЫМ~82, ТО БЫЛО БЫ ЗНАЧИТЕЛЬНО ЛУЧШЕ НЕМНОГО УМЕНЬШИТЬ РАЗМЕР БУФЕРА.
\medskip}

\section ЇОРМУЛЫ ДЛЯ ДЕСЯТИ ПРИМЕРОВ. тОЗВРАЩАЯСЬ К СХЕМЕ~A, ПОПЫТАЕМСЯ
ДАТЬ ФОРМУЛЫ, АППРОКСИМИРУЮЩИЕ ВРЕМЯ РАБОТЫ ДЛЯ КАЖДОГО ИЗ ДЕСЯТИ МЕТОДОВ.
т БОЛЬШИНСТВЕ СЛУЧАЕВ ОСНОВНАЯ
ФОРМУЛА
$$
N C \omega_i \tau + (\pi+\rho\pi')N C \omega \tau + (1+\rho)N C \omega_o \tau
\eqno (9)
$$
БУДЕТ ДОСТАТОЧНО ХОРОШИМ ПРИБЛИЖЕНИЕМ К СУММАРНОМУ ВРЕМЕНИ СОРТИРОВКИ,
ЕСЛИ МЫ ОПРЕДЕЛИМ ЧИСЛО ПРОМЕЖУТОЧНЫХ ПРОХОДОВ СЛИЯНИЯ~$\pi=\alpha \ln S+\beta$
И ЧИСЛО ПРОМЕЖУТОЧНЫХ ПРОХОДОВ ПЕРЕМОТКИ~$\pi'=\alpha' \ln S+\beta$. шНОГДА
НЕОБХОДИМО ВНЕСТИ В~(9) НЕКОТОРУЮ ПОПРАВКУ; СПЕЦИФИКА КАЖДОГО МЕТОДА
УЧИТЫВАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:

\example 1. ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. ЇОРМУЛЫ
$$
\pi=\ceil{\ln S/ \ln P}-1, \quad
\pi'=\ceil{\ln S / \ln P}/P
$$
МОГУТ БЫТЬ ИСПОЛЬЗОВАНЫ ДЛЯ $P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ С $2P$~ЛЕНТАМИ.
%%398

\example 2. ьНОГОФАЗНОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. ьОЖНО
ПОЛОЖИТЬ~$\pi'\approx\pi$, ТАК КАК ЗА КАЖДОЙ ФАЗОЙ ОБЫЧНО СЛЕДУЕТ
ПЕРЕМОТКА ПРИБЛИЗИТЕЛЬНО ТАКОЙ ЖЕ ДЛИНЫ, КАК ПРЕДШЕСТВУЮЩЕЕ СЛИЯНИЕ. шЗ
ТАБЛ.~5.4.2-1 ПОЛУЧАЕМ В СЛУЧАЕ ШЕСТИ ЛЕНТ ЗНАЧЕНИЯ~$\alpha=0.795$,
$\beta=0.846-2$. (тЕЛИЧИНА "$-2$" ВОЗНИКАЕТ ИЗ-ЗА ТОГО, ЧТО ЭЛЕМЕНТЫ
ТАБЛИЦЫ ВКЛЮЧАЮТ НАРЯДУ С ПРОМЕЖУТОЧНЫМИ ПРОХОДАМИ ТАКЖЕ НАЧАЛЬНЫЙ И
КОНЕЧНЫЙ.) ъ~(9) НУЖНО ДОБАВИТЬ ВРЕМЯ ПЕРЕМОТКИ ВВОДНОЙ ЛЕНТЫ ПОСЛЕ
НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ, А ИМЕННО~$\rho N C \omega_i \tau +\delta$.

\example 3. ъАСКАДНОЕ СЛИЯНИЕ С ПРЯМЫМ ЧТЕНИЕМ. ЄАБЛИЦА~5.4.3-1 ПРИВОДИТ К
ЗНАЧЕНИЯМ~$\alpha=0.773$, $\beta=0.808-2$. тРЕМЯ ПЕРЕМОТКИ СРАВНИТЕЛЬНО
ТРУДНО ОЦЕНИТЬ; ВОЗМОЖНО, ПРЕДПОЛОЖЕНИЕ~$\pi'=\pi$ ДОСТАТОЧНО ТОЧНО. ъАК
И В ПРИМЕРЕ~2, МЫ ДОЛЖНЫ ДОБАВИТЬ К~(9) ВРЕМЯ НАЧАЛЬНОЙ ПЕРЕМОТКИ.

\example 4. ьНОГОФАЗНОЕ СЛИЯНИЕ С РАСЩЕПЛЕНИЕМ ЛЕНТ. шЗ ТАБЛ.~5.4.2-5
ПОЛУЧАЕМ~$\alpha=0.752$, $\beta=1.024-2$. тРЕМЯ ПЕРЕМОТКИ ПОЧТИ ВСЕ
СОВМЕЩАЕТСЯ, ЗА ИСКЛЮЧЕНИЕМ ПЕРЕМОТКИ ПОСЛЕ НАЧАЛЬНОЙ УСТАНОВКИ~$(\rho N C
\omega_i \tau + \delta)$ И ДВУХ ФАЗ ВБЛИЗИ КОНЦА (36\% ОТ~$2\rho N C
\omega \tau$). ьЫ МОЖЕМ ТАКЖЕ ВЫЧЕСТЬ~$0.18$ ИЗ~$\beta$, ТАК КАК ПЕРВАЯ
ПОЛОВИНА ФАЗЫ СОВМЕЩАЕТСЯ С НАЧАЛЬНОЙ ПЕРЕМОТКОЙ.

\example 5. ъАСКАДНОЕ СЛИЯНИЕ С СОВМЕЩЕНИЕМ ПЕРЕМОТКИ. чДЕСЬ,
ИСПОЛЬЗУЯ ТАБЛ.~5.4.3-1 ДЛЯ~$T=5$, ПОЛУЧАЕМ~$\alpha=0.897$,
$\beta=0.800-2$. яОЧТИ ВСЯ НЕСОВМЕЩЕННАЯ ПЕРЕМОТКА ВСТРЕЧАЕТСЯ
НЕПОСРЕДСТВЕННО ПОСЛЕ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ И ПОСЛЕ КАЖДОГО
ДВУХПУТЕВОГО СЛИЯНИЯ. яОСЛЕ ТОЧНОГО НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ САМАЯ ДЛИННАЯ
ЛЕНТА СОДЕРЖИТ ПРИМЕРНО~$1/g$ ВСЕХ ДАННЫХ, ГДЕ $g$~ЕСТЬ "ОТНОШЕНИЕ РОСТА".
яОСЛЕ КАЖДОГО ДВУХПУТЕВОГО СЛИЯНИЯ ОБоЕМ ПЕРЕМОТКИ В СЛУЧАЕ ШЕСТИ ЛЕНТ
РАВЕН~$d_k d_{n-k}$ (СМ.~УПР.~5.4.3-5), И МОЖНО ПОКАЗАТЬ, ЧТО В СЛУЧАЕ
$T$~ЛЕНТ ОБоЕМ ПЕРЕМОТКИ ПОСЛЕ ДВУХПУТЕВЫХ СЛИЯНИЙ ПРИБЛИЗИТЕЛЬНО РАВЕН
$$
(2/(2T-1))(1-\cos(4\pi/(2T-1)))
$$
ОТ ВСЕГО ФАЙЛА. т НАШЕМ СЛУЧАЕ~($T=5$) ЭТО СОСТАВЛЯЕТ
${2\over 9}(1-\cos 80^\circ)\approx 0.183$~ФАЙЛА, И ЭТО ПРОИСХОДИТ В
$0.946\ln S+0.796-2$~СЛУЧАЯХ.

\example 6. ёБАЛАНСИРОВАННОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. юНО
НАПОМИНАЕТ ПРИМЕР~1, ЗА ИСКЛЮЧЕНИЕМ ТОГО, ЧТО ЗНАЧИТЕЛЬНАЯ ЧАСТЬ ПЕРЕМОТКИ
УСТРАНЯЕТСЯ. шЗМЕНЕНИЕ НАПРАВЛЕНИЯ ОТ ПРЯМОГО К ОБРАТНОМУ ВЫЗЫВАЕТ
НЕКОТОРЫЕ ЗАДЕРЖКИ, НО ОНИ НЕ СУЩЕСТВЕННЫ. ё ВЕРОЯТНОСТЬЮ~$1/2$ ПЕРЕД
ПОСЛЕДНИМ ПРОХОДОМ НУЖНА БУДЕТ ПЕРЕМОТКА, ПОЭТОМУ МОЖНО ВЗЯТЬ~$\pi'=1/(2P)$.

\example 7. ьНОГОФАЗНОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. ЄАК КАК В ЭТОМ
СЛУЧАЕ ВЫБОР С ЗАМЕЩЕНИЕМ ПОРОЖДАЕТ ОТРЕЗКИ, МЕНЯЮЩИЕ НАПРАВЛЕНИЕ
ПРИМЕРНО КАЖДЫЕ $P$~РАЗ, ТО СЛЕДУЕТ ЗАМЕНИТЬ~(3) ДРУГОЙ ФОРМУЛОЙ ДЛЯ~$S$.
фОСТАТОЧНО ХОРОШИМ ПРИБЛИЖЕНИЕМ (СМ.~УПР.~5.4.1-24)
БУДЕТ~$S=\ceil{N(3+1/P)6P'}+1$. тСЕ ВРЕМЯ ПЕРЕМОТКИ УСТРАНЯЕТСЯ, И
ТАБЛ.~5.4.2-1 ДАЕТ~$\alpha=0.863$, $\beta=0.921-2$.

\example 8. ъАСКАДНОЕ СЛИЯНИЕ С ОБРАТНЫМ ЧТЕНИЕМ. шЗ ТАБЛ.~5.4.3-1
ИМЕЕМ~$\alpha=0.897$, $\beta=0.800-2$. тРЕМЯ ПЕРЕМОТКИ ПО ЭТОЙ ТАБЛИЦЕ
МОЖНО ОЦЕНИТЬ КАК УДВОЕННУЮ РАЗНОСТЬ ["ПРОХОДЫ С КОПИРОВАНИЕМ" МИНУС
"ПРОХОДЫ БЕЗ КОПИРОВАНИЯ"] ПЛЮС~$1/(2P)$ В ТОМ СЛУЧАЕ, ЕСЛИ ПЕРЕД
ОКОНЧАТЕЛЬНЫМ СЛИЯНИЕМ НЕОБХОДИМА ПЕРЕМОТКА ДЛЯ ПОЛУЧЕНИЯ ВОЗРАСТАЮЩЕГО ПОРЯДКА.

\example 9. юСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ОБРАТНЫМ ЧТЕНИЕМ. т ЭТОМ
СЛУЧАЕ ВЫБОР С ЗАМЕЩЕНИЕМ ДОЛЖЕН МНОГО РАЗ НАЧИНАТЬСЯ И ОСТАНАВЛИВАТЬСЯ;
ЗА ОДИН РАЗ РАСПРЕДЕЛЯЕТСЯ СЕРИЯ ОТ~$P-1$ ДО~$2P-1$ ОТРЕЗКОВ (В
СРЕДНЕМ~$P$); СРЕДНЯЯ ДЛИНА ОТРЕЗКОВ, СЛЕДОВАТЕЛЬНО, ОКАЗЫВАЕТСЯ
ПРИБЛИЗИТЕЛЬНО РАВНОЙ~$P'(2P-4/3)/P$, И МОЖНО
ОЦЕНИТЬ~$S=\ceil{N/((2-4/(3P))P')}+1$. эЕКОТОРОЕ ВРЕМЯ РАСХОДУЕТСЯ НА
ПЕРЕКЛЮЧЕНИЕ ОТ СЛИЯНИЯ К РАСПРЕДЕЛЕНИЮ И ОБРАТНО; ЭТО ПРИБЛИЗИТЕЛЬНО ВРЕМЯ,
ТРЕБУЕМОЕ, ЧТОБЫ ПРОЧИТАТЬ С ВВОДНОЙ ЛЕНТЫ $P'$~ЗАПИСЕЙ,
%% 399
А ИМЕННО~$P' C \omega_i \tau$, И ЭТО ПРОИСХОДИТ ПРИМЕРНО
$S/P$~РАЗ. тРЕМЯ ПЕРЕМОТКИ И ВРЕМЯ СЛИЯНИЯ МОЖНО ОЦЕНИТЬ, КАК В ПРИМЕРЕ~6.

\example 10. юСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ПРЯМЫМ ЧТЕНИЕМ. ¤ТОТ МЕТОД
НЕЛЕГКО ПРОАНАЛИЗИРОВАТЬ, ПОСКОЛЬКУ ОКОНЧАТЕЛЬНАЯ ФАЗА "ЧИСТКИ",
ВЫПОЛНЯЕМАЯ ПОСЛЕ ИСЧЕРПАНИЯ ВВОДА, НЕ ТАК ЭФФЕКТИВНА, КАК ПРЕДЫДУЩИЕ.
яРЕНЕБРЕГАЯ ЭТИМ ТРУДНЫМ АСПЕКТОМ И ПРОСТО СЧИТАЯ, ЧТО ЕСТЬ ОДИН
ДОПОЛНИТЕЛЬНЫЙ ПРОХОД, МОЖНО ОЦЕНИТЬ ВРЕМЯ СЛИЯНИЯ, ПОЛАГАЯ~$\alpha=1/\ln
P$, $\beta=0$ И~$\pi'=\pi/P$. ЁАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ В ЭТОМ СЛУЧАЕ
НЕСКОЛЬКО ИНОЕ, ТАК КАК НЕ ИСПОЛЬЗУЕТСЯ ВЫБОР С ЗАМЕЩЕНИЕМ; МЫ
УСТАНАВЛИВАЕМ~$P'=M/C$ И~$S=\ceil{N/P'}$. яРИЛОЖИВ УСИЛИЯ, МОЖНО
СОВМЕСТИТЬ ВЫЧИСЛЕНИЕ, ЧТЕНИЕ И ЗАПИСЬ ВО ВРЕМЯ РАСПРЕДЕЛЕНИЯ, ВВОДЯ
ДОПОЛНИТЕЛЬНЫЙ КОЭФФИЦИЕНТ НАКЛАДНЫХ РАСХОДОВ ОКОЛО~$(M+2B)/M$. тРЕМЯ
ПЕРЕКЛЮЧЕНИИ РЕЖИМОВ, УПОМЯНУТОЕ В ПРИМЕРЕ~9, В НАСТОЯЩЕМ СЛУЧАЕ НЕ НУЖНО,
ТАК КАК ОНО СОВМЕЩАЕТСЯ С ПЕРЕМОТКОЙ. шТАК, ОЦЕНКОЙ ВРЕМЕНИ СОРТИРОВКИ
БУДЕТ~(9) ПЛЮС~$2B N C \omega_i \tau /M$.
\htable{ЄАБЛИЦА~1}%
{ёВОДНАЯ ТАБЛИЦА ОЦЕНОК ВРЕМЕНИ СОРТИРОВКИ}%
{\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&$#$\bskip\hfil&\hfil$#$\bskip&\hfil$#$\bskip\cr
\hbox{яРИМЕР} &  P & B & P' & S & \omega & \alpha & \beta & \alpha' & \beta' & (9) & \hbox{фОБАВКА К~(9)} & \hbox{юЦЕНКА ИТОГА} & \hbox{ЁЕАЛЬНЫЙ ИТОГ} \cr
\noalign{\hrule}
1 & 3 & 12500 & 650           &  79& 1.062& 0.910& -1.000& 0.303&  0.000& 1064&                                 & 1064 & 1076 \cr
2 & 5 &  8300 & 734           &  70& 1.094& 0.795& -1.136& 0.795& -1.136& 1010& \rho N C \omega_i \tau + \delta & 1113 & 1103 \cr
3 & 5 &  8300 & 734           &  70& 1.094& 0.773& -1.192& 0.773& -1.192&  972& \rho N C \omega_i \tau + \delta & 1075 & 1127 \cr
4 & 4 & 10000 & 700           &  73& 1.078& 0.752& -0.994& 0.000&  0.720&  844& \rho N C \omega_i \tau + \delta &  947 &  966 \cr
5 & 4 & 10000 & 700           &  73& 1.078& 0.897& -1.200& 0.173&  0.129&  972&                                 &  972 &  992 \cr
6 & 3 & 12500 & 650           &  79& 1.062& 0.910& -1.000& 0.000&  0.167&  981&                                 &  981 &  980 \cr
7 & 4 & 10000 & 700           &  79& 1.078& 0.863& -1.079& 0.000&  0.000&  922&                                 &  922 &  907 \cr
8 & 4 & 10000 & 700           &  73& 1.078& 0.897& -1.200& 0.098&  0.117&  952&                                 &  952 &  949 \cr
9 & 4 & 10000 & 700           &  87& 1.078& 0.721& -1.000& 0.000&  0.125&  846&  P'S C \omega_i \tau /P         &  874 &  928 \cr
10& 4 & 10000 & \hfill-\hfill & 100& 1.078& 0.721&  0.000& 0.180&  0.000& 1095&  2BNC\omega_i\tau/M             & 1131 & 1158 \cr
\noalign{\hrule}
}

ЄАБЛ.~1 ПОКАЗЫВАЕТ, ЧТО ОЦЕНКИ В ЭТИХ ПРИМЕРАХ НЕ СЛИШКОМ ПЛОХИ, ХОТЯ В
НЕСКОЛЬКИХ СЛУЧАЯХ РАСХОЖДЕНИЕ СОСТАВЛЯЕТ ПОРЯДКА 50~С. ЇОРМУЛЫ В
ПРИМЕРАХ~2 И~3 ПОКАЗЫВАЮТ, ЧТО КАСКАДНОЕ СЛИЯНИЕ ДОЛЖНО БЫТЬ
ПРЕДПОЧТИТЕЛЬНЕЙ МНОГОФАЗНОГО НА ШЕСТИ ЛЕНТАХ, ТЕМ НЕ МЕНЕЕ НА ПРАКТИКЕ
МНОГОФАЗНОЕ СЛИЯНИЕ ЛУЧШЕ! яРИЧИНА ЭТОГО КРОЕТСЯ В ТОМ, ЧТО ГРАФИКИ,
ПОДОБНЫЕ ИЗОБРАЖЕННЫМ НА РИС.~85 (ГДЕ ПОКАЗАН СЛУЧАЙ ПЯТИ ЛЕНТ), БЛИЖЕ К
ПРЯМЫМ ЛИНИЯМ ДЛЯ МНОГОФАЗНОГО АЛГОРИТМА; КАСКАДНЫЙ МЕТОД ПРЕВОСХОДИТ
МНОГОФАЗНЫЙ НА ШЕСТИ ЛЕНТАХ ДЛЯ~$14\le S \le 15$ И~$43\le S \le 55$ ВБЛИЗИ
"ТОЧНЫХ" КАСКАДНЫХ ЧИСЕЛ~15 И~55, НО МНОГОФАЗНОЕ РАСПРЕДЕЛЕНИЕ ПО
АЛГОРИТМУ~5.4.2D ЛУЧШЕ ИЛИ ЭКВИВАЛЕНТНО ДЛЯ ВСЕХ ОСТАЛЬНЫХ~$S\le 100$.
ъАСКАДНЫЙ МЕТОД ПРЕДПОЧТИТЕЛЬНЕЕ МНОГОФАЗНОГО ПРИ~$S\to\infty$, НО
ФАКТИЧЕСКИ~$S$ НЕ ПРИБЛИЖАЕТСЯ К~$\infty$. чАНИЖЕННАЯ ОЦЕНКА В ПРИМЕРЕ~9
ОБУСЛОВЛЕНА АНАЛОГИЧНЫМИ ОБСТОЯТЕЛЬСТВАМИ; МНОГОФАЗНАЯ СОРТИРОВКА ЛУЧШЕ
ОСЦИЛЛИРУЮЩЕЙ, НЕСМОТРЯ НА ТО ЧТО АСИМПТОТИЧЕСКАЯ ТЕОРИЯ ГОВОРИТ НАМ, ЧТО
ДЛЯ БОЛЬШИХ~$S$ ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА БУДЕТ НАИЛУЧШЕЙ.

\section эЕСКОЛЬКО ДОПОЛНИТЕЛЬНЫХ ЗАМЕЧАНИЙ. ёЕЙЧАС САМОЕ ВРЕМЯ СДЕЛАТЬ
НЕСКОЛЬКО БОЛЕЕ ИЛИ МЕНЕЕ СЛУЧАЙНЫХ НАБЛЮДЕНИЙ ОТНОСИТЕЛЬНО ЛЕНТОЧНОГО СЛИЯНИЯ:
%%400
\bye