AOP_Tom3 (1021738), страница 63
Текст из файла (страница 63)
Возвратиться к шагу Н2. Ь На рис. 33 показано содержимое стопок после каждого иэ трех просмотров, выполняемых прн сортировке наших 16 чисел с М = 10. Алгоритм Н очень просто запрограммировать в системе команд М11, если найти удобный способ изменения операции на шагах НЗ и НЗ от одного просмотра к другому. В следующей программе этого удалось достичь, не жертвуя скоростью внутреннего цикла, путем предварительной записи двух команд в тело программы. Заметим, что ТОР[1] И ВОТМ [1] можно упаковать в одно слово. таР [а] таг [П там ОМ ТОР(з] ТОР(4] таР [ь] таР [ь! 7ОР(7] таР [В] таг[В] ватм(О] ватм[1] вати[2] ватм[з] ватм[4] ватм[ь] ватм[ь] Ватм[7] ватм[В] ватм[В] ТОР[а] ТОР(1] ТОР(2] ТОР[э] ТОР[4! ТОР(Б] ТОР(в] ТОР(7] ТОР [8! ТОР(9] ватм[о] ватм(1] ватм[г] воти[э] ватм[4] ватм[ь] ватм[в] ватм(7] ваги[В] Воти[О] д ТОР [а! ТОР [1] ТОР [2] ТОР (3] ТОР[4] ТОР[а] ТОР [в] ТОР (7] ТОР [В] ТОР [В] ВОТМ (О] ВОТМ [1] ВОТМ (2] ВОТИ [3] ВОТМ [4] ВОТМ (Б! ВОТИ [в] ВОТИ [7] ВОТМ [8! ВОТМ (9] Рис.
ЗЗ. Поразрядная сортировка с использованием связного распределения памяти (по- казано содержимое всех десяти стопок после каждого просмотра). Программа Н [Поразрядная сортировка списков). Предполагается, что исходные ключи в ячейках по адресу от 1ВРОт+1 до 1МРОт+м содержат р = 3 компоненты КИЛИ«ИМ 3. = (И 1 1 А «-1. 3 К2. Очистить стопки. Зм !ОС(ВОтибВ) ЗМ -+ ТОР[3) ЗМ ВОТИ[3) +- Л. ЗМ ЗАХ М > с > О.
3 3 Изменить команды на проходе А 3 3 Время выполнения программы Н равно 32ЛР+ 48М+ 38 — 4Е, где «31 — число исходных записей, М вЂ” основание системы счисления (число стопок), а Š— число встретившихся пустых стопок. Сравнение с друтими программами, построенными (аы аш аз), хранящиеся в полях (1: 1), (2: 2) и (3: 3) соответственно. (Таким образом, считается, что значение М меньше или равно размеру байта компьютера НТХ.) В поле (4:5) каждой записи хранится связь 51МК. Пусть ТОР[с): — Р1ЕЕЯ+ 3(1:2) и ВОТН[с) = РИ.ЕБ + с(4:5) при 0 < с < М. Удобно указывать в поле связи положение относительно адреса 1МРОТ, так что ЕОС(ВОТИ[с) ) = Р11.ЕЯ + с — 1МРОТ.
Чтобы избежать появления отрицательных связей, нужно расположить таблицу Р11.ЕБ после таблицы 1МРОТ. Значения индексных регистров таковы: тП И— В Р, г12 с— в с, г13 К— и 3 — А, г14 = ТОР[с). Во время выполнения алгоритма Н г12 = с — М.
01 С1МК ЕОО 4: 5 ОЭ ТОР ЕОО 1: 2 ОЯ БТАНТ ЕМТ! М 04 ЕМТЗ 2 Об 2Н ЕМТ2 Н-! Об ЕМТА Р1ЕЕБ-1МРОТ,2 07 ЯТА Р1ЕЕБ,2(ТОР) ОЯ ЯТ2 Р15ЕЯ,2(51МК) ОУ ОЕС2 ! 10 12ММ «'-4 11 ЬОА ЯЗЯМ,З 13 ЯТА ЗГ 1Э ЕОА НЯЯН,З Ц ЯТА 5Р 10 ЗН [ь02 1МРОТ, !(3:3)) КЯ. Изелечь А-ю си ключа. 1б 4Н 504 Р1ЕЕБ,2(ТОР) ЗЛ' К4. Огко екги оеать связи. 17 ЯТ1 1МРОТ,4(51МК) ЗЛ( ь1МК(ТОРЫ) +- Р. 1Я БТ1 Р1ЕЕЯ32(ТОР) ЗЛс ТОРЫ +- Р. 10 5Н [ОЕС! !) Кб Пе ейтнк еле ю ей записи. ЭО 11М2 ЗВ Здг Перейти к шагу КЗ, если конец прохода. 01 бН ЕММ2 М 3 Кб.
Выполнить алга итм Н. ЯЭ ЭМР 7Р 3 Перейти к шагу Н2. если 2 « — О. ЯЭ НЗЯН Ю2 1МРОТ, 1 (1: 1) 1(С Команды для шага КЗ, если 1« = 3. 04 Ь02 1МРОТ, 1(2: 2) Л( Команды дпя шага КЗ, если А = 2. Яб Ь02 1МРОТ,1(3: 3) 1«Р Команды для шага КЗ, если )с = 1. Эб К5ЯН 1.0! 1МРОТ,!(Е1МК) ЛР Команды для шага КЬ, если )с = 3. 07 50! 1МРОТ,!(1.1МК) Л( Команды для шага КЬ, если )с = 2. ЙЯ ОЕС! 1 ЛР Команды для шага КЗ.
если А = ! 33 ИН ~93 91139 И,И(11ИК( ИН-3 Н(. Р* ЭО ЭАЕ 8Г ЗМ вЂ” 3 Перейти к шагу НЗ, если Воти[3) = Л. Э1 313 13((Н,1(1(ИК( ИК-3-9 ~Нй Н, ЭЭ 7Н ЕО! Р1ьЕЯ+Н,2(ТОР) ЗМ вЂ” Е Н2. Указателыса ее шин стопки. ЭЭ 8Н 1МС2 1 ЗМ НЗ. Сссе гю ая стопка, 3+-3+ !. Э4 12М2 98 ЗМ Перейти к шагу Н4, если 3 ф- М.
Эб ЯТ2 1МРОТР!(Е[МК) 3 ь1МХ(Р) +- Л Яб 50! Р1ЕЕЯ (Е1МК) 3 Р +- ВОТИ [0) . Я7 ОЕСЗ 1 3 ЭЯ ЭЗММ 28 3 Цикл для 1 < А < 3. $ на основе аналогичных предположений (программы 5.2.1М и 5.2.4Б), говорит явно в пользу программы К. Время выполнения р-лраходнаго варианта программы К равно (11р — ЦХ+ 0(рМ) машинных циклов; критический фактор, влияющий на время выполнения, — внутренний цикл, который содержит пять обращений к памяти и адин переход. Для типичного компьютера М = 5" и р = (гуг ~, где 1 — число цифр в ключах, представленных в системе счисления с основанием 5.
С ростом г убывает р, так что можно воспользоваться нашими формулами для определения "наилучшего" значения г. Единственная переменная величина в формуле для времени выполнения эта Е (число пустых стопок, обнаруженных на шаге Н4). Предположим, что все М~ последовательностей цифр М-ичной системы счисления равновероятны. При анализе "покер-теста" в разделе 3.3.20 было показано, как вычислять вероятность того, что лри каждом просмотре встретится ровно М вЂ” г пустых стопок. На каждом проходе она равна М(М вЂ” Ц ... (М - г ч Ц ~ 1Ч) Мл ).
т,(' (6) где (~) — число Стирлинга второго рода. Согласна упр. 5 В последние годы появляется все больше компьютеров с конвейерной (р1ре11пе) и магистральной (пишЬег-сгинсЫпб) архитектурами. Эти машины имеют несколько арифметических устройств н схему "опережения", так что обращения к памяти и вычисления могут в значительной степени совмещаться во времени. Но эффективность таких компьютеров заметно снижается лри наличии условных переходов, если только этн переходы не происходят почти всегда в одном н том же направлении. Внутренний цикл поразрядной сортировки хоро~но приспособлен для таких машин, поскольку зто простое итеративное вычисление — типичное "пережевывание чисел".
Поэтому для компьютеров с магистральной архитектурой метод поразрядной сортировки обычно яоляется наиболее эффективным из всех известных лгетодов внутренней сортировки лрн условии, что Х не слишком малб и ключи не слишком длинные. Разумеется, если ключи уж очень длинные, поразрядная сортировка не так эффективна. Представьте себе, например, что нужно рассортировать 60-разрядные десятичные числа за 20 проходов поразрядной сортировки, используя М = 10з.
Очень мало пар чисел будет иметь одинаковые ключи в первых 9 разрядах, так что первые 17 проходов выоолнятся почти впустую. При анализе обменной поразрядной сортировки мы обнаружили, что вовсе необязательно проверять много битов ключей, если просматривать их не справа налево, а слева направо.
Поэтому давайте возвратимся к поразрядной сортировке, при которой ключи просматриваются, начиная со старших цифр (СЦ), а не с младших цифр (МЦ). Мы уже отмечали, что идея СЦ-норззрядной сортировки приходит в голову естественным образом. В самом деле, нетрудна понять, почему прн сортировке почты в отделениях связи пользуются именно этим методом.
Большое количества писем можно рассортировать по отдельным мешкам, соответствующим географическим областям. Теперь в каждом мешке содержится меныие писем, которые 100000 1000000 10т 10' 10э 1024 8192 2га 2ы 2гв 2 2 2 2 2 18.1 18.0 18.0 18.0 18.0 Дг = 100 1000 10000 Наилучшее М = 32 128 512 Наилучшее р = 2 2 2 д(Х) = 19.3 18.5 18.2 Здесь д(д') — среднее число обращений к памяти на один сортируемый элемент д(й') = 5р+ 8+ + 2РЛХ о' — 1 ХХн (В) эта величина ограничена при Т вЂ” > оо, если взять р = 2 и ЛХ > т/ДГ, так что среднее время сортировки — 0(Дг), а не Х 1ой М.
Данный метод является усовершенствованным вариантом метода вставок в несколько списков (программа 5.2.1М), который, по су~пеству, представляет собой случай р = 1. В упр. 12 приводится интересная процедура Мак-Ларена для окончательной перекомпоновки записей после частичной сортировки массива с помощью списков.
Если воспользоваться методами из алгоритма 5.2?) и упр. 5.2-13, то можно обойтись без полей связи; при этом в дополнение к памяти, занятой самими записями, потребуется всего 0(хуг7) ячеек. Если исходные данные распределены равномерно, то среднее время сортировки пропорционально Х. В. Добосевич (Ъ'. ?1ооояев4св) получил хороший результат при использовании СЦ-сортировки в отношения массивов значительной длины. Процесс распределения был построен таким образом, что для первых 5Х/2 стопок гарантировалось получе- можно независимо рассортировать по другим мешкам, соответствующим все более мелким районам.
(Разумеется, прежде чем продолжить сортировку писем, их можно переправить поближе к месту назначения.) Принцип "разделяй и властвуй" весьма привлекателен, и единственная причина его непригодности для сортировки перфокарт состоит в том, что большое количество стопок приводит к путанице.
Этим же явлением объясняется относительная эффективность алгоритма В (хотя здесь предпочтение отдается анализу, начатому с младших разрядов), потому что никогда не приходится работать более чем с М стопками н стопки приходится сцеплять всего р раз. С друтой стороны, нетрудно построить СЦ-поразрядный метод с помощью связного распределения памяти с отрицательными связими для обозначения границ между стопками, как в алгоритме 5.2 4?.
(см. упр, 10). Пожалуй, наилучший компромиссный выход указал М. Д. Мак-Ларен (М. П. Мас?,агеп) (3АСМ 13 (1966), 404-411), который предложил использовать МЦ-сортировку, как в алгоритме Н, но е применении к старшим разрядам. Это не будет полной сортировкой массива, но в результате массив станет почти упорядоченным, т. е. в нем останется очень мало инверсий, так что для завершения сортировки можно будет воспользоваться методом простых вставок. Наш анализ программы 5.2.1М применим и к этой ситуации, если ключи распределены равномерно, то после сортировки массива по старшим р цифрам в нем останется в среднем — 'Х(Л' — 1)М инверсий (см. формулу 5.2.1 — (17) н упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
