AOP_Tom3 (1021738), страница 60
Текст из файла (страница 60)
Предполагается, что в записяхНО..., 77р~ содержатся ключи Км..., Кя и поля связи Ьм..., Х,А, в которых могут храниться числа от — (д1+ 1) до (Х+ 1). В начале и в конце массива имеются искусственные записи Ьв н ЬА е~ с полями связи Во и Вл+м Этот алгоритм сортировки списков устанавливает поля связи таким образом, что записи оказываются связанными в порядке возрастания.
После завершения сортировки Ьв указывает на запись с наименьшим ключом; при 1 < Й < А1 связь Ьь указывает на запись, следующую за Кь, или Ьь = О, если К» — запись с наибольшим ключом (см. формулы 5.2.1 — (13)). сливаемые серии имеют длину 2ь, тем не менее никаких явных мер предосторожности на случай таких исключений предусматривать не приходится! (См. упр. 8.) Проверки ступенек вниз в прежнем алгоритме заменены посредством уменьшения переменных д и т и проверки равенства нулю.
Благодаря этому время выполнения на машине И1Х асимптотически приближается к 11А'!81У машинным циклам, что несколько лучше результата, которого удалось достичь в алгоритме Х. На практике имеет смысл комбинировать алгоритм Б с методом простых вставок. Вместо первых четырех просмотров алгоритма 5 можно методом простых вставок рассортировать группы, скажем, из 16 элементов, исключив таким образом довольно расточительные вспомогательные операции, связанные со слиянием коротких массивов. Как и в случае быстрой сортировки, такое комбинирование методов не влияет на асимптотическое время работы, но дает, тем не менее, немалую выгоду.
Рассмотрим теперь алгоритмы Х и Б с точки зрения выбора структур данных. Почему необходима память для 2л1, а не для 1У записей? Причина относительно проста; мы работаем с четырьмя списками переменного размера (два входных списка и два выходных списка в каждом просмотре); при этом для каждой пары последовательно распределенных списков используется стандартное понятие "совместный рост", обсуждавшееся в разделе 2.2.2.
Но в любой момент времени половина памяти не используется, и после некоторого размьппления становится ясно, что в действительности для наших четырех списков следовало бы воспользоваться связным распределением памяти. Если к каждой из 1У записей добавить поле связи, то все необходимое можно проделать, пользуясь алгоритмами слияния, которые выполняют простые манипуляции связями и совсем не перемещают сами записи.
Добавление 1У полей связи, как правило, выгоднее добавления пространства памяти еще для 1У записей; отказавшись от перемещения записей, можно сэкономить и время. Итак, рассмотрим следующий алгоритм. В процессе работы этого алгоритма записи Во и Вкд, выполняют роли головных элементов двух линейных списков, подсписки которых в данный момент сливаются. Отрицательная связь означает конец подсписка, о котором известно, что он упорядочен; нулевая связь означает конец всего списка. Предполагается, что Л' > 2. х!ерез "[Ь„[ +- р" обозначена операция "Присвоить Ь, значение р или — р, сохранив прежний знак Ь,'! Такая операция легко реализуется на компьютере И1Х, но, к сожалению, не на большинстве других моделей компьютеров. Нетрудно изменить алгоритм, чтобы получить сталь же эффективный метод для большинства других машин.
ЬХ. [Подготовить два списка.) Установить Ьо +- 1, Ьрд~.д д- 2, Ь, д — — [д+ 2) прн 1 < 1 < Л' — 2 и Ьк д д- Ьк +- О. (Созданы два списка, содержащих записи Вы Лз, Вы... и йз, Вд, Вв,... соответственно; отрицательные связи указывают, что каждый упорядоченный подсписок состоит всего лишь из одного элемента.
Другой способ выполнения этого шага, если принять во внимание упорядоченность, которая могла присутствовать в исходных данных, рассмотрен в упр. 12.) 12. [Начать новый просмотр.] Установить в +- О, г +- Х+ 1, р д — Ь„д +- Ь,. Если д = О, выполнение алгоритма завершается. [В процессе каждого просмотра р и д "пробегают" ло спискам, которые подвергаются слиянию; в обычно указывает на последнюю обработанную запись текущего подсписка, а 1 — на конец только что выведенного подсписка.) ЬЗ.
[Сравнение Кр. Кд.] Если Кр > Кд, перейти к шагу 16. Ь4. [Продвинуть р.] Установить [Ь,[ д- р, в д- р, р +- Ьр. Если р > О, вернуться к шагу ЬЗ. Ьб. [Завершить подсписок.] Установить Ь, д — д, и д- Ь Далее установить 1 д- д и д +- Ьд один или более раз, пока не станет д < О, после чего перейти к шагу Ь8. Ьб.
[Продвинуть д.] (Шаги Ьб и Ь? двойственны шагам Ь4 и Ь5.) Установить [Г,[ +- д, г д — д, д д — Ь,. Если д > О, вернуться к шагу ЬЗ. Ьт. [Завершить подсписок.] Установить Ь, +- р, в +- Ь Затем установить с д — р и р +- Ьр один или более раз, лака не станет р < О. Ь8. [Конец просмотра?] (К атому моменту р < О и д < О, так как оба указателя продвинулись до конца соответствующих лодспнсков.) Установить р +- — р, д д- — д. Если д = О, установить [Ь,[ д- р, [Ьд[ +- О и вернуться к шагу Ь2. В противном случае вернуться к шагу ЬЗ. ) Пример работы этого алгоритма приведен в табл.
3, в которой показаны связи к моменту выполнения шага Ь2. Па окончании выполнения алгоритма можно, пользуясь методам из улр. 5.2 — 12, перекомпоновать в памяти записи Км..., Врд так, чтобы их ключи стали упорядоченными. Нужно отметить интересную аналогию между слиянием списков н щшжением разреженных многочленов (см. алгоритм 2.2.4А). Напишем теперь И1Х-программу для алгоритма Ь„чтобы выяснить, столь ли выгодно оперировать списками с точки зрения скорости выполнения, как и с точки зрения расхода памяти? Программа Ь [Сордпировко посредсшвом слияния списков). Для удобства предполагается, что записи занимают адно слова, причем Ьу хранится в поле (О: 2) и Таблица 3 СОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 275 653 -10 — 11 7 -13 7 0 1 14 10 14 426 154 -12 — 13 9 12 12 10 12 10 1 б 170 897 — 8 — 9 5 -11 8 5 8 5 8 5 061 908 — б -7 3 — 1О 2 -13 2 0 2 0 509 612 677 — 14 -15 — 16 — 16 14 0 9 14 16 13 9 16 3 9 16 765 703 0 0 2 0 15 4 0 15 б 0 15 11 7 15 0 К» 5 51 2 5 4 4 1,1 4 503 -3 — 6 3 3 12 087 512 -4 -5 1 — 8 1 — 11 6 11 13 1ИРОТ + 1.
Состояние регистров таково: г11 = р, Х > 2. поле З=а, ЕЦ11 ЕЦО ЕЦУ Т ЕИТ1 ЕИИА БТА ОЕС1 11Р ЕНТА ЯТА ЕНТА БТА ЯТЕ ЯТЕ ЯИР ЬЮА СИРА ЯЬ ЯТ1 ЕИТЗ ЬВ1 11Р ЯТ2 ЕИТЗ ЕИТ4 ЬВ2 12Р ЯИР ЯТ2 ЕИТЗ ЬР2 12Р БТ1 ЕМТЗ ЕМТ4 ЬВ1 11Р ЕИИ1 Определение имен полей. ЬЬ По готовить ва списка. Ь, +- — (1+ 2). Ж вЂ” 2 > д > О. 1 4-1. Ь .„+-г. Ьп ~+-О, Ь,ч +- О.
Перейти к шагу Ь2. 13. С авненне К: К К, — в 712 =9, г1 01 09 АВБ1 09 КЕУ 04 Я ТАК О» 00 07 00 09 10 11 19 1Я 14 15 16 ЬЗЦ 17 ЬЗР 19 19 Ь4 90 91 99 ЯЭ ЬЯ 94 АЯ 96 97 МЯ 99 Ьб ЭО 91 ЭЯ ЭЯ 1.7 Я4 ЯЯ Эб 97 ЯЯ Ь8 (3: Я) по адресу 714:-1 гА = Кд 0:2 1:2 3:Я Н-2 2,1 П4РОТ,1(Ь) 1 4-3 1 1ИРОТ(Ь) 2 ТНРОТ+Н+1(Ь) 1НРОТ+И-1(Ь) 1МРОТ+И(Ь) Ь2 ТНРОТ,2 1НРОТ„1(КЕУ) Ьб 1ИРОТ,З(АВЯ1) 0,1 1ИРОТ,1( ) ЬЗР 1МРОТ,З(1.) 0,4 0,2 1НРВТ,2(Ь) Ь8 1ИРОТ,З(АВБ1.) 0,2 1НРОТ,2(1) ЬЗЦ 1ИРОТ,З(1.) 0,4 0,1 1МРОТ,1(Ь) ь-2 0,1 1 Д» — 2 Х вЂ” 2 Х вЂ” 2 19 — 2 1 1 1 1 1 1 1 С" + В' С С С' С' С' С' В' В' ПР П! р! В' Сп С" С" С" В" В" АУ П" Пп В Перейти к шагу Ьб, если Кд < Кр. ы~. и ° ° .
~»,Д а+-и р д- Ье. Перейти к шагу 1,3, если р > О. ЬЯ. Заве шить по список. Ь. +- 9. а 4-1. 1+ — 9. 9 д — Ьд. Повторить, если 0 > О. Перейти к шагу Ь8. ы пьь „° ~д~ а д — 9. 9+- Хд. Перейти к шагу ЬЗ, если 0 > О. 1,7.
Заве шить по список. Ь, +- р. а д — 1. 1 д — р. р+- Ь„. Повторить, если р > О. Ь8. Коп п осмот а? р < — -р. Время выполнения этой программы можно оценить при помощи методов, которыми мы уже не раз пользовались (см. упр. 13 и 14). В среднем оно равно приблизительно (10%!БА? + 4,92РР) машинных циклов с небольшим стандартным отклонением порядка эгей. В упр. 15 показано, что за счет некоторого удлинения программы можно сократить время примерно до 9Х)Е гг'. Итак, в случае внутреннего слияния связное распределение памяти имеет бесспорные преимущества перед последовательным распределением: требуется меньше памяти и программа работает на 10 — 20?г быстрее.
Аналогичные алгоритмы опубликованы в работах Е. 3. ЧЪог]гпш, 1ВМ Буясшпв Х 8 (1969), 189-203, и А. 1). ЯЪодаП, Сошр. Э. 13 (1970), 110-111. УПРАЖНЕНИЯ 1. ]21] Обобщите алгоритлг М для А-путевого слвлнил исходных массивов х,1 « ... хчщ при г' = 1, 2,,?г. 2. [М24] Считая, что все ("+") возможных расположений т элементов х среди п элементов у равновероятны, найдите математическое ожидание и стандартное отклонение числа выполнений шага М2 в алгоритме М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
