Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 62
Текст из файла (страница 62)
В работе Р. В. М!!сегяеп, М. Расегяоп, 3. Тэгш,,УАСЛХ 43 (1996), 147-165, теорема Р доработана и установлена нижняя оценка М(т,п) > э((т+гг)!6(т+ 1) — т/!п2) пРи 1 < т < и. Следовательно, ЛХ(т,п) = 1э(т+ и) !6пнп(т, и) + 0(гп+ и). Точная формула М(2, и) = С(2, и) = ! 'э п1 доказана в работе А, С.
Уэо, Р. Р. 1(ао, 3АСЛХ 23 (1976), 566-571. Также известно, что значение М(пд а) равно С(т, и) для т = и < 5 (см. упр, 9). Витонная сортировка. Если допустимы одновременные сравнения, то, кпк видно из формулы (12), при четно-нечетном слиянии для 1 < т < и возникает задержка на Г!6(2п)1 единиц времени.
Бэтчер изобрел другой тнп сети слияния, названный битоннмм сортпроещиком (Мсоп!с яог(ег)е. для которого время задержки снижается до ()6(га+ и)1. Но он требует больше модулей компараторов. (См. Г Я. Расеи! 3426946 (1969).) Последовательность (яы..., яр) из р чисел будем называть битотсой, если лг > > ле « ° лу для некоторого й, 1 < й < р.
(Сравните это с обычным определением пмонотоннглхг последовательностей.) Битонный сортировщик порядка р — это сеть компараторов, способная сортировать в порядке неубынания любую битонную последовательность длиной р. Задача слияния я1 « . к с Рл « . ° ° й„является частным случаем задачи битонной сортировки, так как слияние можно осуществить, применив к последовательности (к,п,..., ям ум..., дп) битонный сортировщик порядка т + п. Заметим, что если последовательность (гы, ..,гр) битоннан, то таковыми же явлиотся и все ее подпоследовательности.
Вскоре после того, как Бэтчер открыл сети четно-нечетного слияния, он обнаружил, что аналогичным образом можно построить битонный сортировщик порядка р, сначала независимо сортируя битонные подпоследовательности (лм ля, ля,... ) и (яэ, ам лв,... ), а затем выполняя сравнения- обмены э: я ля: ле, °, (Доказательство приводится в упр.
10.) Если соответству- * Тврппп ейптОННал ООСЛЕдОВатЕЛЬНОСтсз (ЫЮПК ВЕЧПЕПСЕ) ВВЕДЕН Па амаЛОГИИ С тпрНННОН "нонотоннал н хледовательносгь" (глопоеопк веопепсе). — Прим. перев. Рис. 52. Бнтонный сортнровпшк Бэтчерэ порядка 7. ющее число модулей компараторов обозначить через С'(р), то будем иметь С'(р) = С'()р/21) + С'((р/2)) + (р/2) при р > 2; (15) а время задержки, очевидно, равно ~байр). На рис. 52 показан битонный сортировщик порядка 7, построенный этим способом; он может быть использован и как (3, 4)-, и как (2, 5)-сеть слияния с задержкой в три единицы; четно-нечетное слияние для гп =- 2 и и = 5 имеет на один компаратор меньше, но на один уровень задержки больше.
Особый интерес представляет бнтонный сортировщик Бэтчера порядка 2', он состоит нз 1 уровней по 2' ' компараторов в каждом. Пронумеруем входные линии хэ,гм...,гэ 1, .при этом элемент г; сравнивается с гу на уровне ! тогда и только тогда, когда двоичные представления 1 и 7' различаются только в 1-м слева разряде.
Эта простая структура приводит к созданию параллельной сети сортировки„ которая функционирует так же быстро, как обменная сортировка со слиянием (алгоритм 5.2.254), но реализовать ее значительно проще (см. упр. 11 и 13). Битонная сортировка оптимальна в том смысле„что ни один метод параллельного слияния, основанный на одновременно несвязанных сравнениях, не может выполнять сортировку быстрее, чем за ) !5(т + п)1 стадий, независимо от того, используется ли при этом предьгсторня (см. упр.
46). Существует и другой способ достижения оптимума, который требует меньше сравнений, но логика его чуть сложнее. Этот метод анализируется в упр. 57. Если 1 < пг < и, то гг-й (считая от наименьшего) выход (гп,п)-сети слияния должен зависеть от 2т+ [гп < и) входов (см.
упр. 29). Если его можно вычислить, используя компараторы с ! уровнями задержки., то в результат будет вовлечено не более 2' входов; следовательно, 2' > 2ш + (гн < и) и 1 > ! !5(2пг + !гп < п))1. Бэтчер показал (Верогь СЕВ-14122 (А!стоп, ОЬ!о: Оообуеаг Легоэрасе Согрогагюп, 1958)], что это минимальное времн задержки достигается, если в сети допускается разветвление, т. е.
такое разбиение линий, что одно и то же число в одно и то же время используется несколькими модулями. В качестве примера на рис. 53 изображена сеть (п = б), которая сливает один элемент с и другими после всего двух уровней задержки. Конечно, сети с разветвлением не соответствуют нашим соглашениям; довольно легко понять, что любая (1,п)-сеть слияния без разветвления должна иметь время задержки !5(гг + 1) или более (см. упр.
45). Сети выбора. Сети можно применить также к задаче раздела 5.3.3. Пусть Ц(п) обозначает минимальное число компараторов, необходимых в сети, которая перемещает Ф наибольших из и различных входов на Г определенных выходных линий; они могут располагаться на этих выходных линиях в произвольном порядке. Пусть Ъ~(п) обозначает минимальное количество компараторов, необходимых для перемещения Щ ю Рнс.
53. Сеть, обеспечиваюшая слияние одного элемента с шестью другими н нмеюшая разветвления, в результате чего достигается минимальная задержка. Ф-го входа в порядке убывания из и различных входов на определенную выходную линию, и пусть 14)(п) обозначает минимальное число компараторов, требуемых для перемещения 1 наибольших из п различных входов на определенные г выходные линии в гюрядке неубывания. Нетрудно видеть (см. упр. 17), что (16) Ц(п) < Ц(п) < И'~(п). Сначала предположим, что имеется 21 элементов (хг,..., хэг) и мы хотим выбрать 1 наибольших. В. Е. Алексеев (Кибернетика 5„5 (1969), 99-103) заметил, что зто может быть выполнено, если сначала рассортировать (хю..., хг) и (хд+г,, хш), а затем сравнить и поменять местами (17) х~ хш хз ° хз~ 1 ..
х~ ° хг-ы Так как ни в одной из этих пар не может содержаться более одного из наибольших г элементов (почему7), процедура Алексеева должна выбрать г наибольших элементов. Если нужно выбрать г наибольших из пс элементов, то мы можем применить эту процедуру и — 1 раз (исключая каждый раз г элементов); следовательно, бгг(пс) < (и — 1)(2Л(С) + Г). (15) Алексеев также получил интересную нижнюю оценку для задачи выбора.
Теорема А. (Уг(п) > (п — г) ~)5(г + 1)1. Дояязапгсзьсшеш Удобнее рассматривать эквивалентную задачу выбора наименьших г элементов. Около каждой линии сети компараторов можно выписать числа (1, и)., как показано на рис. 54, где 1 и и обозначают соответственно минимальное н максимальное значения, которые могут появиться в этом месте, если входом служит перестановка (1, 2,..., и). Пусть 1; и 1 — нижние оценки на прямых 1 и у перед сравнением х;:х, и пусть 1,' и 1' — соответствующие нижние оценки после этого сравнения. Очевидно, что Ц = пцп(1,,1 ), а в упр.
24 доказывается соотношение (неочевидное) 1~ < 1;+1;. ьб) нл Рис. 6е. Отделение четырех наибольших от четырех наименьших. (Числа нал линиями используются в лохазательстве теоремы А.) Рис. 66. Иная интерпретация сети, изображенной на рис. 54. 'Теперь дадим другую интерпретацию функционирования сети (рис, 55): предположим, что на всех входных прямых содержится нуль и каждый "компаратор" помещает теперь на верхнюю линию меньший из своих входов, а на нижнюю линию - — больший вход плюс единицу. Получающиеся числа (гам тлю...,гпе) обладают свойством 2 ем в любом месте сети, так как зто свойство первоначально справедливо и сохраняется каждым компаратором в силу (19).
Кроме того, окончательное значение ти~+щз+ -+ пз„равно общему числу компараторов в сети, так как каждый компаратор добавляет к етой сумме единицу. Если сеть выбирает наименьшие $ чисел, то и — ! из чисел 1, больше или равны Ф+ 1; следовательно, и — ! из чисел т; должны быть > !!8($ + 1)~!. $ Нпжняя оценка в теореме А оказывается точной, если ! = 1 нли ! = 2 (см. упр. 19), В табл. 1 даны значения Ц(п), 6~(п) и Фс(п) для небольших 1 и и.
Эндрю Яо (Апс$ген тао) (РЬ. 11. спев!з, О. оЕ 1!1!по!з (1975)) исследовал асимптотическое поведение Ц(и) при фиксированном ! и показал, что ЕУз(п) = 2п + 18п + 0(1) и (7~(п) = и!18(1+ 1)~ + 0((1ойп)рз'!) при п -+ оо; минимальное время задержки равно 18п+ (18г)!818п+0(1об!об!ойп). В работе Х, Р!ррепйег, $100МР 20 (199Ц, 878-887, доказано при помощи неконструктивного метода, что для любого е > О существует сеть выбора с У(„~з! (я) < (2+ е) и !8 и, если только и достаточно велико (В зависимости от е).
Таблица 1 СРАВНЕНИЯ, ИЕОЕХОДИРИЫЕ ЛтйЯ СЕТЕЙ ВЫБОРА (1)с(п), Я(и). ЮЗЮ) 1 в1 1=2 схЗ 1=4 1=5 1=6 (О, О. О) (1,1,1) (0,1,1) (2,2,2) (2,3,3) (0,2,3) (3,3,3) (4,5,5) (3,5,.5) (0,3,5) (4, 4, 4) (6, 7, 7) (6, 7, 8) (4, 7,9) (О, 4,9) (5, 5, 5) (8, 9,9) (8. 10, 10) (8, 10, 12) (5, 9, 12) (О, 5, 12) и=1 п=2 и=3 и=4 Стадия! Стадия 2 Сидни 3 Рис. бб. Нестандартнаи сеть, основанная на битонной сортировке. Если х = (х„...,х„) — зто и-мерный вектор, а о — и-сетгь то обозначим через хо вектор чисел ((ха)м..., (хо)„), порожденных сетью.
Положим также для краткости а Ч Ь = шак(о, Ь), а д Ь = ппп(а, Ь), а = 1 — а; тогда (х(1:у)); = хю д х„(х(ъ':1))з = х; Ч хз и УПРАЖНЕНИЯ (часть 1) Далее в несколькик упражнениях теория сетей сортировки рассматривается более детально, повтому будет удобно ввести некоторые обозначении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
