AOP_Tom3 (1021738), страница 67
Текст из файла (страница 67)
В этом случае Р выбирается достаточно большим, чтобы заполнитгь по существу, всю внутреннюю память. Каждая запись при выводе замещается очередной записью из исходных данных. Если ключ новой записи меньше ключа выведенной записи, то мы не добавляем ее в текущую серию; в противном случае мы обычным образом включаем ее в дерево выбора, так «го она образует часть серии, порождаемой в данный момент.
Таким образом, каждая серия может содержать больше Р записей, хотя в любой момент в дереве выбора находится не более Р записей. В табл. 1 показан этот процесс для Р = 4; числа, заключенные в скобки, ожидают включения в следующую серию. Таблица 1 ПРИМЕР ЧЕТЫРЕХПУТЕВОГО ВЫБОРА С ЗАМЕЩЕНИЕМ Содержимое памяти Вывод Этот важный метод формирования начальных серий впервые был описан Х. Г. Сьювордом (Е.
Н. Яеиагс), Мавгег'в ТЬемв, )з(811а! Сопйлцег ЬаЬогагогу Верогг П-232 (Мавв. 1пвп о1 ТесЛпо)оку, 1954), 29 — 30]. Он привел соображения в пользу того, что если применять метод к случайным данным, серии, видимо, будут содержать более 1.5Р записей. Ту же идею предложил примерно в 1950 году А. И. двуми (А.
1. Вппвеу), который занимался разработкой в Епя(пеег1пб ВевеагсЬ Аввос1а1ев специального устройства для сортировки, но не опубликовал ее. Само название "выбор с замещением" было придумано Э. Г. Френдом [Е. Н. Рг)епб, зАС81 3 (1956), 154), который заметил, что "ожидаемая длина порождаемой последовательности не поддается точной формулировке, но эксперименты позволяют предположить, что разумной оценкой будет 2Р". 503 503 503 503 (275) (275) (275) (275) (275) 275 275 087 087 170 897 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Р, проведя аналогию со снегоочистителем, движущимся по кругу [Г Я. РаСеп~ 2933904 (1961), со!цпшз 3-4).
Рассмотрим ситуацию, изображенную иа рис. 64: па кольцевую дорогу равномерно падают снежинки и один снегоочиститель непрерывно убирает снег. Снег исчезает из системы, как только он выбрасывается на обочину. Точки дороги обозначаются вещественными числами х, О < х < 1, снежинка, падающая в точку х, соответствует входной записи с ключом х, а снегоочиститель представляет собой вывод процесса выбора с замещением.
Скорость снегоочистителя обратно пропорциональна весу снега, который встречается на его пути, и ситуация вполне уравновешена, так что общее количество снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку О, на выходе формируется новая серия. Интуитивно ясно, что система, поработав некоторое время, выйдет на установившийся режим, при котором снегоочиститель будет двигаться с постоянной скоростью (в силу круговой симметрии дороги). Это означает, что в точке, в которой находится снегоочиститель, снег имеет постоянный вес, а впереди снегоочистителя зтот вес линейно уменьшается, как показано на рис.
65. Отсюда следует, что количество снега, удаляемого за один оборот (а именно — длина серии), вдвое превосходит количество снега Р, присутствующего в любой момент. :. Булущн» снег Рнс. 66. Поперечное сечение, показывающее переменный вес снега перед снегоочистителем, когда система нахадится в установившемся режиме. ключ, находящийся в данном внешнем узле; запись, находящаяся в данном внешнем узле [включая КЕ1 как подполе); указатель на "проигравшего" в данном внутреннем случае; номер серии, содержащей запись, на которую указывает ЕОБЕН; указатель на внутренний узел, расположенный в дереве выбора выше данного внешнего узла; указатель на внутренний узел, расположенный в дереве выбора выше данного внутреннего узла. КЕУ— НЕСОНО— ЕОЯЕН— НИ— РЕ— Например, при Р = 12 внутренний узел с номером 5 и внешний узел с номером 17 на рис.
63 будут представлены узлом Х[э] с полями КЕ1 = 170, ЕОБЕН = Ее + 9с [адрес внешнего узла с номером 21), РЕ = Ье + 8с, Р1 = ба + 2с. Значения в полях РЕ и Р1 являются константами; таким образом, строго говоря, нет необходимости хранить их в явном виде. Однако иногда иа начальной фазе внешней сортировки для быстрой работы с устройствами ввода-вывода выгоднее хранить эту изоыточную информацию, чем вычислять ее каждый раз заново. Во многих коммерческих приложениях входные данные нельзя считать полностью случайными — в них уже существует определенный порядок. Следовательно, серии, порождаемые выбором с замещением, преимущественно содержат больше чем 2Р записей. В дальнейшем мы увидим, что время, необходимое для внешней сортировки методом слияния, в значительной степени зависит от количества серий, порождаемых начальной распределительной фазой, так что выбор с замещением становится особенно привлекательным.
Другие способы внутренней сортировки порождали бы примерно вдвое болыпе начальных серий, поскольку размеры оперативной памяти ограничены. Теперь детально рассмотрим процесс создания начальных серий методом выбора с замещением. Следующий алгоритм принадлежит Джону Р. Уолтерсу [лойп В..
Жа!!егв), Джеймсу Пзйнтеру (Лашев Ра!пгег) и Мартину Залку [Маг!,ш Кайс), которые использовали его в программе сортировки методом слияния для компьютера Р!и)!со 2000 в 1958 году. Алгоритм включает интересный способ начального формирования дерева выбора и разделения записей, принадлежащих разным сериям, а также вывода последней серии по единообразной, сравнительно простой логике. [Надлежащая обработка последней серии, порожденной методом выбора с замещением, оказывается довольно сложной: блок, осуществляющий зту обработку, часто бывает камнем преткновения для программиста.) Основная идея заключается в том, чтобы рассматривать каждый ключ как пару [5, К), где К вЂ” первоначальный ключ, а 5 — номер серии, которой принадлежит данная запись. Мы получим выходную последовательность, порожденную методом выбора с замещением, если лексикографически упорядочим зти расширенные ключи [5 считается старше К).
В приведенном ниже алгоритме для представления дерева выбора используется структура данных, состоящая из Р узлов, Предполагается, что З-й узел Х[Я содержит с слов, начинающихся с ЕОС(Х[Я) = Ео + су, 0 < ~' < Р. Он представляет как внутренний узел с номером у, так и внешний узел с номером Р + у (см. рис. 63).
В каждом узле имеется несколько гюлей: Рис. 66. Получение начальных серий методом выбора с замещением. Алгоритм В. (Выбор с замещением). Этот алгоритм (рис. 66) считывает записи последовательно из входного файла и записывает их последовательно в выходной файл, производя НМАХ серий длиной Р или больше (за исключением последней серии).
Имеется Р > 2 узлов Х[0),..., Х[Р— 1] с полями, описанными выше. Н1. [Начальная установка.) Установить НИАХ < — О, НС е — О, ЕАБТКЕТ е — сю, Ц е— ЕОС(Х[0)) и НЦ +- О. (ВС вЂ” номер текущей серии, а ЕАЯТКЕТ вЂ” - ключ последней выведенной записи. Начальное значение ЕАБТКЕУ должно быть больше любого возможного ключа; см. упр, 8.) Для 0 < у ( Р, если обозначить Б = 1ОС(Х[у)), начальное содержимое Х[у) установить следующим образом: 1ОБЕН(У) <- т; РЕ(1) < — 10С(Х[[(Р+у)/2)]); НМ(Б) +- 0; Р1(Б) < — ЕОС(Л[Я2])). (Установка ЕОБЕН(Б) и НМ(1) представляет собой искусственный способ образования начального дерева путем рассмотрения фиктивной серии с номером О, которая никогда не выводится. Это — своего рода трюк; см.
упр. 10.) В.2. [Конец'серии?] Если ВЦ = ВС, то перейти к шагу ВЗ. (В противном случае НЦ = НС+ 1 и обработка серии с номером ВС завершена. Здесь следует выполнить те специальные действия, которые соответствуют схеме слияния для последующих этапов сортировки.) Если ВЦ > НМАХ, то выполнение алгоритма завершено; в протинном случае установить НС е- НЦ.
гьЗ. [Вывод вершины дерева.] (Сейчас Ц указывает на 'чемпиона" и ВЦ вЂ” номер его серии.) Если НЦ ~ О, то вывести БЕСОВО(Ц) и установить 1АБТКЕТ е- КЕТ(Ц). В.4. [Ввод новой записи.) Если входной файл ис серпан, установить НЦ + — НМАХ+ 1 и перейти к шагу В5. В противном случае поместить новую запись из входного файла в БЕСОВО(Ц). Если КЕТ(Ц) < ЕАБТКЕТ (т. е. эта запись не принадлежит текущей серии), то НЦ < — НЦ+1, и теперь, если НЦ > НМАХ, установить ВМАХ е — НЦ. Н5. [Подготовка к изменению.) (Сейчас Ц указывает на новую запись с номером серии ВЦ.) Установить Т < — РЕ(Ц).
(Т вЂ”. переменный указатель, который будет двигаться по дереву,) В6. )Установка нового проигравшего.) Если Нй(Т) ( НЦ илн если НИ(Т) = НЦ и КЕ7(РОБЕН(Т) ) < КЕТ(Ц), то поменять местами ЕОБЕН(Т) е+ Ц, Нн(Т) ~-> НЦ. (В переменных Ц и НЦ запоминается текущий победитель и номер его серии.) В7. (Сдвиг вверх.) Если Т = 1.ОС(Х~1)), то вернуться к шагу Н2; в противном случае Т < — Р1(Т) и следует вернуться к Вб.
$ В алгоритме 11 говорится о вводе и выводе записей по одной, тогда как практически лучше считывать и записывать относительно большие блоки записей. Следовательно, на самом деле за кулисами прячутся буфера ввода и вывода; их присутствие в памяти приводит к уменьшению значения Р. Это будет пояснено в разделе 5.4.6. ьПреобразование серий с звдержкай. В работе й.
Я. Пшвшогег САСМ 8 (1965), 48, предложено интересное усовершенствование метода выбора с замещением, использующее понятие, которое будем называть степенью свободы. Как мы видели, в каждом блоке записей, находящемся на ленте в составе серии, содержатся записи в порядке неубывания, так что первый элемент - — наименьший, а последний — наибольший. В обычном процессе выбора с замещением наименьший элемент каждого блока в некоторой серии вгегда не меньше наибольшего элемента в предььтущем блоке данной серии.
Это соответствует "первой степени свободы". Динсмор предложил ослабить такое условие до "т степеней свободы"; новое условие не требует, чтобы наименьший элемент каждого блока был не меньше, чем наибольший элемент предыдущего блока, но он гге должен быть меньше ноибольипгх элементов кагсихлибо ггг ггредмдйи(их блоков той же серии. Записи в отдельном блоке упорядочены, как и ранее, но соседние блоки не обязаны быть взаимно упорядоченными. Предположим, например, что в блоках содержится только по две записи. Приведенная ниже последовательность блоков является серией с тремя степенями свободы: ( 08 50 ( 06 90 ! 17 27 ! 42 67 ( 51 89 ) Следующий блок, который может быть частью этой серии, должен начинаться с элемента, не меньшего, чем третий по порядку элемент множества 150, 90, 27,67, 89), считая от наибольшего, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
