Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 69
Текст из файла (страница 69)
б5 будут представлены узлом Х(5] с полями КЕ1 = 170, 1.ОБА = Ее + 9с (адрес внешнего узла с номером 21), РЕ = 5е + 8с, Р1 = Те + 2с. Значения в полях РЕ и Р1 являются константами; таким образом, строго говоря, нет необходимости хранить их в явном аиде. Однако иногда на начальной фазе внешней сортировки для быстрой работы с устройствами ввода-вывода выгоднее хранить зту изоыточную информацию, чем вычислять ее каждый раз заново.
Во многих коммерческих приложениях входные данные нельзя считать полностью случайными — в них уже существует определенный порядок. Следовательно, серии, порождаемые выбором с замещением, преимущественно содержат больше чем 2Р записей. В дальнейшем мы увидим, что время, необходимое для внешней сортировки методом слияния, в значительной степени зависит от количества серий, порождаемых начальной распределительной фазой, так что выбор с замещением становится особенно привлекательным. Другие способы внутренней сортировки порождали бы примерно вдвое больше начальных серий, поскольку размеры оперативной памяти ограничены. Теперь детально рассмотрим процесс создания начальных серий методом выбора с замещением.
Следующий алгоритм принадлежит Джону Р. Уолтерсу (ЛоЬп В. %а)1егв), Джеймсу Пэйнтеру (Липез Рашгег) и Мартину Залку (Магйп Еа!Е), которые использовали его в программе сортировки методом слияния для компьютера Рййсо 2000 в 1958 году. Алгоритм включает интересный способ начального формирования дерева выбора и разделения записей, принадлежащих разным сериям, а также вывода последней серии по единообразной, сравнительно простой логике. (Надлежащая обработка последней серии, порожденной методом выбора с замещением, оказывается довольно сложной; блок, осуществляющий эту обработку, часто бывает камнем преткновения для программиста.) Основная идея заключается в том, чтобы рассматривать каждый ключ как пару (Я, К), где К вЂ” первоначальный ключ, а 5 — номер серии, которой принадлежит данная запись.
Мы получим выходную последовательность, порожденную методом выбора с замещением, если лексикографически упорядочим зти расширенные ключи (5 считается старше К). В приведенном ниже алгоритме для представления дерева выбора используется структура данных, состоящая из Р узлов. Предполагается, что т-й узел Х(~] содержит с слов, начинающихся с 1,0С(Х(Я) = Ье + су', 0 < 1 < Р.
Он представляет квк внутренний узел с номером у, так и внешний узел с номером Р+ 1' (см. рис. 63). В каждом узле имеется несколько полей: Рис. 66. Получение начальных серий методом выбора с замещением. Алгоритм К (Выбор с замео4ениам). Этот алгоритм (рис, 66) считывает записи последовательно из входного файла и записывает их последовательно в выходной файл. производя НИАХ серий длиной Р или больше (за исключением последней серии). Имеется Р > 2 узлов Х(0]...., Л'(Р— 1] с полями, описанными выше. Н1.
(Начальная установка.] Установить НИАХ +- О, КС < — О, ЕАЯТКЕТ вЂ” оо, Ц '- ЕОС (Л [0]) и КЦ <- О. (КС вЂ” номер текущей серии, а ЕАЯТКЕХ вЂ” ключ последней выведенной записи. Начальное значение ЕАЯТКЕТ должно быть больше любого возможного ключа; см. упр. 8.) Для О < ) < Р, если обозначить з = 1.0С(Л Ы), начальное содержимое Л ]Я установить следующим образом: КИ(У) +- 0; Р1(о) +-10С(Л ((Д2]]). 1.0ЯЕК(Ю) +- 2; РЕ(о) +- (ОС(Х]((Р+ ))/2]]); (Установка ьОЯЕКИ) и КИ(0) представляет собой искусственный способ образования начального дерева путем рассмотрения фиктивной серии с номером О, которая никогда не выводится.
Это — своего рода трюк; см. упр. 10.) В2. (Конец"серииу] Если КЦ = КС, то перейти к шагу ВЯ, (В противном случае КЦ = КС+ 1 и обработка серии с номером КС завершена. Здесь следует выполнить те специальные действия, которые соогветптвуют схеме слияния для последующих зтапов сортировки.) Если ВЦ > НИАХ, то выполнение алгоритма завершено„в противном случае установить КС ь- КЦ. В,Я.
(Вывод вершимы дерева.) (Сейчас Ц указывает на "чемпиона" и КЦ вЂ” номер его серии.) Если КЦ ф О, то вывести НЕСОКО(Ц) и установить |.АЯТКЕТ < — КЕТ (Ц). 1ь4. (Ввод новой записи.] Если входной файл исчерпан, установить НЦ +- НИАХ+ 1 и перейти к шагу )сб. В противном случае поместить новую запись из входного файла в НЕСОКО(Ц), Если КЕТ(Ц) < 1.АЯТКЕТ (т. е. зта запись не принадлежит текущей серии), то КЦ +- КЦ+ 1, и теперь, если ВЦ > НИАХ, установить НИАХ с- ВЦ.
Нб. ]Подготовка к изменению.] (Сейчас Ц указывает на новую запись с номером серии НЦ.) Установить Т <- РЕ(Ц). (Т -- переменный указатель, который будет двигаться по дереву.) Кб.(Установка нового проигравшего.) Если Кй(Т) < Кц или если КИ(Т) = Кц и КЕТ(ЕОЕЕК(т) ) < КЕТ(Ц), то поменять местами ЕОБЕК(Т) +Ф Ц, Кй(Т) ++ КЦ. (В переменных Ц и КЦ запоминается текущий победитель и номер его серии.) К7. (Сдвиг вверх.) Если Т = ЕОС(Х(1)), то вернутьгм к шагу К2; в противном случае Т < — Р1(Т) и следует вернуться к В.б.
8 В алгоритме К говорится о вводе и выводе записей по одной, тогда как практически лучше считывать и записывать отмосительно большие блоки записей. Следовэ; тельно, на самом деле за кулисами прячутся буфера ввода и вывода; их присутствие в памяти приводит к уменьшению значения Р. Это будет пояснено в разделе 5.4.6. вПреобразомамме серий с задержкой. В работе К. Я, 01пвпюге, САСИ 8 (1965), 48, предложено интересное усовершенствование метода выбора с замещением, использующее понятие, которое будем называть сглепенью свободы. Как мы видели, в каждом блоке записей, находящемся на ленте в составе серии, содержатся записи в порядке неубывания.
тек что первый элемент — наименьший, а последний — наибольший, В обычном процессе выбора с замещением наименьший элемент каждого блока в некоторой серии всегда не меньше наибольшего элемента в предыдущем блоке данной серии, Это соответствует "первой степени свободы". Дянсмор предложил ослабить такое условие до кш степеней свободы'"; новое условие ие требует, чтобы наименьший элемент каждого блока был не меньше, чем наибольший элемент предыдущего блока, но он нв должен бишь меньше наибольших элеменглов каких- либо гл предмоущих блоков щой же серии.
Записи в отдельном блоке упо1 ядочены, как и ранее, но соседние блоки не обязаны быть взаимно упорядоченными. Предположим, например, что в блоках содержится только по две записи. Приведенная ниже поглеловатечьность блоков является серией с тремя степенями свободы: ( 08 50 ! 06 90 ) 17 27 ! 42 67 ! 51 89 ! (1) Следующий блок, который может быть частью этой серии, должен начинаться с элемента, не меньпгего, чем третий по порядку элемент множества (50, 90, 27, 67„89), считая от наибольшею, т. е.
не меньше 67. Последовательмость (1) не является серией с двумя степенями свободы, так как 17 меньше, чем 50 и 90. Серия с ш степенями свободы в процессе чтения на следующей фазе сортировки может быть преобразована таким образом, что для всех практических целей она будет серией в обычном смысле. Начнем с чтения первых гп блоков в т буферов и будем выполнять их гл-путевое слияние; когда один из буферов исчерпается, поместим в него (т + 1)-й блок, и т. д. Таким образом можно восстановить серию в виде одмой упорядоченной последовательности, поскольку первое слово каждого вновь считываемого блока должно быть больше последнего слова только что исчерпанного блока или равно ему (если оно не было меньше, чем наибольшие элементы каких-.чибо предшествующих ему пг блоков).
Этот метод преобразования серии, в сущности, является гп-путевым слиянием, использующим только одно устройство внешней памяти для всех входных блоков! Процедура преобразования действует, как сопрограмма, к которой обращаются каждый раз, когда нужно получить одму очередную запись серии. Можно в одно и то же время преобразовывать различные серии с различных устройств и с различными степенями свободы и сливать получающиеся серии.
Это, по существу, подобно тому, квк если бы процесс четырехпутевого слияния, рассмотренный в начале настоящего раздела, был представлен в виде нескольких процессов двухпутевого слияния, которые происходят одновременно. Такую остроумную идею трудно до конца проанализировать, но в работе Т. О. ВвреЫ, ВЕТ 16 (1976), 133-142, показано, как распространить нашу аналогию с работой снегоочистителя на этот случай и попучить соответствующую приближенную формулу. Как следует из выведенной формулы аппроксимации, длина серии будет равна примерно 7 2Р + (ш — 2)Ь ~ если 8 — размер блока и пт > 2.
Эти данные довольно хорошо согласуются с проведенными практическими экспериментами. Такое увеличение длины нельзя считать достаточным для компенсапди повышения июжности процесса. Но, с другой стороны, это может дать некоторые преимущества, когда существует возможность организовать довольно большое число буферов на второй фазе сортировки.
аНатуральный выбор. Другой путь увеличения длины серий, порождаемых выбором с замещением, бьш исследован в работе Ж. О. Ргавег, С. К. Рйопй, САСМ 15 (1972), 910-913. Изложенная авторами идея состоит в том, чтобы следовать алгоритму 11, кроме случая, когда в дерево включается новая запись, ключ которой меньше, чем 1,АЯТКЕ7. Тогда вывод направляется во внешний дополнительный буфер и считывается новая запись. Этот процесс продолжается до тех пор, пока в дополнительном буфере не окажется определенного количества записей Р'. Тогда остаток текущей серии выводится нз дерева, а элементы из дополнительного буфера используются в качестве исходных данных для следующей серии. Рассмотренный метод должен порождать более длинные серии, чем метод выбора с замещением, поскольку он "обходит" вновь поступаюпше "мертвые" записи, вместо того чтобы позволять им заполнять дерево; но ему требуется дополнительное время на обмен с дополнительным буфером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
