Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 84
Текст из файла (страница 84)
1, если 5' не является точной степенью Р. 3. [ЯУ[ Составьте таблицу, показывающую поведение алгоритма В при Т = 3, предполагая, что имеется 9 начальнмх серий. Покажите, что эта процедура очевидно неэффективна в одном месте, и предложите изменении в алгоритме В, позволяющие исправить этот недостаток. 4.
[21[ На шаге ВЗ имеется установка отрицательного значения как в АУ,43, так и в А Б, г 1. Покажите, что одна из этих операций жегда лишняя, поскольку соответствующий элемент массива А никогда не рассматривается. 5. [5425[ Пусть Я вЂ” число начальных серий в имевшихся исходных данных для алгоритма В. При каких значениях Я не требуется на одное перемотки на шаге В27 эб.й.б.
Практическая реализация слияния на лентах Теперь пришло время заняться "мелочами". В предыдущих разделах было проанализировано множество семейств схем слияния, а в данном будет рассмотрено, как онн проявляются в вычислительных системах разных конфигураций при использовании НМЛ различных типов, и выполнено сравнение разных схем слияния с учетом этих характеристик. Анализ внутренней сортировки показал, что невозможно адекватно оценить эффективность того или иного метода, просто подсчитывая число выполняемых при этом сравнений. Аналогично нельзя правильно оценить метод внешней сортировки, ограничившись анализом числа выполняемых проходов по данным. В этом разделе приводятся характеристики типичных НМЛ и их влияние на начальное распределение и слияние, в частности рассматривается несколько схем распределения буферов и требуемое при их реализации время счета.
Здесь также вкратце описывается структура программ — генеранюров сорнэирооки. Кек работает НМЛ. В характеристиках НМЛ, производимых разными изготовителями, имеются значительные различия. Определим для удобства гипотетический НМЛ И1ХТ, достаточно типичный для оборудования того времени, когда была написана эта книга, Рассмотрев структуру алгоритма сортировки для НМЛ ИХХТ, вы лучше поймете, как обращаться с другими конкретными устройствами. ИТХТ читает или записывает 600 символов на дюйм ленты при скорости протяжки 75 дюймов в секунду. Это означает, что один символ читается нли записывается в течение ~~ мс, т.
е. 165змкс, если лента находится в активном состоянии. Реальные НМЛ, широко распространенные в 70-х годах, имели плотность записи в диапазоне от 200 Рис. 79. Магнитная лента с блоками переменной длины. до 1 600 символов на дюйм и скорость в диапазоне от 37-' до 150 дюймов в секунду, так что их аффективная скорость в сравнении с 81ХТ изменяется в диапазоне 1/8 — 4. Еще в начале раздела 5.4 отмечалось, что, конечно же, в настоящее время НМЛ являются анахронизмом. Но еще в то десятилетие, когда НМЛ были основным компонентом подсистемы внешней памяти, мы подготовили множество примеров и упражнений, сохраняющих актуальность н по сей день.
Наша концепция в дальнейшем изложении такова: значение имеет не столько получение конкретного резучьтата, сколько изучение путей приложения теории к конкретному случаю из практики. Я полагаю, что методология имеет значительно большее значение, чем феноменология, поскольку принципы решения той или иной задачи остаются прежними даже при изменении технологии.
Читателям, желающим максимально глубоко проникнуть в суть изложения, я рекомендовал бы мысленно перенестись в середину 70-х годов. Предположим, что время остановилось и мм живем о прошлом веке компьютерной эры. Одно из важных соображений, которое следует иметь в виду, состоит в том, что ленты имеют конечную длину. Каждая бобина содержит 2 400 футов ленты или меньше; следовательно, на одной бобине ленты И1ХТ есть место для максимум 23 000 000 символов и, чтобы прочесть их все, требуется около 23000000/3600000 т 6.4 мин. Если необходимо рассортировать больший фай.к, то обычно лучше всего рассортировывать за один раз одну полную бобину и затем сливать отдельные рассортированные бобины, чтобы избежать дополнительной работы, связанной с установкой лент.
Это означает, что число начальных серий Я, реально присутствующих в схемах слияния, которые мы кзучали, никогда не будет очень большим. Мы никогда не столкнемся со случаем, когда Я > 5000, даже при очень маленьком объеме внутренней памяти, что приводит к формированию начальных серий длиной только 5 000 символов. Следовательно, формулы, дающие асимптотическую зффективность алгоритмов при Я -+ сю, имеют, главным образом, академический интерес. Данные хранятся на ленте в виде блоков (рис. 79), и по каждой команде чтения/записи передастся один блок. Блоки часто называются зишсями, но мы будем избегать етого термина, чтобы не путать его с записями в файле, которые участвуют в сортировке.
Для многих ранних программ сортировки, написанных в 50-х годах, зто различие было необязательным, так квк в одном блоке хранилась одна запись; но мы увидим, что объединение нескочьких записей в одном блоке на ленте обычно дает определенные преимущества.
Соседние блоки разделяются междублочнмми промежутками длиной по 480 символов, что позволяет остановить лентопротяжный механизм или разогнать сто между отдельными командами чтения или записи. Междублочные промежутки приводят к уменыпению числа символов иа одной бобине ленты, зависящему от числа символов в одном блоке (рис. 80); в той же степени уменьшается количество символов, передаваемых за секунду, так как лента движется с пск,"тоянной скоростью. 20,000,000 о л Ф о о 1О,ОООООО е й 8 о о ОООО 1000 2000 ЗООО 4000 Количество символов в блоке Рис. 80. Число символов на одной бобине ленты ИХХТ квк функция от размера блока. Многие устаревшие модели компьютеров имеют фиксированные и весьма малые размеры блока данных на магнитной ленте. Например, компьютер И1Х, как описано в главе 1, всегда читает и записывает блоки по 100 слов.
Таким образом, для И1Х получается примерно 500 символов на блок и 480 символов на промежуток, т. е. почти половина ленты пропадает! Сейчас большинство машин допускают работу с переменным размером блока, и поэтому ниже мы обсудим проблему выбора подходящего размера блока. В конце операции чтения или записи лента проходит с полной скоростью около 66 первых символов междублочного промежутка. Если в это время будет инициирована следующая операция для этой же ленты, то движение ленты продолжится без перерыва.
Но если следующая операция не начнется достаточно быстро, то лента остановится и к тому же потребуется некоторое время, чтобы разогнать ее до полной скорости при следующей операции. Суммарная стартстопная задержка составляет 5 мс: 2 — для остановки и 3 — для разгона (рис, 81). Таким образом, если не поддерживать непрерывное движение ленты с полной скоростью, то эффект во времени счета будет, в сущности, такой же, как если бы в междублочном промежутке было 780 символов вместо 480. Рассмотрим теперь операцию парамошин. К сожалению, обычно трудно точно охарактеризовать время, требуемое для перемотки ленты на заданное число символов и.
На некоторых машинах имеется быстрая перемотка, которая применяется, только если и превышает число порядка б млн; для меньших значений и перемотка происходит с нормальной скоростью чтения/записи. В других НМЛ существует специальный двигатель, используемый во всех операциях перемотки; он постепенно ускоряет бобину ленты до определенного числа оборотов в минуту, а затем тормозит ее„когда подходит время остановки; действительная скорость ленты в этом случае зависит от заполненности бобины. Мы примем для простоты, что И1ХТ требует шах(30, и/150) мс для перемотки на и символьных позиций (включая промежутки), т. е, примерно две пятых того, что требуется для их чтения/записи. Это достаточно хорошее приближение к поведению многих реальных устройств, где отношение Гз !1 10 к ям 3 й к 3 й„"0 $ о 3 Кй 2 й 0 0 1 2 3 4 Ь 6 7 Время от зазершеккя цредыдужей окерацкк до инициализации цеедуюшей команды коктроллера НЬ1Л Рис.
81. Вычисление времени стартстопной задержки. 10но добавляется ко времени, затрачиваемому на чтение нли запись блоков и промежутков.) времени чтения/записи ко времени перемотки обычно находится в диапазоне между 2 и 3, но оно не дает адекватной модели аффекта комбинированной нормальной и быстрой перемотки, имеющейся во многих других моделях НМЛ (рис, 82). При первоначальной установке и/или перемотке к началу лента помещается в точку загрузки и дзя любой операции чтения или записи, начинающейся из етого положения, требуется дополнительно 110 мс. Если лента не находится в точке загрузки, она может быть прочитана в обратном направлении; 32 мс добавляется ко времени выполнения любой операции чтения~записи в обратном направлении, если она следует за операцией в прямом направлении, и к любой операции чтения/записи в прямом направлении, следующей за операцией, которая выполняется при обратном направлении движения ленты. 0 0 23,000,000 5,000,000 15„000,000 Число скмеолоз от точки загрузки Рис.
82. Приблизительное время счета при двух обычно используемых методах перемотки. Снова о слиянии. Обратимся вновь к процессу Р-путевого слияния, сосредоточив на сей раз внимание на функционировании устройств ввода и вывода. Будем считать, что для вводных н выводного файлов используется Р+ 1 НЫЛ. Наша цель — максимально совместить операции ввода-вывода одну с другой и со счетом по программе так, чтобы минимизировать общее время слияния.
Поучительно рассмотреть следующий частный случай, в котором на возможную степень одновременности наложены серьезные ограничения. Предпсаюжнм, что а) в каждый момент времени можно вьтолнить запись не более чем на одну ленту; Ь) в каждый момент времени можно читать не более чем с одной ленты; с) чтение, запись и вычисления могут происходить одновременно, только если операции чтения и записи были начаты одновременно. Оказывается, что даже при таких ограничениях достаточно иметь 2Р буферов ввода и 2 буфера вывода для поддержки, в сущности, максимальной скорости движения лент, если только мы имеем дело не с очень медленным компьютером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
