AOP_Tom3 (1021738), страница 13
Текст из файла (страница 13)
7тайсев о1 гйе Ашег. Май. 5ос. 14 (1967), 283; Ргос, АИР5 5ргтп8',1отС Сотри!от СолЕ 32 (1968), 307 — 314). Кое-кому удалось сократить число компараторов, используемых в конструкции слияния с обменами, предложенной Бэтчером. В (11) показаны наилучшие из известных в настоящее время верхних оценок для 5(ть). и = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 с(п) = 0 1 3 5 9 12 16 19 26 31 37 41 48 53 59 63 Я(п) < 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60 Так как Я!и.) < с(п) при 8 < п < 16, обменная сортировка со слиянием неоптималыы при всех и ) 8.
Если и < 8, то такая сортировка эквивалентна по количеству компараторов конструкции Бозе и Нельсона. Флойд и Кнут доказали в 1964 1966 годах, что указанные значения Я!и) шочнм при и < 8 ]ем. А Биггеу о7 СопгЫпагог!а! Тпеогу (Мог!!з-Но!!апд, 1973), 163 — !72]; значения Я!и) прн п ) 8 до снх пор неизвестны. Конструкции, позволившие получить указанные выше значения !см. (11)), представлены графически на рис. 49.
Сеть при п = 9, основанная на интересном трехпутевом глиянии, была построена Р. У. Флойдом в 1964 году; установить ее корректность можно при помощи общего принципа, описанного и упр. 27. Сеть при и = 10 построил в 1969 году Л. Ваксман !Л. 1Ча!гэшап); он рассматривал входы как перестановки множества !1,2,...,10] и пытался, сохраняя некоторую симметрию, насколько возможно уменьшить число значений, которые могут появляться в каждой строке на данной стадии. Представленный вариант сети для и = 13 построен по довольно отличающейся технологии: Хью Жуиле (Нпйпеэ Зп!!!е) разработал программу, .чтобы построить эту сеть, моделируя эволюционный процесс размножения ]Ьесйие хо!ел !и Сошр.
Яс!. 929 (1995), 246 — 260]. Сеть имеет несколько необычный вид, но она работает; к тому же она меньше других сетей, созданных рациональным человеческим разумом. В 1969 году Дж. Шапиро (С. Я!тар!го) нашел сеть сортировки 16 элементов с 62 компараторами, и это было весьма неожиданно, поскольку резульшт, полученный методом Бзтчера !63 сравнения), казалось, невозможно улучшить, егчн п является степенью 2, Познакомившись с конструкцией Шапиро, в еще болыпее изумление поверг всех М. У.
Грие (М. %. Сгееп), который нашел сортировку с 60 сравнениями, показанную на рис. 49. Первая часть конструкции Грина довольно проста для понимания; после того как выполнены 32 операции сравнения-обмена слева от пунктирной линии, все прямые можно так пометить 16 подмножествами ]а, Ь, с., И), чтобы о прямой, помеченной в, было известно, что она содержит чшла, меньшие или равные содержимому прямой, помеченной 1, всякий раз, когда э есть подмножество Ь Состояние сортировки на этой стадии более подробно рассматривается в упр. 32.
Однако сравнения, выполняемые на последующих уровнях сети Грина, становятся совершенно загадочными. До сих пор никто не знает, как обобщить эту конструкцию, чтобы получить столь же эффективные сети для больших значений и. Шапиро и Грин создали также изображенную на рис. 49 сеть для и = 12. Хорошие сети для и = 11, 14 или 15 можно получить, удалив нижнюю линию в сети дяя п+ 1 вместе со всеми компараторами, подсоединенными к этой линии. Наилучшая известная к настоящему моменту сеть для 256 элементов, разработанная Д. Ван Ворисом (В. Чап аоот!и!э), свидетельствует, что Я(256) < 3651 по сравнению с 3839 в сети, которая построена по методу Бэтчера.
!См. Н. Ь. Бгуэс!а!е, Р. Н. Уоппй, ЯСОМР 4 (1975), 264 — 270.] При и — ! оо оказывается, что 5(п) = 0(п,!обп); эта впечатляющая верхняя оценка найдена Лйтаи (Л!га!), Комлогпем (Кош!оэ) и Шемереди !Бгешегес!!) в СотЫпасопса 3 !1983), 1 — 19. Построенные ими сети не представляют практического интереса, поскольку множество компараторов в=9 25 мадулей, задержка 9 а=10 29 модулей, задержка 9 я=12 39 модулей, задержка 9 и = 13 45 модулей, задержка 10 в=16 60 модулей, задержка 1О Рис.
49. Эффективные сети сортировки. используется в них только для того, чтобы сохранить множитель !ойп; метод Бэтчера работает гораздо лучше до тех пор, пока н не выйдет за пределы доступной памяти на всех компьютерах старушки Земли! Но теорема Лйтаи, Комлоса и Шемереди все-таки правильно устанавливает асимптотический рост оз(п) до уровня постоянного множителя.
Сети с минимальным временем. В физических реализациях сетей сортировки и на компьютерах с параллельной архитектурой можно выполнять непересекающиеся операции сравнения-обмена одновременно, поэтому кажется естественным попытаться минимизировать время задержки. После некоторого размышления приходим к выводу, что время задержки сети сортировки равно максимальному числу компараторов, расположенных на каком-либо "пути" через сеть, если опредолить путь как траекторию любого движения слова направо, возможно, с переходом с одной линии на другую через компараторы. У каждого компаратора мы можем поставить порядковый номер, указывающий самый ранний момент, когда может быть выполнено сравнение; этот номер на единицу болыпе, чем максимальный номер у компараторов, предшествующих данному (рис.
50, (а); в части (Ь) этого рисунка показана та же сеть, перерисованная так, чтобы каждое сравнение выполнялось как можно раньше.) 1 2 3 4 1 2 3 1 2 3 4 4 3 3 б б (к) Рнс. 50. Выполнение каждого сравнения как можно раньше по времени. В описанной выше сети Бэтчера для четно-нечетного слияния затрачивается Тн(т, и) единиц времени, где Тя(т, О) = Тн(0, и) = О, Та(1, 1) = 1, и Тв(т,п) = 1+ шах(Тн(1т/21, '1п/2)), Тя((тп/2~', )и/2))) при тпп > 2.
Используя эти соотношения, можно доказать по индукции, что Тп (тп, и+1) > Тн (тп, и); следовательно, Тв(т, и) = 1+Тв((тп/Т), (и/2)) для тпп > 2; отсюда заключаем, что Тн(тп,п) = 1+ (18птах(тп,пД при тп > 1. (12) Таким образом, как показано в упр. 5, метод сортировки Бэтчера имеет время задержки 1 + (18п1) (13) Пусть Т(п) — минимальное время задержки, достижимое в любой сети сортировки и элементов.
Некоторые из описанных выше сетей можно так улучшить, не используя дополнительных компараторов, чтобы они имели меньшее время задержки, как показано парис. 51для и = 6 и и = 9, а в упр. 7 — для и = 10. Можно получить еще меньшее время задержки, если добавить один или два дополнительных модуля, как показано на рис. 51 (см.
сети для и = 10, 12 и 16). Эти схемы приводят к следующим верхним оценкам для Т(п) при малых значениях и: и = 1 2 3 4 5'6 7 8 9 10 11 12 13 14 15 16 Т(п) < 0 1 3 3 5 5 6 б 7 7 8 8 9 9 9 9 Известно, что приведенные здесь значения точны при и < 10 (см. упр. 4). Сети, изображенные на рнс.
51, заслуживают тщательного изучения, поскольку вовсе не очевидно, что они годятся для сортировки; эти сети были созданы в 1969-1971 годах Дж. Шапиро (и = 6, 9, 12) и Д. Ван Ворисом (и = 10, 16). Сети слияния. Пусть М(т, и) обозначает минимальное число компараторов, необходимых для сети, которая сливает та элементов х1 « . х с и элементами 91 « ... р„, образуя рассортированную последовательность кт « ° г„,+„.
К настоящему времени не создано ни одной сети слияния, которая была бы лучше и=е 12 модулей, задержка 5 и=9 95 модулей, задержка 8 и=10 31 модуль, задержка 7 п=!2 40 модулей, задержка 8 в=16 61 модуль, задержка 9 Рис. 61. Наиболее быстродействующие сети сортировки, предназначенные для параллельных вычислений.
описанной выше сети четко-нечетного слияния; следовательно, функция С(гп,ц) в (6) представляет наилучшую известную верхнюю оценку для Лз (т, п). Р. У. Флойд обнаружил интересный способ, позволяющий определить пизюмпс оценки в этой задаче слияния. Теорема Р. Лз(2п,2п) > 2М(гь и) + и для всех п > 1.
Доказашельсгпво, Рассмотрим сеть с ЛХ(2пз 2п) модулями компараторов, способную сортировать все входные последовательности (зг,..., гаи), такие, что зг < зз « .. зы, ~ и зз < зз < . < ззв. Мы можем считать, что каждый модуль заменяет (Заду) ЭЛЕМЕНТОМ (ППП(амЗЗ),ШаХ(ЗОЗ1)) Прн НЕКОТОРЫХ З < 1 (унр. 16). ИтаК, компараторы можно разделить на три класса: а) 1<2пиу<2п; Ь) 1 > 2п ну > 2п; с) 1<2пиу>2п, Класс (а) должен содержать, по крайней мере, ЛХ(и, и) компараторов, так как две+и двпьв.....,дгш ьгогут уже находиться на своих местах, когда слияние начинается; аналогично в классе (Ь) должно быть хотя бы ЛХ(и, и) компараторов. Кроме того, как показывает входная последовательность (О, 1, О, 1,..., О, 1), класс (с) содержит не менее и компараторов, так как и нулей должны переместиться из (две+и..., део) в (дг.....,гво).
1 Многократное применение теоремы Г доквзьгвает, что М(2,2 ) > -'(гп+2)2м: следовательно, ЛХ(и,гг) > -'и!ни+ 0(гг), Из теоремы 5.3.2М известно, что г гияние бев сетевого ограничения требует лишь М(и, и) = 2и — 1 сравнений,. таким образом, мы доказали, что сетевое слияние сложнее по существу, чем слияние вообще.
Четко-нечетггое гзияние показывает, что ЛХ(т, и) < С(т, и) = 1(т + и) !к ш1п(т, и) + 0(т -Ь и). В работе Р. В. М!1гегвеп, М. Рагегвоп, 3. Тагш', 4.4СМ 43 (1996), 147-165, теорема Г доработана и установлена нижняя оценка М(т,и) > .г((т+ и) !я(т+ 1) — т/!п2) при 1 < т, < и. Следовательно, ЛХ(т, и) = г (т + и) !я шш(т, и) + 0(т -ь и). Точная формула М(2, и) = С(2, и) = Ц и1 доказана в работе А.
С. г'агй Г. Г. г'ао, оАСЛХ 23 (1976), 566-571. Также известно, что значение ЛХ(т, и) равно С(ги, и) для т = и < 5 [см. упр. 9]. Битонная сортировка. Егли допустимы одновременные сравнения, то, как видно из формулы (12), при четно-нечетном слиянии для 1 < т < и возникает задержка на [!6(2и)1 единиц времени. Бэтчер изобрел другой тнп сети слияния, названный бигпопным сортировщиком (Ьггошс воггег)", для которого время задержки снижается до [)6(иь+ п)1. Но он требует больше модулей компараторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
