1. [22] В тексте раздела, приводится иллюстрадия осциллирующей сортировки Собеля в ее первозданном виде при Т = 5 и 5 = 16. Дайте точное определение алгоритма, в котором эта процедура обобщается и сортируются 5 = начальных серий на Т = Р+1 > 3 лентах. Постарайтесь найти алгоритм, который может быть очень просто описан.

2. [24] Если в изначальном методе Собеля 5 = 6, то мы могли бы заявить, что 5 = 16 и что имеется 11 фиктивных серий. Тогда фаза 3 в примере в тексте раздела поместила бы фиктивные серии Ао на Т4 и Т5, фаза 4 слила бы серии Ai на Т2 и ТЗ в Di на Т1; фазы 5-8 не делали бы ничего, и фаза 9 породила бы Аб на Т4. Лучше бы перемотать Т2 и ТЗ сразу после фазы 3 и затем немедленно получить Аб на Т4 с помощью трехпутевого слияния.

Покажите, как, основываясь на этой идее, улучшить окончание алгоритма из упр. 1, если S не является точной степенью Р.

> 3. [29] Составьте таблицу, показывающую поведение алгоритма В при Г = 3, предполагая, что имеется 9 начальных серий. Покажите, что эта процедура очевидно неэффективна в одном месте, и предложите изменения в алгоритме В, позволяющие исправить этот недостаток.

4. [21 ] На шаге ВЗ имеется установка отрицательного значения как в А U, ql, так и в A[Z,г]. Покажите, что одна из этих операций всегда лишняя, поскольку соответствующий элемент массива А никогда не рассматривается.

5. [М25] Пусть S - число начальных серий в имеющихся исходных данных для алгоритма В. При каких значениях S не требуется ни одной перемотки на шаге В2?

*5.4.6. Практическая реализация слияния на лентах

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

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

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

Междублочные Точка загрузки / промежутки \

Ф 4- Д.

Рис. 79. Магнитная лента с блоками переменной длины.

до 1 600 символов на дюйм и скорость в диапазоне от 37 до 150 дюймов в секунду, так что их эффективная скорость в сравнении с MIXT изменяется в диапазоне 1/8-4.

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

Одно из важных соображений, которое следует иметь в виду, состоит в том, что ленты имеют конечную длину. Каждая бобина содержит 2 400 футов ленты или меньше; следовательно, на одной бобине ленты MIXT есть место для максимум 23 ООО ООО си-мволов и, чтобы прочесть их все, требуется около 23000000/3600000 и 6.4 мин. Если необходимо рассортировать больший файл, то обычно лучше всего рассортировывать за один раз одну полную бобину и затем сливать отдельные рассортированные бобины, чтобы избежать дополнительной работы, связанной с установкой лент. Это означает, что число начальных серий 5, реально присутствующих в схемах слияния, которые мы изучали, никогда не будет очень большим. Мы никогда не столкнемся со случаем, когда 5 > 5000, даже при очень маленьком объеме внутренней памяти, что приводит к формированию начальных серий длиной только 5 ООО символов. Следовательно, формулы, дающие асимптотическую эффективность алгоритмов при S -¥ оо, имеют, главным образом, академический интерес.

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

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

о ч о

20,000,000

10,000,000

1000 2000 3000 4000

Количество символов в блоке

Рис. 80. Число символов на одной бобине ленты MIXT как функция от размера блока.

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

В конце операции чтения или записи лента проходит с полной скоростью около 66 первых символов междублочного промежутка. Если в это время будет инициирована следующая операция для этой же ленты, то движение ленты продолжится без перерыва. Но если следующая операция не начнется достаточно быстро, то лента остановится и к тому же потребуется некоторое время, чтобы разогнать ее до полной скорости при следующей операции. Суммарная стартстопная задержка составляет 5 мс: 2 - для остановки и 3 - для разгона (рис. 81). Таким образом, если не поддерживать непрерывное движение ленты с полной скоростью, то эффект во времени счета будет, в сущности, такой же, как если бы в междублочном промежутке было 780 символов вместо 480.

Рассмотрим теперь операцию перемотки. К сожалению, обычно трудно точно охарактеризовать время, требуемое для перемотки ленты на заданное число символов п. На некоторых машинах имеется быстрая перемотка, которая применяется, только если п превышает число порядка 5 млн; для меньших значений п перемотка происходит с нормальной скоростью чтения/записи. В других НМЛ существует специальный двигатель, используемый во всех операциях перемотки; он постепенно ускоряет бобину ленты до определенного числа оборотов в минуту, а затем тормозит ее, когда подходит время остановки; действительная скорость ленты в этом случае зависит от заполненности бобины. Мы примем для простоты, что MIXT требует тах(30, п/150) мс для перемотки на п символьных позиций (включая промежутки), т. е. примерно две пятых того, что требуется для их чтения/записи. Это достаточно хорошее приближение к поведению многих реальных устройств, где отношение