AOP_Tom3 (1021738), страница 79
Текст из файла (страница 79)
5. Оптимальные схемы слияния. До сих пор мы обсуждали различные схемы слияния с лентами, не пытаясь найти метод, "наилучший из возможных". Определение оптимальной схемы кажется особенно сложным в случае прямого чтения, при котором влияние времени перемотки и времени слияния с трудом поддается анализу. С другой стороны, если слияние осуществляется посредством обратного чтения и прямой записи, то, по существу, все перемотки устраняются и появляется возможность довольно хорошо формализовать оптимизацию способов слияния. Ричард М.
Карп (й)спагб М. Кагр) предложил несколько интересных подходов к решению этой задачи, и мы завершаем настоящий раздел обсуждением развитой им теории. Для начала необходим более удобный способ описания схем слияния вместо довольно таинственных тиблиц "содержимого лент", которые использовались выше. Карп предложил два таких способа — векторное представление схемы слияния и представление в виде дерева. Оба представления можно с успехом использовать, и мы опишем их по очереди. Векторное представление схемы слияния состоит из последовательности "векторов слияния" у) )...
9О) у)о), каждый из которых имеет Т компонент; уб) изображает )-й с конца шаг слияния следующим образом: +1, если лента с номером ) является вводной для данного слияния; ))„О = О, если лента с номером у не используется в данном слиянии; (2) — 1, ° если на ленту с номером у выводится результат данного слияния. Таким образом, ровно одна компонента у)О равна — 1, остальные компоненты равны О и 1. Итоговый вектор у)е) — особый: это единичный вектор, имеющий 1 в позиции 1 (если окончательный рассортированный результат оказывается на устройстве у) и О в остальных позициях.
Из данного определения следует, что векторная сумма О) рр) + 9-1) + + к(О) (3) представляет собой распределение серий на лентах непосредственно перед 1-м с конца шагом слияния; причем на ленте 1 находится о~~ ) серий. В частности, по и) можно судить, сколько серий помещается на каждую ленту на начальном проходе распределения.
Три схемы слияния, описанные ранее в этом разделе в табличной форме, имеют следующие векторные представления. Сбалансированная (Т=4, Я=о) ор>=( 4, 4, О, О) уп> =(+1,+1,-1, 0) у>в> = (+>, +1, а, -Ц у<'> =(+1,+>,-1, 0) дм> =(+1,+1, 0,-Ц дан=( — 1, а,+>,4Ц дсп = ( О, — 1, +1, + ц дп> = (+>, +>, -1, 0) дал=( О, О, >, О) Каскадная (Т=4, 5=14) '"> = ( а, а, з, О) у"" =(+1,+1,+>,-Ц даа =(+1,+1,+1,— Ц уаа = (+1, +1, +1, -Ц у" > = (+ >, +1, — 1, а) у>в> =(+1,+1,— 1, 0) дао = (+1,-1, а, 0) ум> = (-1, +1, +1, +Ц уаа = ( а, — 1, +1, +Ц даа =( а, 0,-1,+Ц д"' =(+1,+1,+1,-ц д'>=(0,0, а, Ц Многофазная (Т=З, б=>З) оав> =( о, В, О) д> "> = (+1, +1, -Ц у>н> = (+1,+>,-Ц по> (+1 +> ц д<'> =(+>,+>,-Ц >в> (+1 +1 Ц (7> ( 1 +1 +Ц у"' =(-,+,+) >в>(1+1+Ц у<'> =(+1,-1,+Ц д>'> =(+»,— ,+ц д" > = (+1, +1, - Ц у>О =( — >,+1,+ц у>о> = ( 1, а, 0) Может показаться неудобным нумеровать данные векторы с конца так, чтобы д>~> появлялся первым, а у(о> --- последним, но этот нестандартный способ нумерации более удобен при разработке теории.
Для поиска оптимального метода неплохо сначала вывести рассортированный результат и представить себе, как его можно распределить на различные ленты (т. е. выполнить операцию, обратную слиянию). Затем следует распределить то, что получилось, и т. д., рассматривая последовательные распределения п(~>, ор>, о(~>,... в порядке, обратном тому, в котором они в действительности появляются в результате слияний в ходе сортировки. Фактически именно этот подход использовался нами прн анализе многофазного и каскадного слияний. Каждая схема слияния, очевидно, имеет векторное представление.
И обратно, как легко видеть, последовательность векторов убв>... ур> у(о> соответствует реальной схеме слияния тогда и только тогда, когда выполняются следующие три условия: 1) вектор ущ> является единичным; й) ровно одна компонента вектора уб> равна -1; все остальные компоненты равны Оияи+1,ти>в>1; й>) все компоненты вектора уй> + -. + ур> + у(о> неотрицательны, т ) ( > 1. Информацию о схеме слияния можно представить в виде дерева. Мы строим дерево с одним внешним "листовым" узлом для каждой начальной серии и с одним внутренним узлом для каждой серии, полученной в результате слияния. Потомками любого внутреннего узла являются образующие его серии.
Каждый внутренний узел помечается номером шага, на котором была образована соответствующая серия, при этом шаги нумеруются в обратном порядке, как в векторном представлении. Кроме того, ребра непосредственно над каждым узлом помечаются именем ленты, на которой находится данная серия. Например, три приведенные выше схемы имеют представления в виде дерева, изображенные на рис.
76, если мы назовем лен~ы А, В, С, 1>, а не Т1, Т2, ТЗ, Т4. Это удобное и наглядное представление многих существенных свойств схемы слияния. Например, если серия на уровне О дерева (корень) должна быть восходящей, то серии на уровне 1 должны быть нисходящими, серии на уровне 2— восходящими и т. д. Некоторая начальная серия является восходящей тогда и только Сбалаясяроаанная ~Т=4, 5=8) Каскадная (Т=4, о=14) Мяогофазная [т=з, й=1з) Рнс. 76. Представления трех схем слияния н ннло деревьев. тогда, когда соответствующий внешний узел находится на уровне с четным номером.
Далее, суммарное количество начальных серий, обрабатываемых при слиянии (не включая начальное распределение), в точности равно длине внешнего пугни дерева, поскольку каждая начальная серия на уровне й обрабатывается ровно я раз. Любая схема глияния имеет представление в виде дерева, но не каждое дерево определяет схему слияния.
Дерево, внутренние узлы которого помечены числами от 1 до т и ребра которого помечены именами лент, изображает правильную схему слияния с обратным чтением тогда и только тогда, когда а) никакие два ребра, смежные с одним внутренним узлом, не имеют одного и того же имени ленты; Ь) если 4 > у и если А есть нмя ленты, то дерево не содержит конфигурации с) если 1 < у < Й < ( и если А .— имя ленты, то дерево не содержит таких пар (4) А и А илн А н А Условие (а) очевидно, так как вводные и выводные ленты слияния должны быть различны; утловие (Ь) также очевидно. Условие "непересечения" (с) отражает характерное для операций обратного чтения ленты ограничение "последним включается — первым исключается".
Серия, образованная на шаге к, должна быть удалена прежде серии, сформированной ранее на той же ленте; следовательно, конфигурации (4) невозможны. Нетрудно проверить, что любое помеченное дерево, удовлетворяющее условиям (а), (Ь) и (с), действительно соответствует некоторой схеме слияния с обратным чтением. Если имеется Т накопителей на магнитной ленте, то из условия (а) следует, что степень каждого внутреннего узла равна Т вЂ” 1 или меньше. Присвоить подходящие метки всем таким деревьям не всегда возможно, :например, если Т = 3, то пе существует схемы слияния с деревом вида Такая форма дерева позволила бы найти оптимальную схему слияния, если бы можно было соответствующим образом присвоить номера шагов и номера лент, поскольку это единственное дерево с минимальной длиной внешнего пути среди деревьев, имеющих четыре внешних узла.
Но в силу симметрии структуры этого дерева имеется, по существу, только один способ пометить его, соблюдая условия (а) и (Ъ): Однако при этом нарушается условие (с). Дерево, которое можеш быть помечено в соответствии с упомянутыми уг юанями с использованием Т или меньше имен лент, называется Т-йуо-деревом. Другой способ охарактеризовать все помеченные деревья, которые могут возникнуть из схемы слияния, состоит в рассмотрении метода "выращивания" всех подобных деревьев.
Начнем с некоторого имени ленты, скажем А, и с ростка дерева Шаг 1 роста дерева состоит в выборе различных имен лент В, Вы Вз,..., Вь и дальнейшей замене всего образованного узла, соответствующего В, (7) от до Правило "последним образован — первым растет" в точности описывает способ построения представления в виде дерева непосредственно из векторного представления. Определение строго оптимальной Т-ленточной схемы слияния, т.
е. дерева, имеющего минимальную длину пути среди всех Т-!!(о-деревьев с данным числом внешних узлов, кажется весьма трудной задачей. Следующая неочевидная схема, например, представляет наилучший способ слияния семи начальных серий с помощью четырех лент и считывания в обратном направлении: (8) По существу, для достижения оптимума необходимо однопутевое слияние! (См. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
