AOP_Tom3 (1021738), страница 83

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 83)

[88[ В тексте раздела приводится иллюстрация осциллирующей сортировки Собеля в ее первозданном виде при Т = 5 и Я = 16. Дайте точное определение алгоритма, в котором эта процедура обобщается и сортируются Я = Рь начальных серий на Т = Р+1 > 3 лентах. Постарайтесь найти алгоритм, который может быть очень просто описан. 2. [24[ Если в изначальном методе Собеля Я = 6, то мы могли бы заявить, что Я = 16 и что имеется 11 фиктивных серий. Тогда фаза 3 в примере в тексте раздела поместила бы фиктивные серии Ае на Т4 и Т5, фаза 4 слила бы серии А~ на Т2 и ТЗ в Пе на Т1; фазы 5-8 не делали бы ничего, и фаза 9 породила бы Ае иа Т4. Лучше бы перемотать Т2 и ТЗ сразу после фазы 3 и затем немедленно получить Ае на Т4 с помощью трехпутевого слияния.

Покажите, как, основываясь иа этой идее, улучшить окончание алгоритма иэ упр. 1, если 8 ие является точной степенью Р. 3. [89[ Составьте таблицу, показывающую поведение алгоритма В при Т = 3, предполагая, что имеется 9 начальных серий. Покажите, что эта процедура очевидно неэффективна в одном месте, и предложите изменения в алгоритме В, позволяющие исправить этот недостаток. 4. [И [ На шаге ВЗ имеется установка отрицательного значения как в 4У,91, так и в 4[1, г3. Покажите, что одна из этих операций всегда лишняя, поскольку соответствующий элемент массива А никогда не рассматривается.

5. [М85[ Пусть Я вЂ” число начальных серий в имеющихся исходных данных для алгоритма В. При каких значениях Я не требуется нв адиев перамогпка на шаге В27 *5.4.5. Практическая реализация слияния ив лентах Теперь пришло время заняться "мелочами". В предыдущих разделах было проанализировано множество семейств схем слияния, а в данном будет рассмотрено, как они проявляются в вычислительных системах разных конфигураций при использовании НМЛ различных типов, и выполнено сравнение разных схем слияния с учетом этих характеристик. Анализ внутренней сортировки показал, что невозможно адекватно оценить эффективность того нли иного метода, просто подсчитывая число выполняемых при этом сравнений.

Аналогично нельзя правильно оценить метод внепшей сортировки, ограничившись анализом числа выполняемых проходов по данным. В этом разделе приводятся характеристики типичных НМЛ и их влияние на начальное распределение и слияние, в частности рассматривается несколько схем распределения буферов и требуемое при их реализации время счета.

Здесь также вкратце описывается структура программ — генераглоров сортировки. Как работает НМЛ. В характеристиках НМЛ, производимых разными изготовителями, имеются значительные различия. Определим для удобства гипотетический НМЛ ИХХТ, достаточно типичный для оборудования того времени, когда была написана эта книга. Рассмотрев структуру алгоритма сортировки для НМЛ ИТХТ, вы лучше поймете, как обрагцаться с другими конкретными устройствами. ИХХТ читает или записывает 800 символов на дюйм ленты при скорости протяжки 75 дюймов в секунду. Это означает, что один символ читается или записывается в течение — о мс, т. е, 1б-мкс, егти лента находится в активном состоянии. Реальные НМЛ, широко распространенные в 70-х годах, имели плотность записи в диапазоне от 200 Рис.

79. Магнитная лента с блоками переменной длины. до 1 600 символов на дюйм и скорость в диапазоне от 37э до 150 дюймов в секунду, так что их эффективная скорость в сравнении с И1ХТ изменяется в диапазоне 1/8 — 4. Еще в начале раздела о.4 отмечалось, что, конечно же, в настоящее время НМЛ являются анахронизмом. Но еще в то десятилетие, когда НМЛ были основным компонентом подсистемы внвпней памяти, мы подготовили множество примеров и упражнений, сохраняющих актуальность и по сей день. Наша концепция в дальнейшем изложении такова: значение имеет не столько получение конкретного результата, сколько изучение путей приложения теории к конкретному случаю из практики.

Я полагаю, что методолоеия имеет значителыю болыпее значение, чем феноменолоеия, поскольку принципы решения той или иной задачи остаются прежними даже при изменении технологии. Читателям, желающим максимально глубоко проникнуть в суть изложения, я рекомендовал бы мысленно перенестись в середину 70-х годов.

Предположим, что время остановилось и мы оживем в прошлом веке компьютерной эры. Одно из важных соображений, которое следует иметь в виду, состоит в том, что ленты имеют конечную длину. Каждая бобина содержит 2 400 футов ленты или меньше; следовательно, на одной бобине ленты И1ХТ есть место для максимум 23 000 000 символов и, чтобы прочесть их все, требуется около 23000000/3600000 се 6.4 мин. Если необходимо рассортировать больший файл, то обычно лучше всего рассортировывать за один раз одну полную бобину и затем сливать отдельные рассортированные бобины, чтобы избежать дополнительной работы, связанной с установкой лент.

Это означает, что число начальных серий 5, реально присутствующих в схемах слияния, которые мы изучали, никогда не будет очень большим. Мы никогда не столкнемся со случаем, когда о ) 5000, даже при очень маленьком объеме внутренней памяти, что приводит к формированию начальных серий длиной только 5 000 символов. Следовательно, формулы, дакнцне асимптотическую эффективность алгоритмов при о -+ оо, имеют, главным образом, академический интерес. Данные хранятся на ленте в виде блоков (рис.

79), и по каждой команде чтения/записи передается один блок. Блоки часто называются записями, но мы будем избегать этого термина, чтобы не путать его с записями в файле, которые участвуют в сортировке. Для многих ранних программ сортировки, написанных в 50-х годах, это различие было необязательным, так как в одном блоке хранилась одна запись; но мы увидим, что объединение нескольких записей в одном блоке на ленте обычно дает определенные преимущества. Соседние блоки разделяются междублочньсми промежуткавси длиной по 480 символов, что позволяет остановить лентопротяжный механизм нли разогнать его между отдельными командами чтения или записи. Междублочные промежутки приводят к уменьшению числа символов на одной бобине ленты, зависящему от числа символов в одном блоке (рис. 80); в той же степени уменьшается количество символов, передаваемых за секунду, так как лента движется с постоянной скоростью.

с то,ооо,ооо х в с й 1о,аоо,ооо й м 8 о о оооо 1ооо зоба зооа 4ооо Количество символов в блоке Рис. 80. Число символов нв одной бобине ленты К1ХТ как функция от размера блока. Многие устаревшие модели компьютеров имеют фиксированные и весьма малые размеры блока данных на магнитной ленте.

Например, компьютер И1Х, как описано в главе 1, всегда читает и записывает блоки по 100 слов. Таким образом, для И1Х получается примерно 500 символов на блок н 480 символов на промежуток, т. е. почти половина ленты пропадает! Сейчас большинство машин допускают работу с переменным размером блока, и поэтому ниже мы обсудим проблему выбора подходящего размера блока. В конце операции чтения или записи лента проходит с полной скоростью около 66 первых символов междублочного промежутка.

Если в это время будет инициирована следующая операция для этой же ленты, то движение ленты продолжится без перерыва. Но если следующая операция не начнется достаточно быстро, то лента остановится и к тому же потребуется некоторое время, чтобы разогнать ее до полной скорости при следующей операции. Суммарная стартстопная задержка составляет 5 мс; 2 — для остановки и 3 — для разгона (рис.

81). Таким образом, если не поддерживать непрерывное движение ленты с полной скоростью, то эффект во времени счета будет, в сущности, такой же, как если бы в междублочном промежутке было 780 символов вместо 480. Рассмотрим теперь операцию перемошки. К сожалению, обычно трудно точно охарактеризовать время, требуемое для перемотки ленты на заданное число символов и. На некоторых машинах имеется быстрая перемотка, которая применяется, только если и превышает число порядка 5 млн: для меньших значений и перемотка происходит с нормальной скоростью чтения/записи. В других НМЛ существует специальный двигатель, используемый во всех операциях перемотки; он постепенно ускоряет бобину ленты до определенного числа оборотов в минуту, а затем тормозит ее, когда подходит время остановки; действительная скорость ленты в этом случае зависит от заполненности бобины.

Мы примем для простоты, что И1ХТ требует шах(30, и/150) мс для перемотки на и символьных позиций (включая промежутки), т. е. примерно две пятых того, что требуется для нх чтения/записи. Это достаточно хорошее приближение к поведению многих реальных устройств, где отношение 12 11 и и 10 и'и 9 йб 9 3чо т и 5 и и и СЗ 0 0 1 2 з 4 5 б 7 Время от заиерщеиия оредыдущей операции до инициализации следующей комаиды коитроллира НЪ4Д Рис. В1. Вычисление времени стартстолиой задержки (Оно добавляется ко времени, затрачиваемому на чтение или зались блоков и промежутков.) времени чтения/записи ко времени перемотки обычно находится в диапазоне между 2 и 3, но оно не дает адекватной модели зффекта комбинироваиной нормальной и быстрой перемотки, имеющейся во многих других моделях НМЛ 1рис.

82). При первоиачальиой установке и/или перемотке к началу лента помещается в точку загрузки и для любой операции чтения или записи, начинающейся из етого положения, требуется дополнительно 110 мс. Если лента не находится в точке загрузки, оиа может быть прочитана в обратном направлении; 32 мс добавляется ко времени выполнения любой операции чтения/записи в обратном направлении, если она следует за операцией в прямом направлении, и к любой операции чтения/записи в прямом направлении, следующей за операцией, которая выполняется при обратном направлении движения ленты.

Характеристики

Список файлов книги