AOP_Tom3 (1021738), страница 86
Текст из файла (страница 86)
Поэтому пример на диаграмме А был построен с использованием такого метода размещения фиктивных серий (см. упр. 7). Он оказался самым быстрым из всех представленных примеров. Пример 8. Каскадное слияние с обратным чтением. Как и в примере 7, здесь участвует только 5 лент, Эта процедура соответствует алгоритму 5.4.ЗС, используя перемотку и прямое чтение, чтобы избежать однапутевого слияния (так как перемотка более чем в два раза быстрее чтения на устройствах 81ХТ).
Распределение, следовательно, та же, что и в примере б. Используя символ "~" для обозначения перемотки, изобразим эту схему так: Аг1 Ам Ам 4гд 1 1 1 1 ~44 4г5 РгргРэ Рго АдАг Аг А4д — Р,'4 Рн Ад4. Ргэ Рм Пример 9. Осцнллнруюгцая сортировка с обратным чтением. При осциллирующей сортировке с Т = 5 (алгоритм 5.4.5В) может использоваться распределение буферов, как в примерах 4, 5, 7 и 8, поскольку она выполняет четырехпутевое слияние, Однако выбор с замещением действует здесь иначе, так как непосредственно перед входом в каждую фазу слияния выводится серия длиной 700 (а не примерно 1 400), чтобы очистить внутреннюю память. Следовательно, здесь порождается 85 серий вместо 72. Некоторые ключевые шаги этого процесса таковы: Аг А1Аг А1А1 А1 А1 А1 А1 Р4Р4 Р4Р4 Р4Р4 Р4 Р4 Рд Р4 — А1в Р» А)6Р4Р4 АиР4 А)вР4А) Аи Р4 Аилл А)вР»Р) АиР» Аи А)вР4 АиР4 Аи А6Аз А16А» .4) 6А1з -'116 Р4 А)6 АиА4 АиА» АиАи А)6 Р37 А)64 Аи~ Аи» Авв Пример 10.
Осциллирующая сортировка с прямым чтением. В погледнем примере выбор с замещением не используется, так как все начальные серии должны быть одной длины. Следовательно, будет происходить внутренняя сорт)»ровна 1 000 записей (полной емкости памяти) каждый раз, когда требуется начальная серия; зто дает Я = 100. Вот некоторые ключевые шаги процесса; А) А) А) А)А» А) А) А).4» А).44 А)А» 4)1 А» 41 А» У))А» А)А» 4)А» А)А» А)А» $)А» )~)А» .41 А» )1)А» А» .436 Ам)в Эта программа оказывается самой медленной из всех частично из-за того, что в ней не используется выбор с замещением, но большей частью вследствие ее весьма нескладного конца (двухпутевое слияние).
Оценка времени выполнения. Посмотрим теперь, как вычислить приблизительное время выполнения некоторого метода сортировки с учетом характеристик используемого НМЛ И1ХТ. Можно ли предсказать результаты, изображенные на диаграмме А, не выполняя детального моделирования? А) А) А» А)А»А)6 А4 А» Аи 1)4Аи А) А) А» А) А4 А) А» )~) А» А) А4 А) А»А)вА64 )~) А» А) 6.464 )ЗД„АиА64 41)»7»А)в 464 4144416 Ав» !о 9 ~ в 6 Сбалансированная (Т = 6) Касяирвав (т=5) МноввРвзная (Т = 5) он нрт и (т 5) И 5 о 4 н $ 2 я р' 1 О 1 2 5 10 20 50 1ОО 200 500 1000 2000 5000 Начальныс ссркн, Х Рис.
80. Несколько обманчивый способ сравнения схем слияния. рт — время в секундах для перемотки в пересчете на один символ, пт — время в секундах стартстопной задержки, 7 --. число символов в междублочном промежутке, Один способ, который традиционно использовался для сравнения различных схем слияния, состоит в том, чтобы совместить графики, подобные представленным на рис.
70, 74 и 78. На этих графиках изображено аффективное число проходов по данным как функция от числа начальных серий в предположении, что все начальные серии имеют примерно равную длину (рис. 85). Но зто не позволяет выполнить аде- кватное сравнение, потому что, как мы видели, разные методы приводят к различ- ному числу начальных серий; кроме того, имеются различные накладные расходы, зависящие от относительной частоты междублочных промежутков; значительное воздействие оказывает также время перемотки.
Все зти зависящие от конкретного оборудования особенности затрудняют использование машинно-независимой мето- дики истинного сравнения методов слияния. С другой стороны, из рис. 85 все же явствует, что за исключением сбалансированного слияния эффективное числа про- ходов может быть достаточно хорошо аппроксимировано плавными кривыми вида о!п5+(). Следовательно, можно неплохо сравнивать методы в любой практической ситуации, проанализировав формулы, аппроксимирующие время выполнения.
Ко- нечно, наша цель — найти формулы простые, но достаточно близкие к реальности. Попытаемся теперь вывести такие формулы в терминах следующих параметров: )в' — число сортируемых записей, С вЂ” число символов в записи, М -- объем доступного пространства в оперативной памяти (символов; предполагается кратным С) т — время в секундах, нужное для того, чтобы прочитать илн записать один символ, б — время в секуцдах, необходимое оператору для снятия и замены вводной ленты, В; — число символов в блоке нерассортированного ввода, „— число символов в блоке рассортированного вывода.
Для М1ХТ имеем г = 1/60000, р = 2/5, и = 300, Т = 480. В примере, рассмотренном выше, Х = 100000. С = 100, ЛХ = 100000, б = 30, В, = В, = 5000. Обычно именно эти характеристики оборудования н данных решшощим образом влияют на время сортировки (хотя время перемотки часто задается более сложным выражением, чем просто коэффициентом р). 11мея указанные параметры и схему слияния, вычислим еще некоторые величины: максимальный порядок слияния в схеме, число записей в дереве выбора с замещением, число начальных серий, х = о!п5+11 приблизительное среднее число чтений и записей каждого сим- вола, не считая начального распределения и окончательного слияния, х' = о'!пВ+,3' приблизительное среднее число перемоток каждого символа во время промежуточных фаз слияния, число символов в блоке в промежуточных фазах слияния, "коэффициенты накладных расходов" — действительное вре- мя, необходимое для чтения или записи в пересчете на один символ (с учетом промежутков и стартстопного времени), отне- сенное к общему времени г.
В В примерах диаграммы А размеры блоков и буферов выбраны в соответствии с формулой С(2Р+ 2) Р' = (л1 — 2В, — 2В)/С. (г) Для случайных данных числа начальных серий можно оценить формулой ! 2Р' 61' (3) опираясь на результаты раздела 5.4.1. Предполагая, что В; с В и что вводная лента во время распределения может работать с полной скоростью (см. ниже), распреде- ление начальных серий займет примерно ХСы,т с, где (4) ы, = (В; + з)/Вь чтобы блоки могли быть максимально большими при условии совместимости со схе- мой буферизации алгоритма г .
(Во избежание ненужных забот во время последнего прохода величина Р должна быть достаточно малой, чтобы (1) обеспечило В > В,.) Размер дерева во время выбора с замещением будет, следовательно, таковым: Во время слияния схема буферизации допускает совмещение чтения, записи н вычислений, но при частом переключении вводных лент необходимо учитывать и стартстопное время; поэтому положим, что = (В + 7+ о)/В, (5) и время слияния оценим формулой (зг + рк')ХСыг. (6) В этой формуле слегка завышена оценка времени перемотки, так как в нее включено стартстопное время, но другие факторы (такие, как взаимная блокировка пере- моток и потери времени на чтение с точки загрузки) обычно компенсируют это.
Окончательный проход слияния в предположении, что В, < В, ограничивается коэффициентом накладных расходов ы, = (В, + у)/В,. (7) Можно оценить время выполнения последнего слияния и перемотки как пС(1+ р)ы,т; на практике оно могло бы быть несколько больше из-за наличия неравных блоков (ввод и вывод не синхронизированы, как в алгоритме Г), но это время будет, в основном, одинаково для всех схем слияния.
Прежде чем переходить к более специфическим формулам для отдельных схем, попробуем обосновать два из сделанных выше предположений. а) Может ли сиспзема, реализующая выбор с замещением "поспеть" за вводной лентойр В примере на диаграмме А, вероятно, может, так как для выбора новой записи требуется около десяти итераций внутреннего цикла алгоритма 5.4.1В и в нашем распоряжении время Сы,т > 1667 мкс, за которое следует выполнить эти итерации.
Тщательно запрограммировав цикл выбора с замещением, можно достичь этого на многих компьютерах (что и происходило даже в 70-х годах). Заметим, что при слиянии положение несколько менее критическое: время вычисления для одной записи почти всегда меньше времени работы НМЛ при Р-путевом слиянии, так как Р не очень велико, Ь) Должны ли мы на самом деле выбирать в качестве В максимально возможный размер буфера, как задано в формуле (1)7 Выбрав большой размер буфера, можно сократить отношение издержек ьг в (5), но прн этом увеличится чнгло начальных серий Я, так как Р' уменьшается. Сразу и не скажешь, какой фактор важнее. Рассматривая время слияния как функцию от х = СР', можно выразить его в виде (8) для некоторых подходящих констант б„ую дз, В4. причем Вз > 84.
Дифференцирование по х показывает, что есть некоторое Ага, такое, что для всех Х > Аоо невыгодно увеличивать х за счет размера буфера. В примерах, приведенных на диаграмме А, А?а оказалось, грубо говоря, равным 10 000: при сортировке более 10 000 записей большой размер буфера предпочтительнее. Заметим, однако, что при сбалансированном слиянии число проходов резко изменяется, когда Я "проходит" через степень Р. Егли заранее известно приближенное значение Х, то размер буфера следует выбрать таким, чтобы Я с большой вероятностью оказалось немного меньше степени Р. Например, размер буфера для первого графика диаграммы Л был равен 12 500, так как Я = 78. Это было вполне удовлетворительно, но если бы Я оказалось равным 82, было бы значительно лучше немного уменьшить размер буфера. Формулы для десяти примеров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
