\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