AOP_Tom3 (1021738), страница 87
Текст из файла (страница 87)
Возвращаясь к диаграмме А., попытаемся вывести формулы, аппроксимирующие время работы для каждого из десяти методов. В большинстве случаен основная формула (9) ЖСьгт+ (я + рх)гхСыт+ (1+ р) л1Сга,т будет достаточно хорошим приближением к суммарному времени сортировки, если мы определим число промежуточных проходов слияния к = и !пб + // и число промежуточных проходов перемотки я' = и'1п 5 + р'. Иногда необходимо внести в (9) некоторую поправку-, специфика каждого метода учитывается следующим образом. Пример 1, Сбалансированное слияние с прямым чтением. Формулы х = (!пб/!ггР) — 1, ~~ = (1пЯ/1пР)/Р могут использоваться для Р-путевого слияния с 2Р лентами. Пример 2.
Многофазное слияние с прямым чтением. Можно положить я' - х, так как за каждой фазой обычно следует перемотка приблизительно такой же длины, как предшествующее слияние. Из табл. 5.4.2" 1 получаем в случае шести лент значения о 0.795, р" — 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/д всех данных, где д есть отношение роста. После каждого двухпутевого слияния объем перемотки в случае шести лент равен Ыьб„ь (см. упр.
5.4.3 — 5) и можно показать, что в случае Т лепт объем перемотки после двухпутевых слияний приблизительно равен (2/(2Т вЂ” 1)) (1 — сов(4х/(2Т вЂ” 1) ) ) от всего файла. В нашем случае Т = 5, что составляет 1~(1 — соэ80') - 0.184 от длины файла, и зто происходит в 0.9461п 5+ 0.796 — 2 случаях. Пример б. Сбалансированное слияние с обратным чтением. Оно напоминает пример 1, но значительная часть операпий перемотки устраняется.
Изменение направления обработки ленты от прямого к обратному вызывает некоторые задержки, но они несущественны. С вероятностью 1/2 перед последним проходом понадобится перемотка, поэтому можно взять х' = 1/(2Р). Пример 7. Многофазное слияние с обратным чтением. Так как в этом случае выбор с замещением порождает серии, меняющие направление примерно через каждые Р раз, то следует заменить (3) другой формулой для о'.
Достаточно хорошим приближением будет Я = (дт(3+ 1/Р)/(6Р')( + 1 (см. упр. 5.4.1-24), Все время перемотки устраняется,и из табл. 5.4,2-1 следует, что а 0.863, б - 0.921 — 2, Пример 8. Каскадное слияние с обратным чтением. Из табл. 5.4.3 — 1 имеем а 0.897., )1 0.800 — 2. Время перемотки по этой таблице можно оценить как удвоенную разность ("проходы с копированием" минус "проходы без копирования") плюс 1/(2Р) в том случае, если перед окончательным слиянием необходима перемотка для получения возрастающего порядка. Пример 9. Осциллирующая сортировка с обратным чтением. В этом случае выбор с замещением должен многократно начинаться и останавливаться; за один раз распределяется от Р— 1 до 2Р— 1 серии (в среднем Р); средняя длина серий, следовательно, оказывается приблизительно равной Р'(2Р— 4/3) /Р и можно оценить Я = (Х/((2 — 4/(ЗР)) Р') ~ +1, Некоторое время расходуется на переключение от слияния к распределению и обратно; оно приблизительно равно времени, затрачиваемому.
на чтение Р' записей с вводной ленты, а именно — Р'Сьз,т, и это происходит примерно Я/Р раз. Время перемотки и время слияния можно оценить, как в примере 6. Пример 10. Осциллирующвя сортировка с прямым чтением. Данный метод нелегко проанализировать, поскольку окончательная фаза "чистки', выполняемая после исчерпания исходных данных, не так эффективна, как предыдущие. Пренебрегая этим трудным аспектом и просто считая, что есть один дополнительный проход, можно оценить время слияния, полагая а = 1/1и Р, 8 = 0 и яз = т/Р.
Распределение серий в этом случае несколько иное, так как не используется выбор с замещением; мы устанавливаем Р' = М/С и о = (Х/Р'~(. Приложив некоторые усилия, можно совместить вычигленне, чтение и запись во время распределения, введя дополнительный коэффициент накладных расходов, равный приблизительно (М+ 2В)/М. Время переключения режимов, упомянутое в примере 9, в настоящем случае не нужно учитывать, поскольку переключение совмещается с перемоткой. Итак, оценка времени сортировки имеет вид (9) плюс 2ВЛ'Сийг/М, Из табл. 1 следует, что полученные опенки достаточно хорошо совпадают с реальностью, хотя в нескольких случаях расхождение составляет порядка 50 с. Формулы в примерах 2 и 3 показывают, что каскадному слиянию нужно отдать Таблица 1 СВОДНАЯ ТАБЛИЦА ОЦЕНОК ВРЕМЕНИ СОРТИРОВКИ Добавления ОцеикаРеаиаиыа к (9) итога итог Пр р Р В Р' Ь' и о д о' В' (9) 650 79 !.062 734 70 1.094 734 70 !.094 700 73 1.078 700 73 1.078 650 79 1.062 700 79 1.078 700 73 1.078 700 87 1.078 — 100 1.078 0.910 — 1.000 0.795 -1.136 0.773 — 1.192 0.752 -0.994 0.897 — !.200 0.910 -1.000 0.863 — ! .079 0.897 -1.200 0.72! — !.ООО 0.721 0.090 1 2 3 4 5 6 7 8 9 10 3 12500 5 8300 5 8300 4 10000 4 !ОООО 3 12500 4 10000 4 10000 4 10000 4 10000 1064 1076 1113 1103 1075 1127 947 966 972 992 981 980 922 907 952 949 874 928 1131 1158 0.303 0.000 О.
795 — 1. 136 О. 773 — 1.! 92 0.000 0.720 О. 173 О. 129 0.000 0.167 О.ООО 0.000 0.098 0.117 0.000 0.125 0.180 О.ООО 1064 1010 ргуСмсг -!- Ю 972 р!УСм,т + 4 844 рФСм, т -1- Ю 972 981 922 952 846 Р'5Си,т( Р 1095 2ВХСег,т~ы предпочтение перед многофазным на шести лентах, тем не менее на практике многофазное слияние лучше! Причина этого кроется в там, что графики, подобные изображенным на рис.
85 (на котором показан случай для пяти лент), ближе к прямым линиям для многофазного алгоритма; каскадный метод превосходит многофазный на шести лентах для 14 < В < 15 я 43 < В < 55 вблизи "точных" каскадных чисел 15 и 55, но многофазное распределение по алгоритму 5.4.2П лучше или, по крайней мере, не хуже для всех остальных В < 100. Каскадный метод предпочтительнее многофазного при о -+ оо, но на практике В не может быть слишком большим. Заниженная оценка в примере 9 обусловлена аналогичными обстоятельствами; многофазнвя сортировка лучше осциллирующей, несмотря на то что, как следует из асимптотического выражения, для больших В осциллируюп!ая сортировка будет наилучшей.
° Разрабатывая программу сортировки, которая должна испачьзоваться многократно, разумно очень тщательно оценить время работы и сравнить теорию с действительными наблюдаемыми характеристиками выполнения. Так как теория Несколько дополнительных замечаний. Сейчас самое время сделать несколько более или менее случайных замечаний относительно ленточного слияния. ° Приведенные формулы показывают, что сортировка является, в сущности, функцией от произведения )у н С, а не )у и С по отдельности. За исключением нескольких относительно незначительных соображений (например,что В выбирается кратным С) из наших формул следует, что сортировка миллиона записей по 10 символов займет примерно столько же времени, сколько сортировка 100000 записей па 100 символов.
На самом деле здесь может появиться различие, которое невозможно обнаружить в наших формулах, чак как во время выбора с замещением некоторое пространство используется для полей связи. В любом г.чучае размер ключи едва ли окажет какое-либо влияние, если толька ключи не будут столь длинными и сложными, что внутренние вычисления не смогут угнаться за работой НМЛ. При длинных записях и коротких ключах соблазнительно выделить ключи, рассортировать их, а затем как-нибудь переставить записи целиком. Но эта идея, кажется, не работает: она может только отсрочить агонию, поскачьку процедура окончательной перестановки требует почти столько же времени, сколько потребовала бы общепринятая сортировка методом слияния. сортировки развита довольно хорошо, эта процедура, как известно, способна внезапно выявить дефекты в оборудовании или программном обеспечении ввода-вывода в существующих системах.
Оказывается, обслуживание выполнялось медленнее, чем следовало,и никто этого не замечал, пока данный недостаток не проявился на программе сортировки! ° Наш анализ выбора с замещением был выполнен в предположении, что данные в файле расположены сэучайно, но файлы, встречающиеся на практике, очень часто уже являются упорядоченными в той или иной степени. (Фактически иногда пользователи обращаются к сортировке файлов, уже упорядоченных ранее, только для того. чтобы убедиться в этом.) Таким образом, опыт даже в ббльшей мере, чем указывают наши формулы, показал, что выбор с замещением предпочтительнее других видов внутренней сортировки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
