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