Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 87
Текст из файла (страница 87)
М а~ма В примерах диаграммы А размеры блоков и буферов выбраны в соответствии с формулой С(2Р+ 2) чтобы блоки моглн быть максимально большими при условии совместимости со схе- мой буферизации алгоритма г. (Во избежание ненужных забот во время последнего прохода величина Р должна быть достаточно малой, чтобы (1) обеспечило В > В,.) Размер дерева во время выбора с замененном будет, следовательно, таковым: Р' = (М вЂ” 2В; — 2В)/С. (2) Для случайных данных число начальных серий можно оценить формулой ап = (В'+ у)/В опираясь на результаты раздела 5А.1. Предполагая, что В, ( В н что вводная лента во время распределения может работать с полной скоростью (см.
ниже), распреде- ление начальных серий займет примерно ХСьят с, где Во время слияния схема буферизации допускает совмещение чтения, записи н вычислений, но при частом переключении вводных лент необходимо учитывать и стартстопиое время; поэтому положим, что ы = (В + 7 + и)/В, и время слияния оценим формулой (б) В этой формуле слегка завышена оценка времени перемотки, так как в нее включено глвртстопное время, но другие факторы (такие, как взаимная блокировка пере- моток и потери времени на чтение с точки загрузки) обычно компенсируют это. Окончательный проход слияния в предположении, что В, < В, ограничивается коэффициентом накладных расходов Ъ = (В.
+ 7)/В' (7) Можно оценить время выполнения последнего слияния и перемотки как пС(1+ р)ы,т; на практике оно могло бы быть нескозько больше из-за наличия неравных блоков (ввод и вывод не синхронизированы, как в алгоритме Е), но это время будет, в основном, одинаково для всех схем слияния. Прежде чем переходить к более специфическим формулам для отдельных схем, попробуем обосновать два из сделанных выше предположений. а) Может ли система, реализрющал выбор с замещением "поспеть" за вводной лентойу В примере на диаграмме А, вероятно, может, так как для выбора новой записи требуется около десяти итераций внутреннего цикла алгоритма 5.4.1К и в нашем распоряжении время Сы;г > 1бб7 мкс, за которое следует выполнить эти итерации.
Тщатачьно запрограммировав цикл выбора с замещением, можно достичь этого на многих компьютерах (что и происходило даже в 70-х годах). Заметим, что прн слиянии положение несколько менее критическое: время вычисления для одной записи почти всегда меныпе времени работы НМЛ при Р-путевом слиянии, так как Р нв очень велико. Ь) Долзюны ли мы на самом деле выбирать в качестве В максимально возмооюный размер брфера, как задано в формуле (1)7 Выбрав большой размер буфера, можно сократить отношение издержек ы в (б), но при этом увеличится число начальных серий Я, так как Р' уменьшается. Сразу н не скажешь, какой фактор важнее. Рассматривая время слияния как функцию от з = СР',.
можно выразить его в виде для некоторых подходящих констант ры рз, дз, дз, причем Юз > И4, Дифференцирование по з показывает, что есть некоторое Хв, такое, что для всех А' > Кв невыгодно увеличивать х за счет размера буфера. В примерах, приведенных на диаграмме А, Хв оказалось, грубо говоря, равным 10 000; при сортировке более 10 000 записей большой размер буфера предпочтительнее. Заметим, однако, что при сбалансированном слиянии число проходов резко изменяется., когда Я "проходит" через степень Р. Если заранее известно приближенное значение Аг, то размер буфера следует выбрать таким, чтобы Я с большой вероятностью оказалось немного меньше степени Р. Капример, размер буфера для первого графика диаграммы А был равен 12 500, так как Я = 78.
Это было вполне удовлетворительно, но если бы Я оказалось равным 82, было бы значительно лучше немного уменьшить размер буфера. Формулы для десяти примеров. Возвращаясь к диаграмме А, попытаемся вывестн формулы, аппроксимирующие время работы для каждого из десяти методов. В большинстве случаев основная формула ХСигт + (гг+ рл')ХСшг+ (1+ р)57Сы,т будет достаточно хорошим приближением к суммарному времени сортировки.
если мы определим число промежуточных проходов слияния х = а!пЯ + 6 и число промежуточных проходов перемотки х' = а'1пЯ+ 6г. Иногда необходимо внести в (9) некоторую поправку; специфика каждого метода учитывается следующим образом. Пример 1. Сбалансированное слияние с прямым чтением. Формулы х = ! 1п Б/!и Р11 — 1, х' = ! 1п о/!п Р1! /Р могут использоваться для Р-путевого слияния с 2Р лензвмн. Пример 2. Многофазное слияние с прямым чтением. Можно положить х' гг, так как за каждой фазой обычно следует перемотка приблизительно такой же длины., как предшествующее слияние.
Из табл. 5.4.2-1 получаем в случае шести лент значения о 0.795, 6 0.864 — 2. (Значение 2 вычитается из-за того, что элементы таблицы включают наряду с промежуточными проходамн также начальный и конечный.) К значению, полученному по формуле (9), нужно добавить время пеРемотки вводной ленты после начального РаспРеделениЯ, а именно — РдгСьггт+б. Пример 3. Каскадное слияние с прямым чтением. Из табл. 5.4.3-1 следуют значения о м 0.773, зд и 0.808 — 2.
Время перемотки сравнительно трудно оценить; возможно„предположение х' «х достаточно точно отражает суть дела. Как и в примере 2, нужно добавить к (9) время начальной перемотки. Пример 4. Многофазное слияние с расщеплением лент. Из табл. 5.4.2-6 получаем а м 0.752, д 1.024 — 2. Происходит совмещение почти всех операций перемотки, за исключением перемотки после начальной установки (рЖСьггт + б) и двух фаз вблизи конца (36% от 2р)з'Сыт). Мы можем также вычесть 0.18 из Д, так как первая половина фазы совмещается с начальной перемоткой. Пример 5.
Каскадное слияние с совмещением перемоток. Здесь, используя табл. 5,4.3-1 для Т = 5, получаем а м 0.897, д м 0.800 — 2. Почти все несовмещенные операции перемотки встречаются непосредственно после начального распределения н после каждого двухпутевого слияния. После точного начального распределения самая длинная лепя содержит примерно 1/д всех данных, где д есть отношение роста, После каждого двухпутевого слияния объем перемотки в случае шести лент равен 4,.г(„ь (см. упр. 5.4.3 — 5) и можно показать, что в случае Т лент объем перемотки после двухпутевых слияний приблизительно равен (2/(2Т вЂ” 1) ) (1 — соя (4я /(2Т вЂ” 1) ) ) от всего файла.
В нашем случае Т = 5, что составляет Хз(1 — соэ80') и 0.184 от длины файла, и это происходит в 0.946 !п В+ 0.796 — 2 случаях. Пример 6. Сбалансированное слияние с обратным чтением. Оно напоминает пример 1, но значительная часть операций перемотки устраняется. Изменение направления обработки ленты от прямого к обратному вызывает некоторые задержки, но онн несущественны. С вероятностью 1/2 перед последним проходом понадобится перемотка, поэтому можно взять л' = 1/(2Р). Пример 7. Многофазное слияние с обратным чтением.
Так как в этом случае выбор с замещением порождает серии, меняющие направление примерно через каждые Р раз, то следует заменить (3) другой формулой для Я. Достаточно хорошим приближением будет 5 = '|г'|3+ 1/Р)/(6Р')1+ 1 (см. упр. 54.1 — 24). Все время перемотки устраняется, и из табл. 5.4.2-1 следует, что а 0.863, 8 ш 0.921 — 2. Пример 8. Каскадное слияние с обратным чтением.
Из табл. 5.4.3 — 1 имеем а и 0.897, |) 0.800 — 2. Время перемотки по этой таблице можно оценить как удвоенную разность ("проходы с копированием"' минус "проходы без копирования") плюс 1/(2Р) в том случае, если перед окончательным слиянием необходима перемотка для получения возрастающего порядка. Пример 9. Осциллирующая сортировка с обратным чтением.
В этом случае выбор с замещением должен многократно начинаться н останавливаться; за один раз распределяется от Р— 1 до 2Р— 1 серии (в среднем Р); средняя длина серий, следовательно, оказывается приблизительно равной Р'(2Р-4/3)/Р н можно оценить Я = (Ж/((2 — 4/(3Р))Р')1+1. ЕХекоторое время расходуется на переключение от слияния к распределенпю н обратно; оно приблизительно равно времени, затрачиваемому на чтение Р' записей с вводной ленты, а именно — Р'Сш1 т, и это происходит примерно Я/Р раз. Время перемотки и время слияния можно оценить, как в примере 6.
Пример 10. Осциллирующая сортировка с прямым чтением. Данный метод нелегко проанализировать, поскольку окончательная фаза "чистки", выполняемая после исчерпания исходных данных, не так эффективна, как предыдущие. Пренебрегая этим трудным аспектом и просто считая, что есть одни дополнительный проход, можно оценить время слияния, полагая и = 1/!и Р, 8 = 0 н к' = к/Р. Распределение серий в этом случае несколько иное, так как не используется выбор с замещением; мы устанавливаем Р' = М/С и 5 = (Х~Р ). Приложив некоторые усилия, можно совместить вычисление, чтение н запись во время распределения, введя дополнительный коэффициент накладных расходов, равный приблизительно (М+ 2В)/М. Время переключения режимов, упомянутое в примере 9, в настоящем случае не нужно учитывать, поскольку переключение совмегнается с перемоткой. Итак, оценка времени сортировки имеет вид (9) плюс 2ВМСы<т/М.
Из табл. 1 следует, что полученные оценки достаточно хорошо совпадают с реальностью, хотя в нескольких случаях расхождение составляет порядка 50 с. Формулы в примерах 2 и 3 показывают, что каскадному слиянию нужно отдать Таблица 1 СВОДНАЯ ТАБЛИЦА ОЦЕНОК ВРЕМЕНИ СОРТИРОВКИ Добаалеииа ОцеикаРеальиый (9) к (9) итога итог Пример Р В Р' Д ы а р а' 3 12500 650 5 8300 734 5 8300 734 4 10000 700 4 10000 700 3 12500 650 4 10000 700 4 10000 700 4 !0000 700 4 10000 79 1.062 0.9!О -1.000 70 !.094 0.795 — 1.136 70 1.094 0.773 - 1.192 73 1.078 0.752 -0.994 73 1.078 0.897 -1.200 79 1,062 0.910 — 1.000 79 1.078 0.863 — 1,079 73 1.078 0.697 -1.200 87 1.078 0.721 -1.000 100 !.078 0.721 0.000 1 2 3 4 5 6 7 8 9 !О 1064 1076 1113 1103 1075 1127 947 966 972 992 98! 980 922 907 952 949 874 928 1131 1158 О.зоз о,ооо 0.795 -1.136 0.773 -1.192 0.000 0.720 0.173 0.129 О.ООО 0.167 О.ООО О.ООО 0.098 0.117 0.000 0.125 0.180 0.000 ! 064 !010 рАГСачт+ 3 972 рА'Скат + 3 844 р74Сы;т+3 972 981 922 952 846 Р'ЯСалт/Р 1095 2лг7Сы;т)М предпочтение перед многофазным на шести лентах, тем не менее на практике многофазнае слияние лучше! Причина зтого кроется в том, что графики, подобные изображенным на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
