AOP_Tom3 (1021738), страница 73
Текст из файла (страница 73)
К счастью, заботиться о больших о приходится довольно редко (см. раздел 5.4.6), так что алгоритм )з на практико не так уж плох (а иа самом деле — даже весьма неплох!). яи в х Д 7 "8 86 И 5 ь 5 4 з 10 36 20 90 50 294 100 702 500 4641 1000 10371 5000 63578 24 19 60 49 194 158 454 362 3041 2430 6680 5430 41286 32905 0.951 0.761 +.14 +.16 17 44 135 325 2163 4672 28620 0.656 +. 19 15 14 38 36 128 121 285 271 1904 1816 4347 3872 26426 23880 0.589 0.548 +.21 +.20 13 12 34 33 113 104 263 254 1734 1632 3739 3632 23114 22073 0.539 0.488) к о!по+ +.02 +.18) х о Таблица 4 ЧИСЛО НАЧАЛЬНЫХ СЕРИЙ, ОБРАБАТЫВАЕМЫХ ПРИ СТАНДАРТНОМ МНОГОФАЗНОМ СЛИЯНИИ 8 Т=З Т=4 Т=5 Т=б Т=7 Т=8 Т=9 Т=10 10 36 20 90 50 294 100 714 500 4708 1000 10730 501)0 64740 24 19 62 49 194 167 459 393 3114 2599 6920 5774 43210 36497 14 13 12 37 34 33 131 120 114 312 292 277 2100 2047 2025 4716 4597 4552 29533 28817 28080 17 15 44 41 143 134 339 319 2416 2191 5370 4913 32781 31442 Математически многофазная сортировка впервые проанализирована У.
К. Картером (%. С. Саг1ег) [Ргос. 1Р?Р Сопдгевв (1962), 62-66]. Многие из приведенных им результатов относительно оптимального размещения принадлежат Б, Сэкману (В. аас1апап) и Т. Зингеру (Т. бйпдег) ["А чесгаг шабе! 1ог гпегде васс апа!ув1в", неопубликованный доклад, представленный на симпозиуме АСМ Загс Бушров1шп (1вочешЬег, 1962), 21 радев). Позднее Сэкман предложил метод распределения по горизонтали, используемый в алгоритме П. Дональд Шелл (Попа!с) Зйе11) [САСМ 14 (1971), 713 — 719; 15 (1972), 28], независимо развив эту теорию, указал на соотношение (10) и подробно изучил несколько различных алгоритмов распределения.
Дальнейшие полезные усовершенствования и упрощения были получены Дереком Э. Зэйвом (Пеге1г А. Еаче) [91СОМР 6 (1977), 1 — 39); некоторые из результатов Зэйва рассматриваются в упр. 15 — 17. Производящая функции (16) впервые была исследована У. Буржем (1ч'. Впгде) [Ргос. 1Р1Р Сопдгевв (1971), 1, 454 — 459). А как обстоит дело с временем перемотки? До сих пор мы использовали число начальных обрабатываемых серий как единственную меру эффективности для сравнения стратегий слияния на лентах.
На после калсдой из фаз 2 — 6 в примерах в начале этого раздела компьютер должен ожидать перемотки двух лент; обе выводные ленты — как предыдущая, так и новая текущая — должны быть перемотаны в начало, прежде чем сможет выполняться следующая фаза. Эта может вызвать существенную задержку, так как в общем случае на предыдущей выводной ленте содержится значительный процент сортируемых записей (см.
столбец "Проходы/фазы" в табл. 1). Досадна, когда компьютер простаивает при перемотке, тогда как в это время можно было бы, используя иную схему слияния, выполнять полезную работу с остальными лентами. Данную задачу можно решить с памошью простой модификации мнагофазной процедуры, хотя она требует не менее пяти лент [см. диссертацию И. Сезари (У. Ссвай) (П. о(Раг1в (1968), 25-27), в которой эта идея приписывается Ж. Карону (3.
Сагоп)). Каждая фаза схемы Карона сливает серии с Т вЂ” 3 лент на любую другую ленту, в то время как оставшиеся две ленты перематываются. Рассмотрим, например, случай для шести лент н 49 начальных серий. В следующей таблице буквой В. обозначены ленты, верематывающиеся во время данной фазы; предполагается, чта на ленте Т5 содержатся первоначальные серии. Т2 ТЗ Т4 Т5 Тб Время записи Фаза Т1 111 2 (К) 3 )в 12 5 б В. 7 15' 8 К 9 15' 10 (РЗв) (В.) 3 К 34 32 К 23' К (232) Здесь все перемотки, по существу, совмещены, за исключением фазы 9 ("фиктивная фаза", которая подготавливает окончательное слияние) и перемотки после начальной фазы распределения (когда перематываются все ленты).
Если 1 есть время, необходимое для слияния стольких записей, сколько содержится в одной начальной серии, а г — время перемотки на одну начальную серию, та этому процессу необходимо около 1821+ 407 плюс время начального распределения и завершающей перемотки. Соответствующие выражения для стандартного многофэзного метода, использующего алгоритм )У, есть )401+ 1047, что несколько хуже, если г = ~11, и несколько лучше, если г = —,' Е Все сказанное о стандартном многофвзном методе приложимо к многофвзному методу Карона; например, последовательность а„теперь удовлетворяет рекуррентному соотношению (20) а„ = а„ г + а„-з + а„ 4 вместо (3). Читателю будет полезно проанализировать этот метод таким же образом, как мы анализировали стандартный многофазный, поскольку это улучшит понимание обоих методов (см., например, упр. 19 и 20).
В табл. 5 сведены данные о многофвзнои методе Карана, аналогичные данным об обычном многофазном иетоде, приведенным в табл. 1. Заметим, что на самом деле при восьми и более лентах метод Карона становится лучше многофэзного как по числу обрабатываемых серий, так и по времени перемотки, несмотря на то что он выполняет (Т вЂ” 3)-путевое слияние вместо (Т вЂ” 1)-путевого! Таблица 5 ПРИБЛИЗИТЕЛЪНЫЕ ДАННЫЕ О ХОДЕ СОРТИРОВКИ МЕТОДОМ МНОГОФАЗНОГО СЛИЯНИЯ КАРОНА Проходы Фазы Проходы/ Отношение фазы, % роста Ленты 3.556 )и 8+ 0.158 2.616 )а 5 — 0.166 2.337 !п  — 0.472 2.216 )а Б — 0.762 2.156 !п 5 — 1.034 2.124)п 5 — 1.290 2.078 )в Я вЂ” 3.093 5 6 7 8 9 10 20 117 112 )в )в 1" — К К 71 112 К К 7' 11' 7 11' — К 1 в — К К 3' 5 К К 3 52 31 5' — К К 33 49' (К) 1,463 !и 5 + 1.016 0.951 !в Я + 1.014 0.781 !па т 1.001 0.699 )и 8 + 0.980 0.654 )п 8+ 0.954 0.626 )и 8 + 0.922 0.575 )в а + О.
524 49 8 х 3 = 24 5 х 3 = 15 4 х 5 = 20 2х 7=14 2 х 11 = 22 1 х 15 = 15 1 х 23 = 23 Охзз= О 1 х 49 = 49 41 36 ЗЗ 32 ЗО 29 28 Время перемотки 17 49 — 17 = 32 гпах(8, 24) гпах(13, 15) гпвх(17, 20) гпвх(11, 14) !пах(22, 24) гпвх(15, 15) гпах(20, 23) 14 1.3247180 1.4655712 1.5341577 1.5701473 1,5900054 1.6013473 1.6179086 Эти данные будут казаться парадоксальными, пока мы не поймем, что высокий порядок слияния не обязательно озивчаегп эффективную сорпъировку. В качестве крайнего рассмотрим случай, когда 1 серия помещается на ленту Т1 и и серий— на Т2, ТЗ, Т4, Т5; если поочередно выполнять слияния на Тб и Т1, пока Т2, ТЗ, Т4, Т5 не станут пустыми, то время обработки будет соответствовать (2пз + Зп) длинам начальных серий, т.
е., по существу, будет пропорционачьио 5з, а не 51о55, хотя все время производится пятипутевое слияние. Растцепление лент. Эффективное совмещение времени перемотки является проблемой, возникающей во многих приложениях, а не только при сортировке. Существует общий подход, который можно использовать в большинстве случаев. Рассмотрим итеративный процесс, в котором ленты используются следующим образом. Т1 Т2 Фаза 1 Вывод 1 Перемотка Фаза 2 Ввод 1 Вывод 2 Перемотка Перемотка Фаза 3 Вывод 3 Ввод 2 Перемотка Перемотка Фаза 4 Ввод 3 Вывод 4 Перемотка Перемотка и т. д.
Здесь "Вывод кз означает запись в й-й выводной файл, а "Ввод кз — его чтение. Можно устранить время перемотки, если использовать три ленты, как было предложено в работе 1.. %е1зпег, САСМ 5 (1962), 102: ТЗ Т2 Т1 Фаза 1 Вывод 1.1 Вывод 1.2 Перемотка Вывод 1.3 Фаза 2 Ввод 1.1 Вывод 2.1 Ввод 1.2 Перемотка Вывод 2.2 Перемотка Ввод 1.3 Вывод 2.3 Фаза 3 Вывод 3.1 Ввод 2.1 Перемотка Вывод 3.2 Перемотка Ввод 2.2 Перемотка Вывод З.З Ввод 2.3 Фаза 4 Ввод 3.1 Вывод 4.1 Перемотка Ввод 3.2 Перемотка Вывод 4.2 Перемотка Ввод З.З Вывод 4.3 и т.
д. Здесь "Вывод й.у" означает запись у-й трети к-го выводного файла, а "Ввод Й.уз — ее чтение. В конце концов, будет исключено все время перемотки, если перемотка выполняется, по крайней мере., вдвое бьгстрее чтения/записи. Подобная процедура, в которой вывод в каждой фазе разделяется между лентами, называется расщеплением лент. В работе В. 1 .
444сА11еззег, САСМ Т (1964), 168-159, показано, что расщепление лент приводит к эффективному методу совмещения времени перемотки в многофазном слиянии. Этот метод можно использовать с четырьмя или более лентами, и он осуществляет (Т вЂ” 2)-путевое слияние. Предположим снова, что имеется шесть лент, и попытаемся построить схему слияния, которая работает следующим образом, расщепляя вывод на каждом уровне (буквы "1", "О" и "В" обозначают соответственно ввод, вывод и перемотку).
Уровень 7 выводимых серий иг Оз и4 и! ш ио (21) оо Чтобы по окончании работы получить одну серию на ленте Т4, а остальные ленты сделать пустыми, необходимо иметь оо — — 1, но+ и! — — О, из+из = но+по, из + оз = и! + и! + ио + оо, из+ ез = из+ из+ и!+ о! + ио+ оо, и4+ из = 445+ из+ из+из+44! + и!+445+но, из + ив — 444 + 444 + из + 442 + 442 + и2 + 441 + е! + ио + ио и т. д. В общем случае требуется, чтобы и„+ о„е! — — и„! + ев ! + ив-2 + ов-2 + и„— з + и — з + и„-4+ е а-4 (22) при всех п > О, если считать иу = с, = О при всех 4 < О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
