Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 68
Текст из файла (страница 68)
Кроме того, такая "концевая" запись часто служит удобным способюм разделения записей файла. В рассматриваемом процессе каждый шаг, кроме первого, заключается в замещении наименьшего элемента следующим элементом из этой же серии и в изменении соответствующего пути в дереве выбора. Так, на шаге 2 изменяются 3 узла, которые содержали 087 на шаге 1; на шаге 3 изменяются 3 узла, содержавшие 154 на шаге 2, и т. д.
Процесс замещения в дереве выбора одного ключа другим называется выбором с замещением. Мы можем по-разному рассматривать описанный процесс четырехпутевого слияния. С одной точки зрения он эквивалентен трем двухпутевым слияниям, выполняемым совместно, как сопрограммы; каждый узел дерева выбора изображает одну из последовательностей, используемых в процессах слияния. Дерево выбора, по существу, используется как приоритетная очередь с дисциплиной "наименьший из включенных первым исключается". Так же, как в разделе 5.2.3, можно было бы для реализации приоритетной очереди использовать не дерево выбора, а пирамиду. (Пирамиду, конечно, следовало бы организовать таким образом, чтобы иа ее вершине появился наименьший элемент, а не наиболыпий, обратив для этого порядок соотношения 5.2.3-(3),) Так как пирамида не имеет фиксированного размера, можно избежать использования ключа "оо"; слияние заканчивается, когда пирамида становится пустой.
С другой стороны, в приложениях, в которых используетсн внешняя сортировка, обычно имеют дело со сравнительно длинными записями и ключами, так что в пирамиду будут записаны вместо самих ключей указатели на них. Мы увидим ниже, что деревья выбора можно настолько удобно изображать с помощью указателей, что они (деревья), вероятно, в данной ситуации лучше пирамид. Дерево "проигравших'! На рис.
62 изображено полное бинарное дерево с 12 внешними (квадратными) узлами и 11 внутренними (круглыми); во внешних узлах записаны ключи, во внутренних — 'победители", если дерево рассматривать как турнир для выбора наименьшего ключш Меньшие числа над каждым узлом показывают традиционный способ распределения последовательных позиций памяти для полного бинарного дерева.
Чтобы определить новое состояние дерева выбора, изображенного на рис. 62, когда наименьший ключ 061 будет заменен другим ключом, нужно рассмотреть только ключи 512, 087 и 154, Если интерпретировать дерево как турнир, последние трн ключа будут представлять собой проигравших в матчах с игроком 061. Это Рис. 62. Турнир, в котором выбирается наименьший ключ; используется 1юлное бинарное дерево„узлы которого пронумерованы от 1 до 23. Рис. 63. Тот же турнир, что и иа рнс. 62„на показаны проигравшие, а не победители; чемшюн находится на самом верху.
наводит на мысль, что мы в действительности должны записать во внутренние узлы проикравшега в каждом матче, а не победителя. Тогда пнформация, необходимая для изменения дерева, будет легкодоступной, На рнс. 63 изображено то же дерево, что н на рис, 62, но вместо победителей в нем представлены проигравшие. Дополнительный узел с номером "О' добавлен. на вершине дерева для указания чемпиона турнира, Заметим, что каждый ключ, кроме ключа чемпиона, является проигравшим ровно один рзз ~см. раздел 5.3.3).
На практике внешним узлам в нижней части рис. 63 будут соответствовать весьма длинные записи, расположенные в памяти компьютера, а внутренним узлам — указатели на зги записи. Заметим, что Р-путевое слияние требует ровно Р внешних н Р внутренних узлов — по одному в соседних группах. Это наводит на мысль о возможности использовать известные эффективные методы распределения памяти. Нетрудно увидеть, каким образом можно применять дерево проигравших для выбора с замещением. Более детально мы обсудим этот алгоритм в настоящем разделе чуть позже.
Получение начальных серий посредством выбора с замещением. Технология выбора с замещением может использоваться на первой фазе внешней сортировки, если фактически выполнить Р-путевое слияние входных данных с самими собой. Б этом случае Р выбирается достаточно большим, чтобы заполнить, по существу, всю внутреннюю память. Каждая запись при выводе замещается очередной записью нз исходных данных. Если ключ новой записи меньше ключа выведенной записи, то мы не добавляем ее в текущую серию; в противном случае мы обычным образом включаем ее в дерево выбора, так что она образует часть серии, порождаемой в данный момент. Таким образом, каждая серия может содержать больше Р записей, хотя в любой момент в дереве выбора находится не более Р записей. В табл.
1 показан этот процесс для Р = 4; числа, заключенные в скобки, ожидают включения в следующую серию. Таблица 1 ПРИМЕР ЧЕТЫРЕХПУТЕВОГО ВЫБОРА С ЗАМЕЩЕНИЕМ Содержимое памяти Вывод Этот важный метод формирования начальных серий впервые был описан Х. Г. Сьювордом 1Е. Н. Беиагс), Мавгег'э ТЬев1В, 111рга) Сощрпгег 1 аЬогагогу Нерогс Б;232 (Мавэ, 1пэй..
о1 ТесЬпо!ойу, 1954), 29 — 30). Он привел соображения в пользу того, что если применять метод к случайным данным, серии, видимо, будут содержать более 1.5Р записей. Ту же идею предложил примерно в 1950 году А, И. Дуни (А. 1. Опшеу), который занимался разработкой в Епрпеейпй НеэелгсЬ Аззос(агез специального устройства для сортировки, но не опубликовал ее. Само название "выбор с замещением" было придумано Э. Г. Френдом [Е. Н. Рйепс),,7АСМ 3 (1956), 154), который заметил, что "ожидаемая длина порождаемой последовательности не поддается точной формулировке, но эксперкменты позволяют предположить, что разумной оценкой будет 2Р'! 503 503 503 503 (275) (275) (275) (275) (275) 275 275 087 087 170 897 897 897 (154) (154) 154 612 512 512 512 512 512 653 (426) (426) (426) 426 426 061 908 908 908 908 908 908 908 (509) 509 509 061 087 170 503 512 653 897 908 (Конец серии) 154 275 Рис.
64. Вечный снегоочиститель в своем нескончаемом цикле. Э, Ф. Мур (Е. Р. Мооге) предложил изящный способ доказательства того, что ожидаемая длина серии равна 2Р, проведя аналогию со снегоочистителем, движущимся по кругу (Г5. Расепг 2983904 (1961), со1ппше 3-4). Рассмотрим ситуацию, изображенную на рис. 64: на кольцевую дорогу равномерно падают снежинки и один снегоочиститель непрерывно убирает снег. Снег исчезает из системы„как только он выбрасывается на обочину. Точки дороги обознача~отся вещественными числами к, О < к < 1, снежинка, падающая в точку к, соответствует входной записи с ключом х, а снегоочиститель представляет собой вывод процесса выбора с замещением. Скорость снегоочистители обратно пропорциональна весу снега, который встречается на его пути, и ситуация вполне уравновешена, так что общее количество снежинок на дороге в точности равно Р.
Каждый раз, когда снегоочиститель проходит точку О, на выходе формируется новая серия. Интуитивно ясно, что система, поработав некоторое время, выйдет на установившийся режим, при котором снегоочиститель будет двигаться с постоянной скоростью (в силу круговой симметрии дороги).
Это означает, что в точке, в которой находится снегоочиститель, снег имеет постоянный вес, а впереди снегоочистителя зтот вес линейно уменьшается, как показано на рнс. 66. Отсюда следует, что количество снега, удаляемого за один оборот (а именно — длина серии), вдвое превосходит количество снега Р, присутствующего в любой момент. Рис, 6$. Поперечное сечение, показывающее переменный вес снега перед снегоочистите- лем, когда система находится в установившемся режиме. ключ, находящийся в данном внешнем узле; запись, находящаяся в данном внешнем узле (включая КЕУ как подполе); указатель на "проигравшего" в данном внутреннем случае; номер серии, содержащей запись, на которую указывает ЕОБЕК; указатель на внутренний узел, расположенный в дереве выбора выше данного внешнего узла; указатель на внутренний узел, расположенный в дереве выбора выше данного внутреннего узла, КЕУ— КЕСОКО— Р1— Например, при Р = 12 внутренний узел с номером 5 и внешний узел с номером 17 на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
