Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 86
Текст из файла (страница 86)
Это оставляет для дерева выбора место объемом 650 записей. Ббльшая часть начальных серий будет, следовательно, иметь длину около 1 300 записей (10 или 11 блоков); на диаграмме А получилось 78 начальных серий, причем последняя серия короткая. При первом проходе слияния, как показано, сливаются 9 серий на ленту 4, а не чередуются ленты 4 — 6. Это дает возможность выполнять полезную работу в то время, когда оператор вычислительной машины устанавливает рабочую ленту на устройство 6; так квк общее число серий з известно срезу после завершения начального распределения, то алгоритм знает, что на ленту 4 должно быть слито (Я/91 серий, затем ((Я вЂ” 3)~9) — на ленту 5, затем ((о — 6)/9) — на ленту 6. Вся процедура сортировки в этом примере может быть изображена с использованием обозначений, введенных в разделе 5.4.2, следующим образом: 126 126 126 39 39 36 92 92 9261 27' 27' 24' 78' Пример 2.
Миогофазиое слияние с прямым чтением. Второй пример на диаграмме А иллюстрирует многофаэное слияние в соответствии с алгоритмом 5,4.2Р. В этом случае мы выполняем пятипутевое слияние, поэтому память разбита на 12 буферов по 83 записи. В течение первоначального выбора с замещением мы имеем два буфера ввода объемом 50 записей н два буфера вывода объемом 83 записи, что оставляет 734 записи в дереве; таким образом, начальные серии на этот раз будут иметь длину около 1 468 записей (17 яли 18 блоков). В данной ситуации получено о = 70 начальных серий, причем длины двух последних в действительности равны только четырем блокам и одному блоку соответственно.
Схему слияния можно изобразить так: Сбалансированное слияние с прямым чтением Многофазное слияние с прямым чтен ем Каскадное слияние с прямым чтением Многофазное слияние с расщепление лент Каскадное слияние с совмещением пе мотки Сбапансированноеслияниесобратны чтением Многофазное слияние с обратным чте ием Каскадное слияние с обратным чтени Осциллирующая сортировка с обрати м чтением Осциллирующая сортировка с прямы чтением 10.
8 Время в миртах 0" 1гз 18 013117 1!4 18 12 0131!$ 1!2 14 0818 0!3118 11$ 17 1з 11 0'142 53 142!5з 2'5' 52 51 48 44 42 41 84 82 81 16!191 19' 34' 70' Удявигешьно, но для многофазного слияния необходимо на 25 с больше, чем для значительно более простого сбалансированного слияния! Это объясняется двумя основными причинами. 1) Этот случай особенно удачен для сбалансированного слияния, так как 5 = 78 очень близко к точной степени 3. Если бы было получено 82 начальные серии, то сбалансированное слияние потребовало бы еще одного прохода. 2) При многофазном слиянии теряется 30 с во время замены вводной ленты и в целом свыше 5 мии проходит в ожидании завершения операций перемотки.
В противоположность этому сбалансированное слияние требовало сравнительно небольшого времени перемотки. Во второй фазе многофазного слияния сэкономлено 13 с, так как 8 фиктивных серий на ленте 6 можно считать присутствующими ллже во время перемотки этой ленты, но затем не происходит никакого совмещения перемотки. Таким образом, многофазный метод щюигрывает, несмотря иа то что оп требует значительно меньшего времени чтения/записи. Пример 3. Каскядное слияние с прямым чтением. Этот случай аналогичен предыдущему, только в нем используется алгоритм 5.4.362 114 1гз 112 1!4 1И 1319 114 11$ 5'6» 53 5362 — 1' — 12! 6' 18! 18 70! 1з2з38 22 16' (Просматривая диаграмму А, не забывайте представлять каждый пример в дей- ствии.) 1!9 1!$ 18 0219 021'$ 021!' 0214 — 021944 12! 02117 Пример 4.
Многофазное слияние с рассцеплепнем лент. Эта процедура, описанная в конце раздела 5.4.2, позволяет совместить ббльшую часть времени перемотки. Она использует четырехпутевое слияние, так что мы делим память на 10 буферов по 100 записей; в дереве выбора имеется 700 записей, и в результате оказывается, что образовано 72 начальные серии. Последняя серия вновь очень короткая. Использована схема распределения, аналогичная представленной в алгоритме 5.4.20, за ней следует простой, но в некоторой степени специализированный метод размещения фиктивных серий: 1!1 18 1з 12 14 131 131141 13!14! 141 13! 13' 271 72' Среди всех примеров на диаграмме А, в которых не используется чтение в обратном направлении, в етом, как оказывается, нандучшее время выполнения.
Поскольку 5 никогда не бывает очень большим, можно разработать более сложный алгоритм, который позволит разместить фиктивные серии еще лучше 1см. упр. 5.4,2-(2б)). Пример Б. Каскадное слияние с совмещением неремоток. Эта процедура работает почти так же быстро, как предыдущая, хотя управля!оший е!о алгоритм более прост. Мы используем для начального распределения метод каскадной сортировки, как в алгоритме 3,4.3С, но с Т = о, а не Т = б. Зачем использование лент в каждой фазе каждого "каскада" чередуется таким образом, что мы обычно не выполняем запись на ленту, пока она почти наверняка не окажется перемотанной. Короче говоря, схема такова: 1м 1м 116 116 14 1" 72 Зз 7232 — 2б! — В' 72' 122236 4!е 41 10' Пример В.
Сбалансированное слияние с обратным чтением. Этот пример похож на пример 1, но все перемотки устранены: 126 ! П22 Так как в примере 1 было сравнительно мадо перемоток, зта схема не намного лучше, чем в случае прямого чтения. Фактически она оказывается несколько медленнее многофазной схемы с расщеплением лент, несмотря на удачное значение Я = 78, 1)з 116 16 16 1з 11 З'7' З'7'1З' 3'7213' 72131 7'1З' 131 ,14 4'3' 4431 4231 42З' 4'З' 31 0244 0244324' 0244324' О'4'З'4' 423241 413241 324! 3!4! 41 021644 1644 1444 1244 44 4з ,$2 4! Пример 7.
Миогофазяое слияние с обратным чтением. В этом примере используется только пять лент из шести, чтобы устранить время перемотки и смены вводной ленты. Таким образом, применяется только четырехпутевое слияние и такая же структура буферов„как в примерах 4 и 5. Используется распределение, аналогичное приведенному в алгоритме 5.4.20, но направление серий чередуется н лента 1 фиксируется, как конечная выводная лента.
Сначала записывается восходящая серия на ленту 1, затем — нисходящие серии 2-4, после этого— восходящие серии на ленты 2-4, нисходящие серии на ленты 1-3 и т. д. Всякий раз, когда переключаетсн направление, выбор с замещением обычно дает более короткую серию, поэтому было образовано 77 начальных серий вместо 72 в примерах 4 и о, Эта процедура в результате дает распределение (22, 21, 19, 15) серий, а ближайшее точное распределение — (29, 56, о2, 44). В упр.
5.4.4-5 показано, как построить строки чисел слияния, которые могут использоваться для размещения фиктивных серий оптимальным образом. Такая процедура может выполняться на практике, поскольку конечность бобины гарантирует; что Я-никогда не будет слишком большим. Поэтому пример на диаграмме А был построен с использованием такого метода размещения фиктивных серий (см. упр, 7). Он оказался самым быстрым из всех представленных примеров. Пример б. Каскадное слияние с обратным чтением.
Как и в примере 7, здесь участвует только 5 лент. Эта процедура соответствует алгоритму 5.4,3С, используя перемотку и прямое чтение„чтобы избежать однопутевого слияния (так как перемотка более чем в два раза быстрее чтения на устройствах й1ХТ). Распределение, следовательно, то же, что и в примере 6. Используя символ "г" для обозначения перемотки, изобразим эту схему так: 4г1 1гг Агэ 1 1 ) А»1 Агг4 )у»с А»Аг Агг Аэ» — В»г4 17!г Аэ»»'гэ 2 гг Агг Пример 9.
Осциллируюгцая сортировка с обратным чтением, При осциллирующей сортировке с Т = 5 (алгоритм 5.4.оВ) может использоваться распределение буферов, как в примерах 4, 5, 7 н 8, поскольку она выполняет четырехпутевое слияние. Однако выбор с замещением действует здесь иначе, так как непосредственно перед входом в каждую фазу слияния выводится серия длиной 700 (а не примерно 1 400), чтобы очистить внутреннюю память. Следовательно, здесь порождается 65 серий вместо 72.
Некоторые ключевые шаги этого процесса таковы: А»А1 А1А» АгА» Аг А1 )7»~ ~» 1~»~ ~» В» )'.г» .4м 04 А!61!4114 Ам,04 А1»И~А! .4м 4»4 А16»144»4 А!61УФ! А16-~-~4 416 А!6114 416 А16Агз А!6~ ~4 А16»14 Ам А16А4 А!6А13 А16 А16А» А16 44 А16 16 4161 А!64 416~ Пример 10. Осциллирующая сортировка с прямым чтением. В последнем примере выбор с замещением не используется, так как все начальные серии должны быть одной длины. Следовательно, будет происходить внутренняя сортировка 1 000 записей (полной емкости памяти) каждый раз, когда требуется начальная серия: зто дает Я = 100. Вот некоторые ключевые шаги процесса: А1 А1 .41 А!А» А! А»А» А»А» А1А4 А1А» )41 44 41 44 4!А» 41 44 А1 А» .41.44 А1 А» )61А» )61А» ,ф1А» Ашб Эта программа оказывается самой медленной из всех частично из-за того, что в ней не используется выбор с замещением, но большей частью вследствие ее весьма нескладного конца !двухпутевое слияние).
Оценка времени выполнения. Посмотрим теперь, как вычислить приблизительное время выполнения некоторого метода сортировки с учетом характеристик используемого НМЛ й1ХТ. Можно ли предсказать результаты, изображенные на диаграмме А, не выполняя дебильного моделирования? А! А1А» А!А»А16 А» А»А!8 )6»А16 А1 А!А4 А»А4 А»А» ф1А» А»А» А!А»А!6А64 )4 А»АмА64 .$14»А16 464 41 4»А!6А64 41)4441»А64 Сбалвнснроввнввв )Т 6) Квсявлнвя гТ 5) МногоФввнвя (Т= 5) оснлллирвивия (т = 5) $0 Ф с 5 $ в о о' О ! 2 5 !О 20 50 !00 М0 500 !ООО 2000 5000 Нвчвлмснс сорин, Ю Рис.
Вб. Несколько обманчивый способ сравнения схем слияния. Один способ, который традиционно использовался для сравнения рэзличных схем слияния, состоит в том, чтобы совместить графики, подобные представленным на рис. 70, 74 и 78. На этих графиках изображено эффективное число проходов по данным как функция от числа начальных серий в предположении, что все начальные серии имеют примерно равную длину (рис. 88). Но это нс пссзволяет выполнить адекватное сравнение, потому что, как мы видели, разные методы приводят к различному числу начальных серий; кроме того, имеются различные накладные расходы, зависящие от относительной частоты междублочных промежутков; значительное воздействие оказывает также время перемотки. Все эти зависящие от конкретного оборудования особенности затрудняют использование машинно-независимой методики истинного сравнения методов слияния.
С другой стороны, из рис. 88 все же явствует, что за исключением сбалансированного слияния эффективное число проходов может быть достаточно хорошо аппрокснмировано плавными кривыми вида а )п о+ 8. Следовательно, можно неплохо сравнивать методы в любой практической ситуации, проанализировав формулы, аппроксимирующие время выполнения. Конечно, наша цель — найти формулы простые, но достаточно близкие к реальности. Попытаемся теперь вывести такие формулы в терминах следующих параметров: 2ч — число сортируемых записей, С вЂ” число символов в записи, М вЂ” объем доступного пространства в оперативной памяти (символов; предпола- гается кратным С) т — время в секундах, нужное для того, чтобы прочитать илн записать одни символ, рт — время в секундах для перемотки в пересчете на один символ, пт — время в секундах стартстопной задержки, 7 — число символов в междублочном промежутке, 6 — время в секундах, необходимое оператору для снятия и замены вводной ленты, В, — число симвспшв в блоке иерассортироваиного ввода., В, — число символов в блоке рассортированного вывода.
Для ИХХТ имеем т = 1/60000, р = 2/5., и = ЗОО, т = 480. В примере, рассмотренном выше, Ь = 100000, С = 100, М = 100000, Ю =- ЗО, В; = В, = 5000. Обычно именно зти характеристики оборудования и данных решающим образом влияют на время сортировки (хотя время перемотки часто задается более сложным выражением, чем просто козффицнентом р). Имея указанные параметры и схему слияния, вычислим еще некоторые величины: максимальный порядок слияния в схеме, число записей в дереве выбора с замещением, число начальных серий, приблизительное среднее число чтений и записей каждого сим- вола, не считая начального распределения н окончательного слияния, 7Г = о 1пВ +;9 я' = а'!пЯ+,9' — приблизительное среднее число перемоток каждого символа во время промежуточных фзз слияния, — число символов в блоке в промежуточных фазах слияния, — "козффициенты накладных расходов" — действительное время, необходимое для чтения или записи в пересчете на один символ (с учетом промежутков н стартстопного времени), отнесенное к обп1ему времени т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
