AOP_Tom3 (1021738), страница 14
Текст из файла (страница 14)
[См. 0.5. Рагепг 3428946 (1969).) Последовательность (дг,..., гр) из р чисел будем называть битонной, если дг > > дь « др для некоторого й, 1 < )с < р. (Сравните это с обычным определением "монотонных" последовательностей.) Битонный сортировщик порядка р -- это сеть компараторов, способная сортировать в порядке неубывания любую битонную последовательность длиной р.
Задача слияния в:г « .. вп, г, уг « у„ является частным слу.чаем задачи битонной сортировки., так как слияние можно осуществить, применив к последовательности (вп,,..., вг, ум., ., у„) битонный сортировшик порядка т, + и, Заметам, что если последовательность (дг,...,др) битонная, то таковыми же являются и все ее подпоследовательности. Вскоре после того, как Вэтчер открыл сети четно-нечетного слияния, он обнаружил, что аналогичным образолг можно построить битонный сортировщик порядка р, сначала независимо сортируя битонные подпоследовательности (вм дэ, л;„... ) и (дв, лгн де,... ), а затем выполняя сравнения- обмены лг.дв, гв.гм .... (Доказательство приводится в упр.
10.) Если соответству- * Термин "бетонная последовательность" (Ь1сошс веяпепсе) введен по аналогии с термппом 'мопотоппвп последовательность" (пюпосошс, ведпепсе), — Прим. псрео. «) «2 «« «4 «5 «6 Рис. 52. Битонный сортировщик Бэтчера порядка 7. ющее чигшо модулей компараторов обозначить через С'(р), то будем иметь С'(р) = С'((р/2]) + С'((р/2]) + ]р/2] при р > 2; (15) а время задержки, очевидно, равно (!яр]. На рис. 52 показан битонный сортировщик порядка 7, построенный этим способом; он может быть использован и как (3, 4)-, и как (2, 5)-сеть слияния с задержкой в три единицы, четно-нечетное слияние для т = 2 и и = 5 имеет на один компаратор меныпе, но на один уровень задержки болыпе. Особый интерес представляет битонный сортировщик Бэтчера порядка 2', он состоит из 1 уровней по 2' компараторов в каждом.
Пронумеруем входные линии ге,г„...,«э Б пРи этом элемент «; сРавниваетсЯ с «на УРовне 1 тогда и только тогда, когда двоичные представления «и г различаются только в 1-м слева разряде. Эта простая структура приводит к созданию параллельной сети сортировки, которая функционирует так же быстро, как обменная сортировка со слиянием (алгоритм 5.2.2М), но реализовать ее значительно проще (см. упр.
11 и 13). Битонная сортировка оптимальна в том смысле, что ни один метод параллельного слияния, основанный на одновременно несвязанных сравнениях, не может выполнять сортировку быстрее, чем за (!8(т + и)] стадий, независимо от того, используетгл ли при этом предыстория (см. упр. 46). Существует и другой способ достижения оптимума, который требует меньше сравнений, но логика его чуть сложнее. Этот метод анализируется в упр. 57. Если 1 < т < и, то и-й (считая от наименыпего) выход (т, и)-сети слияния должен зависеть от 2т + (т < и] входов (см, упр. 29).
Если его можно вычислить, используя компараторы с 1 уровнями задержки, то в результат будет вовлечено не более 2' входов; следовательно, 2' ) 2«и + (т < и] и 1 ) (!8(2т + (т < ««])]. Бэтчер показал (Берег«СЕВ-14122 (А!«гоп, О!«!о: Соог!уеаг Аегоэрасе Согрогабоп, 1968)], что это минимальное время задержки достигается, если в сети допускается разветвление, т. е. такое разбиение линий, что одно и то же число в одно и то же время используется несколькими модулями. В качество примера на рис. 53 изображена сеть (и = 6), которая сливает один элемент с и другими после всего двух уровней задержки. Конечно, сети с разветвлением не соответствуют нашим соглашениям; довольно легко понять, что любая (1, п,)-сеть слияния без разветвления должна иметь время задержки !8(«1 + 1) или более (см. упр, 45). Сети выбора.
Сети можно применить также к задаче раздела 5.3.3. Пусть Бь«(и) обозначает минимальное число компараторов, необходимых в сети, которал перемещает ! наибольших из и различных входов на 1 определенных выходных линий: они могут располагаться на этих выходных ливиях в произвольном порядке. Пусть «««(и) обозначает минимальное количество компараторов, необходимых для перемещения Рис.
53. Сеть, обеспечивающая слияние одного элемента с шестью другими н имеющая разветвления, в результате чего достигается минимальная задержка. 1-го входа в порядке убывания из п различных входов на определенную выходную линию, и пусть В)(п) обозначает минимальное число компараторов, требуемых для перемещения 1 наибольших из п различных входов на определенные 1 выходные линии в порядке неубывания. Нетрудно видеть (см. упр.
17), что 0,(п) < гб(п) < Кб(п), (16) Сначала предположим, что имеется 21 элементов (хм...,ям) и мы хотим аыбрать 1 наибольших. В. Е. Алексеев (Кибернетика 5, 5 (1969), 99-103) заметил, что это может быть выполнено, если сначала рассортировать (хд,..., хб) и (хбьб,, ям), а затем сравнить и поменять местами (17) яых, бм х1.хм, нэпам ы Так как ни в одной из этих пар не может содержаться более одного из наибольших 1 элементов (почемуу), процедура Алексеева должна выбрать 1 наибольших элементов.
Если нужно выбрать 1 наибольших из п1 элементов, то мы можем применить эту процедуру п — 1 раз (исключая каждый рач 1 элементов); следовательно, (7б(п1) < (и — 1)(2Б(1) +1). Алексеев также получил интересную нижнюю оценку для задачи выбора. Теорема А. буб(п) ) (п — 1) ~1ф(1+ 1)1. Доказательство.
Удобнее рассматривать эквивалентную задачу выбора наименьших 1 элементов. Около каждой линии сети компараторов можно выписать числа (1, и), как показано на рис. 54, где 1 и и обозначают соответстиенно минимальное и максимальное значения, которые могут появиться в этом месте, если входом служит перестановка (1,2,...,и). Пусть 1; и 1 — нижние оценки на прямых б и у перед сравнением х,:х~ и пусть 1,' и 1' — соответствующие нижние оценки после этого сравнения.
Очевидно, что 1,'. = ппп(1,,1 ), а в упр. 24 доказывается соотношение (неочевидное) (19) 1'<1,+1,. (1,В) (1,7) (1,1) (1,Ь) [1,4) Рис. 54. Отделение четырех наибольших от четырех наименьших. (Числа над линиями используются в доказательстве теоремы А.) Рис. бб. Иная интерпретация сети, изображенной на рис.
54. Теперь дадим другую интерпретацию функционирования сети (рнс. 55); предположим, что на нсех входных прямых содержится нуль и каждый "компаратор" помешает теперь на верхнюю линию меньший из своих входов, а на нижнюю линию — больший вход плюс единицу. Получающиеся числа (гп(, тт,, .., т„) обладают свойством (20) в любом месте сети, так как это свойство первоначально справедливо и сохраняется каждым компаратором в силу (19).
Кроме того, окончательное значение ги) +те+ + т„равно общему числу компараторов в сети, так как каждый компаратор добавляет к этой сумме единицу. Если сеть выбирает наименьшие ! чисел, то и — ! из чисел 1; больше или равны Г + 1; следовательно, и — ( из чисел ш( должны быть > ) !8(( + 1)1. Нижняя оценка в теореме А оказывается точной, если ! = 1 или ! = 2 (см. упр.
19). В табл. 1 даны значения Й(п), 7((п) и И'1(п) для небольших Г и 71. Эндрю Яо (Апг)геег Уао) !Р)(. П. Ншвз, Н. о( 11!шо!В (1975)] исследовал асимптотическое поведение 171(п) при фиксированном ! и показал, что Гз(п) = 2п + !8п + 0(1) и ГЬ(п) = п)18((+ 1)1 + 0((1ойп)!В'!) при п ) со; минимальное время задержки равно !8п+ (181) 18!8п+О(!ой!об!ойп).
В работе Х. Р!ррепйег, ЯСОМР 20 (1991), 878-887, доказано при помощи неконструктнвного метода, что для любого е > 0 существует сеть выбора с 17(„(В)(п) ( (2+ е) и 18 и, если только и достаточно велико (В зависимое!н от е). Таблица 1 СРАВНЕНИЯ, НЕОБХОДИМЫЕ ДЛЯ СЕТЕЙ ВЫВОРА (Вг(п), Ьг(п), Й'г(п)) 1=1 1=2 1=3 еж4 1=5 1=6 (О, 0,0) (1,1,1) (0.,1,1) (2,2,2) (2,3,3) (О.
2,3) (З,З,З) (4,Ь,Ь) (3,5,5) (0,3,5) (4, 4, 4) (6, У, У) (6, Т, 8) (4, г, 9) (О, 4, 9) (5, 5, 5) (8, 9, 9) (8, 10, 10) (8, 10, .12) (5, 9, 12) (О, 5, 12) п=1 п=2 п=З п=4 п=5 п=б Стадия 1 Стадия 2 Стадия 3 Стадия 4 Рнс. 56. Нестандартная сеть, основанная на битанной сортировке. Если х = (хг,..., х„) — это и-мерный вектор, а о — п-сеть, то обозначим через хо вектор чисел ((хо)г,...,(хо)„), порожденных сетью. Положим также для краткости о 'гг' Ь = шах(а Ь), о Л Ь = ппп(о Ь), а = 1 — о, тогда (х[г гу[), = х, Л х, (х[г:1[)г = х, гг' хг и УПРАЖНЕНИЯ (часть 1) Далее в нескольких упражнениях теория сетей сортировки рассматривается более детально, поэтому будет удобно ввести некоторые обозначения.
Вместо молуля сравнения-обмена будем писать [г:1[. Сеть с и входами и г модулями компараторов обозначим через [гг:)г[ [гг:1г[ [г,;15[, где каждое из г и г меныпе или равно и:, для краткости будем называть ее п-сетью. Сеть называется стандартной, если гг < у„лля 1 < 9 < г. Так, например, .на рис.
44 приведена стандартная 4-сеть, обозначепнаи последовательностью компаратаров [1:2[[3;4[[1:ЗЦ2 4Ц2:3[. Наши соглашения в тексте о графическом представлении диаграмм сетей позволяют рисовать толька стандартные сети: все кампараторы [г г[ изображаются прямой линией от г к 1, где 1 < 1 Чтобы нарисовать нестандартную сеть, можно испадьзовать стрелку от г к 1, указываюшую, чта большее число направляется к острию стрелки. Например, на рнс.
56 изображена нестандартная сеть для 16 элементов с компараторами [1г2Ц4.3ЦЬ:6Ц8гу) и т. д. В упр. 11 доказывается, что это сеть сортировки. (х[г:1])г = хы когда г ~ й Зв 71 Будем говорить, чта о является сетью сортировки, если (хо), < (ха),эг для всех х и для 1 < г < и. Символ еаг обозначает вектор, в позиции г которого находится 1, а в остальных позициях — 0; таким образом, (е 0)г = Яо Символ Р обозначает множество всех (О 2'и-мерных векторов из 0 и 1, а Р— множества всех и! векторов, являющихся перестановками (1, 2,..., и). Мы будем использовать обозначения х Д у и х ч' у для векторов (х1 д уы, .., х и у„) и (хг Ч уг,..., х„г7у ) и будем писать х < у, если х, < у, при всех г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
