Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 89
Текст из файла (страница 89)
Фактически сбалансированное слияние с шестью лентами, если оно тщательно запрограммировано, может сортировать три бабины до момента окончательного слияния. Для слияния относительно большого числа отдельно рассортированных бобин лучше всего использовать дерево слияния с минимальной длиной пути (ср. с разделом 5А.4). Этот подход впервые был реализован Э. Г. Френдом (Е. Н. Кг!епб) [,УАСМ 3 (1956), 166-167) и затем — — У.
Г. Буржем ('1г'. Н. В1пйе) (1пгагшайап аЫ Сопгго! 1 (1958), 181-197], которые отметилн, что оптимальный способ слияния серий данных (возможно, неравных ллнн) получается путем построения дерева с минимальной взвешенной длиной пути и использования длины серий в качестве весов (см, разделы 2.3А.5 и 5.4.9), если пренебречь временем установки лент. Но файлы, занимающие несколько бобин, вероятно, следует хранить на дисках нли другом запоминающем устройстве большой емкости, а не на лентах.
° В нашем обсуждении мы, не особенно задумываясь, предполагали, что имеется возможность испольэовать непосредственно инструкции ввода-вывода и чза никакой сложный системный интерфейс не мешает нам использовать ленты с такой эффективностью, на какую рассчитывали конструкторы оборудования. Эти идеальные предположения позволили нам проникнуть в суть проблем слияния, и они могут дать некоторый подход к разработке соответствующих операционных систем. Однако следует понимать, что мультипрограммирование и мультипроцессирование могут значительно усложнить ситуацию. ° Обсуждаемые нами вопросы впервые были рассмотрены в работах Е. Н. Ег!епб, .!АСМ 3 (1956), 134-168; %. ЕоЬегЪ|ег, Е(е(гпоп!всЬе .0агепгегагЬейипй Б (1960), 28-44, и М.
А. Ооесх, 11!8!га! Сашригег Нявг'в Напхав)г (Хезг Ъогйо Мсбгак-Н10, 1967), 1.292-1.320. Резюме. Мы можем следующим образом вкратце подытожить все, что узнали о сравнении различных схем слияния. Теорема А. Трудно решить„какая схема слияния является наилучшей в конкретной ситуации. $ Примеры, которые мы видели на диаграмме А, показывают, как 100 000 записей по 100 символов (или миллион записей по 10 символов), расположенных в случайном порядке, могли бы быть рассортированы с помощью шести лент при достаточно реалистических предположениях. Эти данные занимюот около половины ленты и могут быть рассортированы приблизительно за 15-19 мин при использовании НМЛ М1ХТ.
Однако существующее ленточное оборудование силыю различается по возможностям, и время выполнения такой работы на разных машинах изменяется в диапазоне приблизительно от 4 мин до 2 ч, В наших примерах около 3 мин расходуется на начальное распределение серий и внутреннюю сортировку, около 4-' мин — на окончательное слияние и перемотку выводной ленты н приблизительно 71-111 мин — на промежуточные стадии слияния.
2 2 Для шести лент, которые нельзя читать в обратном направлении, наилучшим методом сортировки прн наших предположениях было многафазное слияние с рас- щеплением лент (пример 4), а для НМЛ, допускающих обратное чтение, наилучшим оказался многофазный метод с обратным чтением со сложным размещением фиктивных серий (пример 7). Осцнллирующая сортировка (пример 9) занимает в нашей табели о рангах второе место. В обоих случаях каскадное слияние является более простым и лишь незначительно медленнее (примеры 5 и 8). В случае прямого чтения обычное сбалансированное слияние (пример 1) оказалось удивительно эффективным, частично из-за удачного сочетания параметров в данном конкретном примере, а частично из-за того, что прн этом тратится сравнительно мало времени на перемотку.
Положение несколько изменилось бы, если бы в нашем распоряжении было другое число НМЛ. Генераторы сортировки. В условиях болыпого разнообразия характеристик данных и оборудования почти невозможно написать единственную программу внешней сортировки, которая была бы удовлетворительной в подавляющем большинстве случаев. Также весьма трудно создать программу, которая в реальных условиях эффективно работает с лентами. Следовательно, разработка программного обеспечения сортировки — самостоятельная задача, требующая большой работы.
Генератор сортировки — - это программа, которая, ск.новываясь на параметрах, описывающих формат данных и конфигурацию оборудования, порождает машинную программу, специально приспособленную к конкретному применению сортировки. Подобная программа часто связана с такими языками высокого уровня, как СОВОЕ и РЬ/1, или она может быть написана как набор макроопределений для использования совместно с макроассемблером. Одной из особенностей, обычно обеспечиваемых генератором сортировки, является возможность вставлять собственные команды — особые инструкции, которые должны включатся в первый и последний проходы программы сортировки.
Собственные команды первого прохода обычно используются для некоторой коррекции исходных записей, часто сокращая их или незначительно удлиняя, чтобы привести к форме, более простой для сортировки. Пусть, например, исходные записи должны быть рассортированы по девятисимвольному ключу, изображающему дату в формате "месяц-день-год": 301.041776 ОСТ311517 ИОЧ051605 ЛП.141789 МОЧ071917. Трехбуквенные коды месяцев можно найти в таблице и заменить числами, причем наиболее значащие поля могут быть помещены слева: 17760704 15171031 16051105 17890714 19171107. Это уменьшает длину записей и упрощает последующие сравнения.
(Код ключей мог бы быть сделан даже более компактным.) Собственные команды последнего прохода могут использоваться лля восстановления исходного формата и(или для внесения других желательных изменений в файл, и/или для вычисления какой- либо функции от выводных записей. Алгоритмы слияния, которые мы изучили, организованы таким образом, что последний проход легко отличить от остальных фаз слияния. Заметим, что если имеются собственные команды, то должно быть, по крайней мере, два прохода по файлу, даже если он первоначально находился в нуж- ном порядке. Собственные команды, изменяющие размер записей, могут затруднить совмещение некоторых операций ввода-вывода в осциллирующей сортировке.
Генераторы сортировки заботятся о таких системных деталях, как соглашения о метках на лентах; они также часто обеспечивают подсчет контрольной суммы или иные проверки того, что никакая часть файла не пропала и не изменилась. Иногда имеются средства для остановки сортировки в удобных местах и возобновления ее позднее. Самые высококыественные генераторы позволяют записям иметь динамически меняющиеся длины (см.
Р. 3. Ч~а?сэ, САСМ 6 (1963), 267 — 272). *Слияние с меньшим числом буферов. Мы видели, что 2Р+ 2 буферов достаточно для поддержания бьк:трого движения лент в течение Р-путевого слияния. В завершение этого раздела проведем математический анализ времени слияния в том случае, когда в нашем распоряжении имеется меньше 2Р+ 2 буферов.
Очевидно, что желательно иметь два буфера вывода — можно будет выполнять запись из одного буфера, образуя в это же время следующий блок вьшода в другом. Поэтому можно вообще не рассматривать вопрос вывода и заняться только вводом. Допустим, имеется Р + Я буферов ввода, где 1 < Я < Р. Воспользуемся для описания нашей ситуации моделью, предложенной в работе? .
3. %оойгшп, ?ВМ Яуэ(ешл,?. 9 (1970), 118-144. Чтение одного блока ленты занимает одну единицу времени. Обозначим через ре вероятность того, что в течение этого времени ни один из буферов ввода не станет пустым, через р1 — что один буфер станет пустым, через р>т — что два или больше буферов станут пустыми и т. д. По завершении чтения ленты мы оказываемся в одном из („? + 1 состояний. Состолппе О. Я буферов пусты. Мы начинаем читать блок подходящего файла в один из них, используя метод прогнозирования, описанный ранее в этом разделе.
Через один такт времени мы переходим в состояние 1 с вероятностью ре, в противном случае остаемся в состоянии О. Соспюлиие 1. Я вЂ” 1 буферов пусты. Начинаем выполнять чтение в один из них, предсказывая подходящий файл. Через один такт времени переходим в состояние 2 с вероятностью ре, в состояние 1 с вероятностью р~ и в состояние О с вероятностью р т. Сосптояиие Я вЂ” 1, Один буфер пуст. Начинаем выполнять чтение в него, предсказывая подходящий файл. Через один такт времени переходим в состояние Я с вероятностью ре, в состояние (~ — 1 с вероятностью рм ..., в состояние 1 с вероятностью рг7 1 и в состояние О с вероятностью рйо.
Соспюанпе Я. Все буфера заполнены. Чтение лент останавливается в среднем па р тактов времени, н затем мы переходим в состояние () — 1. Начинаем с состояния О. Модель этой ситуации соответствует марковскому процессу (см. упр. 2.3.4.2-26), который можно проанализировать с помощью производящих функций следующим интересным способом. Пусть г — произвольный параметр, и предположим, что каждый раз, когда мы решаем осуществлять чтение с ленты, делаем это с вероятностью г, а с вероятностью 1- х завершаем выполнение алгоритма. Пусть ро(г) = 2 „>в а(1о~х" (1 — -) — среднее число появлений в этом процессе состояния (7'; отсюда следует, что а~,'З1 — это среднее число появлений состояния (,), если было прочитано ровно и блоков. Тогда и + оц'ОР— среднее суммарное время, затраченное на ввод и вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
