Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 61
Текст из файла (страница 61)
7>>ог!сев оГ гЛе Ап>ег. 51агЛ. Яос. 14 (1967), 283; Ргос. АРХЕ Ярг!пй,Ушпг Сошригег Сс>пй 32 (1968), 307-314). Кое-кому удалось сократить число компараторов. используемых в конструкции слияния с обменами, предложенной Бэтчером. В (11) показаны наилучшие из известных в настоящее время верхних оценок для о'(и).
и = 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 Так как 5(п) < с(п) при 8 < и < 16, обменная сортировка со слиянием неоптимальна при всех и > 8. Если и < 8, то такая сортировка эквивалентна по количеству компараторов конструкции Бозе и Нельсона.
Флойд и Кнут доказали в 1964-1966 годах, что указанные значения Я(п) яючнм при и < 8 (см. А ЯцггеуоГСотЬ!лагоа!а! Т!икиу (г!оггЬ-Но!!апс1, 1973), 163-172,', значения Я(п) при и > 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 подмножествами (а, Ь, с, И), чтобы о прямой, помеченной з, было известно, что она содержит числа, меньшие или равные содержимому прямой, помеченной г, всякий раз, когда в есть подмножество Ь ° Состояние сортировки на этой стадии более подробно рассматривается в упр. 32. Однако сравнения, выполняемые на последующих уровнях сети Грина, становятся совершенно загадочными.
До сих пор никто не знает, как обобщить эту конструкцию, чтобы получить столь же эффективные сети для больших значений и. Шапиро и Грин создали также изображенную на рис. 49 сеть для и = 12. Хорошие сети для и = 11, 14 или 15 можно получить, удалив нижнюю линию в сети для и + 1 вместе со всеми компараторами, подсоединенными к этой линии. Наилучшая известная к настоящему моменту сеть для 256 элементов, разработанная Д. Ван Ворисом (В. Уап УоогЬ!э), свидетельствует, что Я(256) < 3651 по сравнению с 3839 в сети, которая построена по методу Бэтчера.
[См. В,. Ь. Пгузг!а!е, Р. Н. Уоппй, ЯТСОМР 4 (1975), 264-270.) При п -+ оо оказывается, что Я(п) = 0(п!ойп); этц впечатлякнцая верхняя оценка найдена Айтаи (А)гш), Комлошем (Кснп!оэ) и Шемереди (Язешегей) в Сош!ипагог!са 3 (1983), 1.19. Построенные ими сети не представляют практического интереса, поскольку множество компараторов о=9 25 модулей, задержка 9 кж10 29 модулей, задержка 9 о — -12 39 модулей, задержка 9 к=13 45 модулей, задержка 10 о = 16 60 ваодулей, задержка 1О Рис. 49.
Эффективные сети сортировки. используется в них только для того, чтобы сохранить множитель 1ойп; метод Вэтчера работает гораздо лучше до тех нор, пока и не выйдет за пределы доступной памяти на всех компьютерах старушки Земли! Но теорема Айтаи, Комлоса и Шемереди все-таки правильно устанавливает асимптотический рост 8(п) до уровня постоянного множителя. Сети с минимальным временем.
В физических реализациях сетей сортировки и на компьютерах с параллельной архитектурой можно выполнять непересекающиеся операции сравнения-обмена одновременно, поэтому кажется естественным попытаться минимизировать время задержки. После некоторого размышления приходим к выводу, что время задержки сети сортировки равно максимальному числу компараторов, расположенных на каком-либо "пути" через сеть, если определить путь как траекторию любого двюкения слева направо, возможно, с переходом с одной линии на другую через компараторы.
У каждого компаратора мы можем постанить порядковый номер, указывающий самый ранний момент, когда может быть выполнено сравнение; этот номер на единицу больше, чем максимальный номер у компараторов, предшествующих данному (рис. 50, (а); в части (Ь) этого рисунка показана та же сеть, перерисованная так, чтобы каждое сравнение выполнялось как можно раньше.) 1 2 3 1 2 3 4 4 3 $6 6 Рис.
$0. Выполнение каждого сравнения как можно раньше по времени. В описанной выше сети Бэтчера для четно-нечетного слияния затрачивается Тв(т, и) единиц времени, где Тв(т, 0) = Тв(0, и) = О, Тв(1, 1) = 1, к Тв(т,и) = 1+ шах[ТвЯп~2), ~и/2)), Тв()т/2), ~и/2))) при ти > 2, Используя эти соотношения, можно доказать по индукции, что Тв(т,и+1) > Тв(т,и); следовательно, Тв(т, и) = 1+ Та((т/2), ~и/2) ) для ти > 2; отсюда заключаем, что Тв(т, и) = 1+ ~18 гпах(т, и)) при ти > 1.
(12) Таким образом, как показано в упр. о, метод сортировки Бэтчера имеет время задержки 1+ ~(йи) Пусть Т(и) — минимальное время задержки, достижимое в лкбой сети сортировки и элементов. Некоторые из описанных выше сетей можно так улучшить, не используя дополнительных компараторов, чтобы они имели меньшее время задержки, как показано парис. 51 для и = 6 ни = 9, а вупр. 7 — для и = 10. Можнополучить еще меньшее время задержки, если добавить один нли два дополнительных модуля, как показано на рнс. 51 (см. сети для и = 10, 12 и 16).
Эти схемы приводят к следукнцнм верхним оценкам для Т(и) при малых значениях и: и = 1 2 3 4 5'б 7 8 9 10 11 12 13 14 15 16 (14) Т(и) < О 1 3 3 5 5 6 6 7 7 8 8 9 9 9 9 Известно, что приведенные здесь значения точны при и < 10 (см. упр. 4). Сети, изображенные на рис. 51, заслуживают тщательного изучения, поскольку вовсе не очевидно., что онн годятся для сортировки; эти сети были созданы в 1969-1971 годах Дж. Шапиро (и ж 6, 9, 12) и Д.
Ван Борисом (и = 10, 16), Сети слияния. Пусть М(т, и) обозначает минимальное число компараторов, необходимых для сети, которая сливает т элементов х1 « а'„, с и элементами 91 « . р„, образуя рассортированную последовательность 31 « 3„+„. К настоящему времени не создано ни одной сети слияния, которая была бы лучше к=а 12 модулей, задержка 5 а= 10 З1 модуль, задержка 7 к=12 40 модулей, задержка 8 Пж16 01 МедуЛЬ, ЗадЕржКа 9 Рис. Ы. Наиболее быстродействующие сети сортировки, предназначенные для параллещ ных вычислений.
описанной выше сети четно-нечетного слияния; следовательно, функция С(т, и) и (6) представляет наилучшую известную верхнюю оценку для М(т, п). Е', У. Флойд обнаружил интересный способ, позволяющий определить нижа»ие оценки в этой задаче слияния. Теорема Р, М(2п,2п) > 2М(п, п) + и для всех п > 1. Доказав»сазов»ее.
Рассмотрим сеть с М(2п, 2п) модулямн компараторов, способную Сортнровата ВСЕ ВХОДНЫЕ ПОСЛЕДОВЮЕЛЬНОСти (З1 . ° . З»к)1 таино, ЧтО З1 < ЗЗ « ' д»„, и лз < к» « ° г»„, Мы можем считать, что каждый модуль заменяет (дозу) элементом (ппп(лпл;),1пах(зцзу)) при некоторых 1 < у (упр. 16). Итак, компараторы можно разделить на три класса: а) 1 < 2п и,у < 2п; Ь) 4 > 2п и у > 2п; с) 1<2пиу>2и. Класс (а) должен содержать, по крайней мере, ЛХ(и, и) компараторов, так как яэ„+м лт„+э,..., яеп могут уже находиться на своих местах, когда слияние начинается; аналогично в классе (Ь) должно быть хотя бы ЛХ(п, и) компараторов. Кроме того, как показывает входная последовательность (О, 1, О, 1,..., О, 1), класс (с) содержит не менее и компараторов, так как и нулей должны переместиться из (ля„эы..., леп) в (лг ° лэп) ° ° Многократное применение теоремы Р доказывает, что ЛХ(2™, 2") > -'(т+ 2) 2"', следовательно, М(п, и) > -'и !йп+ 0(п).
Из теоремы 5.3 2М известно,. что слияние 6сл сетевого ограничения требует лишь М(п, и) = 2п — 1 сравнений; таким образом, мы доказали, что сетевое слияние сложнее по существу, чем слияние всюбще. Четно-нечетное слияние показывает, что М(т, и) < С(т, и) = -'(гп + п) !аппп(т, и) + 0(т + и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
