AOP_Tom3 (1021738), страница 81
Текст из файла (страница 81)
Хуже того, мы вскоре проскочим конец ленты! Здесь возникает та же проблема, что и в случае выхода очереди эа границу памяти [см. соотношения 2.2.2 — (4) и (5)), но решение в виде 2.2.2 — (б) и (7) не применимо к лентам, так как их нельзя закольцевать. Поэтому дерево будем называть сильным Т-Яо-деревом, если оно может быть помечено так, чтобы соответствующая схема слияния испольэовала ленты, подчиняясь особой дисциплине: "записать, перемотать, прочитать все, перемотать; записать, перемотать, прочитать все,перемотать и т, д.", ь 19. (23) (Р. М.
Карп.) Найдите бинарное дерево, которое не является З-йуо, з 20. (23) Сформулируйте условие "сильного Т-б(о-деревьв в терминах достаточно простого правила относительно недопустимых конфигураций меток дент, аналогичного (4'). 21. (1б) Нарисуйте представление в виде дерева схемы слияния с прямым чтением, определенной посредством векторов в уцр. 7. Можно ли считать его сильным 3-ррро-деревом7 22. (йб) (Р. М. Карп.) Докажите, что представления в виде дерева многофазного и каскадного слияний с точным распределением полностью одинаковы как в случае обратного чтения, так и в случае прямого чтения, эа исключением номеров, которыми помечены внутренние узлы. Найдите более широкий класс векторных представлений схем слияния, для которык верно сказанное.
23. [24] (Р. М. Карп.) Будем говорить, что серия уы1... уР" Р схемы слияния является сгладиепр если никакая выводная лента не используется в дальнейшем как вводная, т. е. если нс существует р, 1, (з, таких, что р7 > р > Й > г и К ' = -1, у = +1. Назначение этого упражнения — доказать, что при каскадном слиянии минимизируезся число стадий среди всех схем слияния с тем же числом лент и начальных серий.
Удобно ввести некоторые обозначения. Будем писать о -ч тюр если е и ш такие Т- векторы, что существует схема слияния, которая на своей первой стадии переводит ир в е (т. е, существует скема глияния уР ~... 0Р~Р, такая, что у ... 01~П является стадией, ш = Кррш + + Кюр и о = К01+ + бр~1.) Будем писать е .С ш, если о и ир — Т-векторы, такие, что сумма наиболыпих й элементов вектора е < не превышает суммы наибольших й элементов вектора кр при 1 < Й < Т. Так, например, (2,1,2,2,2,1) 4 (1,2,3,0,3,1), поскольку 2 < 3, 2+2 < 3+3, ..., 2+2+2+2+1+1 < 3+3+2+1+1+0.
Наконец, если о = (ер,..., нт), то пусть С(о) = (зт, зт-г, зт — з,..., зр,О), где зь есть сумма наибольших )з элементов векторов ш а) Докажите, что е -+ С(е). Ь) Докажите, что е .С ш влечет С(е) С С(ш). с) Считая известным результат упр. 24, докажите, что при каскадном слиянии минимиэируется число стадий. 24. (Муб) Используя обозначения, принятые в упр. 23, докажите, что е -ч ю влечет ш < С(о). 25.
(Мбб) (Р. М. Карл.) Будем говорить, что сегмент уРзР... у01 схемы слияния является фазой, если ни одна иэ лент не используется и для ввода, и для вывода, т. е. если не существует р',,1, )з, таких, что д > р > г, р7 > )з > г, ур01 = +1, и КрРЮ = — 1. Назначение этого упражнения — исследовать схему слияния, которая минимизирует число фаз. Будем писать о ~ ир, если щ может быть преобразовано в е за одну фазу (ср.
с подобным обозначением, введенным в упр. 23), и пусть Рь(о) = (зь+гьзр, зь+гььз,..., зь+ет, О, ..., 0), где зр обозначает 1-й в порядке убывания элемент е и зь = зр + -. + зь. а) Докажите, что о ~ Рь(и) при 1 < )з < Т. Ь) Докажите, что из е .< ш следует Рь(е) ~ Рь(щ) при 1 < й < Т.
с) Докажите, что из о ~ пр следует ш -( Рь(е) для некоторого )с, 1 < /з < Т. 0) Следовательно, схема слияния, сортируюя1ая максимальное число начальных серий на Т лентах эа р7 фаэ, может быть изображена последовательностью целых чисел /ср /сз... )ср, такой, что начальное распределение есть Рь,(... (Рьз(Рь,(и)))...), где и = (1,0,...,0). Эта стратегия минимума фаз имеет сильное Т-Яо-представление и входит в класс схем из упр. 22. Когда Т = 3, это мизгафазиал схема, а при Т = 4, 5, б, 7 зто вариация сбалансированной схемы. 26. (М4б) (Р.
М. Карп.) Верно ли, что оптимальная последовательность )зр йз... йю упомянутая в упр. 25, всегда равна 1(Т)2)(Т)2)(Т/2)(Т/2) ... для всех Т > 4 и всех достаточно больших р7? Операция Т1 Т2 ТЗ Т4 Т5 Стоимость Фаза 1 Фаза 2 Фаза 3 Фаза 4 Фаза 5 Фаза 6 Фаза 7 Фаза 8 Фаза 9 Распределение Слияние Распределение Слияние Распределение Слияние Распределение Слияние Слияние 4 4 4 4 4 4 4 4 16 А1 А1 Р» Р4А, Р4 Р» А1 Р» Р»А1 ,04 А1 А1 Р4 Р4А, Р4 Р»А1 Р» А1 А1 Р» Р, А1 Р» А1 Здесь, как и в разделе 5.4.4, А„и Р, применяются для обозначения соответственно восходящих и нисходящих серий относительной длины г. Прн использовании рассматриваемого метода сначала начальные серии по одной записываются на каждую из четырех лент и сливаются (чтение выполняется в обратном направлении) на пятую ленту.
Затем распределение возобновляется, на этот раз циклически сдвинутое на одну позицию вправо по отношению к лентам, и в результате второго слияния образуется еще одна серия Р». Когда этим способом будут сформированы четыре серии Р», дополнительное слияние приведет к созданию Аш. Процесс можно продолжать, создав еще три Аш, слив их в Рв», и так до тех пор, пока не исчерпаются исходные данные. При этом заранее знать длину исходных данных не нужно. Если число начальных серий 5 есть 4, то нетрудно заметить, что этот метод обрабатывает каждую запись ровно гп + 1 раз (один раз во время распределения и гл раз во время слияния). Если 5 лежит между 4™ 1 и 4, можно с помощью фиктивных серий увеличить 5 до 4"', следовательно, весь процесс сортировки потребует )!об»51 + 1 проходов по всем данным.
Это именно то, что достигается при сбалансированной сортировке на восьми лентах. В общем случае осциллирующая сортировка с Т рабочими лентами эквивалентна сбалансированному слиянию с 2(Т вЂ” 1) лентами, так как при этом выполняется ) !обг 1 51 + 1 проходов по данным. Если 5 оказывается степенью Т вЂ” 1, то это самое лучшее, что можно получить при любом методе с Т лентами (здесь достигается нижняя оценка из соотношения 5.4.4 — (9)).
С другой стороны, если 5 равно (Т вЂ” 1)™ 1 + 1, т. е. ровно на единицу больше степени Т вЂ” 1, при этом методе теряется почти целый проход. В упр. 2 показано, как, используя специальную программу завершения, устранить часть этой лишней работы для случая, когда 5 — - не степень Т. Еще одно усовершенствование было предложено в 1966 году Деннисом Л.
Венчером (44епи!з Е. ВепсЬег), который назвал свою процедуру перекрестным слиянием. [См. «5.4.5. Осциллирующая сортировка Еще один подход к сортировке методом слияния был предложен Шелдоном Собелем (БЬе!боп 5оЬе!) в 3АСЛХ 9 (1962), 372 — 375. Вместо того чтобы начинать с распределения прохода, когда все начальные серии распределяются по лентам, он предложил алгоритм, который переключается то на распределение, то на слияние, так что большая часть сортировки происходит еще до того, как вся исходная информация полностью проанализирована.
Предположим, например, что для слияния используются 5 лент. По методу Собеля 16 начальных серий будут сортироваться следукнцнм образом. Н. Ч'ебеЫпб, Рагепогбашва11оп (Бег!ш: %". »1е Огиусег, 1970), 164-166; см. также »1. Я. Рагелг 3540000 (1970).] Основная идея состоит в том, чтобы отложить слияние до тех пор, пока не будет накоплено больше сведений о Я, Мы обсудим несколько измененную форму первоначальной схемы Бенчера.
Этот усовершенствованный метод осциллирующей сортировки действует следующим образом. Операция Т1 Т2 ТЗ Т4 Т5 Стоимость А» А» А» А1А» А» А» А» А1А» А» А» А» А» А» 1д» Р»А» Р» Р»А» Р» Р» А» Р» Р» Р„А, Р» Р»А» Р» Р» Р»А» Р» В зтот момент слияние всех Р» в Аш не выполняется (если только не окажется, что исходные данные исчерпаны). Лишь после того, как закончится Фаза 15 Слияние Р» Р» Р»1 ~» лл Р» 4, будет получена первая серия А~в Фаза 16 Слияние Р» Р» Р» А1» 16. Вторая серия Аы появится после создания еще трех Р», Фаза 22 Слияние Фаза 23 Слияние лл лл Р» АшР» 4 Р» Р» — - Ага Ага 16, и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
