Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 47
Текст из файла (страница 47)
Поразрядная сортировка списка. две переменные-указателн: ТОРЯ н ВОТМЯ, О < 1 < ЛХ, н, как н в главе 2, предполагается, что ЫМК()ОС(ВОТМЯ)) зэ ВОТМЯ. (б) Н1. (Цнкл по к.) Вначале установить Р е- КОС(НМ), указатель на последнюю валясь. Затем выполннтыпагн Н2-Нб прн Й = 1, 2,,, р (шагн Н2-Нб составляют один "проход" — просмотр исходных данных) н завершить выполнение алгорнтма. Переменная Р будет указывать на запнсь с наименьшим ключом, 11МК(Р) .- - на запись со следующнм по величине ключом, ЫМК((.ТМК(Р)) — на следующую запись н т. д, Поле 11МК последней записи будет равно Л. Н2.
(Очнстнть стопки,) Пр 0 < г' < М установить ТОРЯ е- ЫС(ВОТКНИ) н ВОТИ [П +- Л. НЗ. (Выделять (с-1о цифру ключа.1 Пусть ККТ(Р) —. ключ запнсн, на которую указывает Р, — равен (ам аз,...,а„). Установнть ( +- ары э, к-ю младшую цифру этого ключа. Н4. (Откорректнровать связн.) Установить 1ТМК(ТОР[О ) +- Р н ТОРЯ е- Р.
НЬ. (Перейтн к следующей записи.) Еслн [с = 1 (первый просмотр) н если Р = 1.ОС(Н)) прн некотором у' ф 1, установнть Р +- ЬОС(Н, ~) н возвратиться к шагу ЙЗ. Если Й > 1 (не первый просмотр), то установнть Р +- ЫМК(Р) н возвратиться к НЗ, если Р ф Л. Нб. (Выполнять элгорнтм Н.) (Теперь все элементы распределены по стопкам.) Выполнять приведенный анже алгоритм Н, который "сцепляет" отдельные стопки в один список, подготавлнвая нх к следукнцему просмотру. Установить Р +- ВОТМ [03, указатель на первый элемент объединенного спнгка (см.
упр, 3). 1 Алгоритм Н (Сцен.ление очередей). Из М данных очередей со связями, удовлетворяющнмн соглашениям алгоритма В., данный алгорнтм создает одну очередь, меняя прн этом не более Лт' связей. В результате ВОТМ [03 указывает на первый элемент н стопка 0 предшествует стопке 1 ..., стопка М вЂ” 2 предшествует стопке М-1. Н1. (Начальная установка.) Установнты' +- О.
Н2. (Указатель на вершину стопкн.1 Уствновнть Р е- ТОР [О. НЗ. [Следующая стопка.[ Увеличиты на 1. Если 1 = М, то установить [.1МК (Р) е- Л и завершить выполнение алгоритма, Н4. [Стопка пустау[ Если ВОТИ[13 = Л, возвратиться к шагу НЗ. Нб. [Сцепить стопки.] Установить [.1МК [Р) 4- ЗОТИН.
Возвратиться к шагу Н2. На рис. 33 показано содержимое стопок после каждого нз трех просмотров, выполняемых при сортировке наших Эб чисел с М = 10. Алгоритм ЕЕ очень просто запрограммировать в системе команд М1Х, если найти удобный способ изменения операции на шагах НЗ и 3[б от одного просмотра к другому.
В следующей про- грамме зтого удалось достичь, не жертвуя скоростью внутреннего цикла, путем предварительной записи двух команд в тело программы, Заметим, что ТОРЫ и ВОТМ [1) можно упаковать в одно слово. ТОР [03 ТОР [13 ТОР [23 ТОР ЕЗ) ТОР Е43 ТОР ЕБ) ТОР [63 ТОР [7] ТОР[В) ТОР [93 ВОти[03 ВОтиС13 ВОтмЕ23 ВОткСБ) ВОтк[43 ВОтм[б) ВОти[63 ВОти[73 ВОтиСВ] ВОтиЕ93 ТОР [03 ТОР С1) ТОР [23 ТОРЕЗ) ТОР [43 ТОР ЕБ) ТОР ЕБЭ ТОР [73 ТОР СВ] ТОР Е93 ВОТК[03 ВОТИС13 ВОТМЕ23 ВОТИ[3) ВОТИ[43 ВОТИЕБ) ТОР[43 ТОРРО ВОТИ[63 ВОТИ[73 ВОТИС63 ВОТИ[9) ТОР[63 ТОР[73 ТОР[В) ТОР [9Э ТОР СОЭ ТОР ОО ТОР Е23 ТОР Ез) ВОТИ[03 ВОТКС13 ВОТИЕ23 ВОТМ[З) ВОТИЕ43 ВОТМЕБЭ ВОТИ[63 ВОТИЕТЭ ВОТИ[6) ВОТИ[93 Рис.
ЗЗ. Поразрядная сортировка с использованием связного распределения памяти [по- казано содержимое всех десяти стопок после каждого просмотра). Программа Н [Поразрядная сорязироека списков). Предполагается, что исходные ключи в ячейках по адресу от 1МРОТ+1 до 1МРОТ+М содержат р = 3 компоненты нз.х мз.
= з~зн з. 1 1в ь-?. 3 22. Очистить стопки, ЗЛХ ЬОС(ВО?НИ) ЗМ -+ ТОРИ Зм ВО?НИ +- л. ЗЛХ ЗМ М>в>О. 3 3 Изменить команды на проходе А 3 3 Время выполнения программы Н равно 32йт + 48Ы + 38 — 4Е, где Лг — число псходных записей, М вЂ” основание системы счисления (число стопок), а Š— число встретившихся пустых стопок. Сравнение с другимн программами, построенными (ох, ош оз), храняшнеся в полях (1: 1), (2:2) и (3: 3) соответственно. (Таким образом, считается, что значение ЛХ меньше или равно размеру байта компьютера М?Х.) В поле (4:5) каждой записи хранится свхгзь 1?МК. Пусть ТОР[11 — = Р11ЕБ+ х(1:2) и ВОТН[в) = Р1[ЕБ+ в(4:5) при О < х < М.
Удобно указывать в поле связи положение относительно адреса 1МРОТ, так что 1ОС(ВОТН [х) ) = Р1ЬЕБ + х — 1МРОТ. Чтобы избежать появления отрицательных связей, нужно расположить таблицу РП.ЕЯ после таблицы 1МРОТ. Значения индексных регистров таковы: г11 вв Р, г12 гй х, г13 = 3 — Й„г14 = ТОРИ. Во время выполнения алгоритма Н г12 = в' — М. 01 11МК ЕОО 4: 5 02 ТОР ЕОО 1: 2 08 БТАНТ ЕМТ1 М 04 ЕМТЗ 2 06 2Н ЕНТ2 К-1 06 ЕМТА РП.ЕЯ-?КРОТ,2 07 ЯТА Р1155,2(ТОР) 08 БТЕ РП.ЕБ,2(1.1МК) 00 ОЕС2 1 10 22ММ е-4 11 1ОА НЗБЫ,З 18 БТА ЗР 18 ЫА НББМ, 3 14 ЯТА БР 16 ЗН [?2)2 1МРОТ, 1(З т 3) ) НЗ. Н ечь 1х-ю н г ключа. 16 4Н Ы4 Р11,55,2(ТОР) 3?з' Н4.
Отко ектн вать связи. 17 ЯТ1 1МРОТ,4(1?МК) 3)з' 1?МХ(ТОР[вО) +" Р 18 ЯТ1 Р?153,2(ТОР) 31в" ?ОР[П +- Р. 10 5Н [ОЕС1 1) НЛ Пе ейтя коле ю ейзалясл, 20 11МЗ ЗВ Здт Перейти к шагу НЗ, если конец прохода. 81 БН ЕММ2 Н 3 Н6, Выполнять алто ягм Н. 22 ЗНР 7Р 3 Перейти к шагу Н2, если в х- О, 88 НЗЯМ Ы2 1МРОТ,1(1: 1) Лт Команды для шага НЗ, если А = 3.
26 ?.О2 1МРОТ,1(2т2) Ж Команды для шаха НЗ, если й = 2. 26 ??)2 1МРОТ,?(3:3) Хзт Команды для шьга НЗ, если й = 1. НО й5ЯМ Ы1 1МРОТ, 1(1.1МК) Лт Команды для шага НЗ, если А = 3. 27 151 1МРОТ,10.?МК) ЛХ Команды для шага НЗ, если А = 2. 28 ОЕС1 1 1в' Команды для шага вь5, если Л = 1. ь вв звз зтзвв+з.зтзтззт зк- 3 щ, ~в а~.
80 ?АЗ 8Р .ЗМ вЂ” 3 Перейти к шагу НЗ, если ВО?НИ = Л. 81 втз твен.зтзтззт зк-з-в нз знзз~~, 82 7Н 1О1 Р1ЬЕБ+Кз2(ТОР) ЗМ вЂ” Е Н2. Указатель на ве шнн стопки. 88 ЗН 1МС2 1 ЗЛХ НЗ. Сле ю ая стопка. в+- в+ 1. 84 82МЗ 9В ЗМ Перейти к шагу Н4, если в ф М. 86 ЯТЕ 1МРОТ, 1(1.1МК) 3 1?МК(Р) +- Л. 86 Ы1 РП.ея(11мк) 3 р +- ВО?К[О), 87 ОЕСЗ 1 3 88 13ММ 28 3 Цикл для 1 < А < 3. $ на основе аиалогичиых предположений (программы 5,2.1М и 5.2.41 ), говорит явно в пользу программы К.
Время вь<павпения р.проходного варианта программы К равно (Пр — 1)Х + 0(рЛХ) машинных циклов; критический фактор, влияющий иа время выполнения, — виутренний цикл, который содержит пять обращений к памяти и один переход. Для типичного компьютера М = Ь' и р = (<Я, где 1 — - число цифр в ключах, представленных в системе счисления с осиованием Ь. С ростом г убывает р, так что можно воспользоваться нашими формулами для определения мниилучшегом значения г.
Единственная переменная величииа в формуле для времени выполнения— это Е (число пустых стопок, обиаружеииых на щие Н4). Предположим, что все М~ последовательностей цифр М-ичной системы счисления равновероятны. При анализе "покер-теста" в разделе 3.3.2В было показано, как вычислять вероятность того, что при каждом просмотре встретится ровно М вЂ” г пустых стопок.
На каждом проходе она равна М(М вЂ” 1) ... (Лр — г+ 1) г Л< ) ЛХ <м <' где ( „~ — число Стирлинга второго рода. Согласно упр. 5 1 ° <<< я=( ° <и<-м,оэ, ° м(<- — ) р, <м-«~). «< МУ' В последние годы появляется все больше компьютеров с конвейерной (р<рсйпе) и магистральной (пцшЬег-сгипсй<пй) архитектурами. Зги машины имевэт несколько арифметических устройств и схему "опережения'", так что обращения к памяти и вычисления могут в значительной степени совмещаться во времени. Но эффективность таких компьютеров заметно снижается при наличии условных перв- ходов, если только эти переходы ие происходят почти всегда в одном и том же направлении.
Внутреиний цикл поразрядной сортировки хорошо приспособлен для таких машин, поскольку это простое итеративное вычисление -- типичное мпережевывание чисел". Поэтому дл,а комоьюглеров с магвсшрольной архип<сатирой а<ешод яоразрлдной сортировки обычно лоллеп<ел наиболее э<Лфеьэпиоимм из всех известных методов оиутренней сор<пирооки при условии, что <<' не слишком малб и ключи не слишком длинные. Разумеется, если клк<чи уж очень длинные, поразрядная сортировка ие так эффективна. Представьте себе, например, что нужно рассортировать 60-разрядиые десятичные числа за 20 проходов поразрядной сортировки, используя ЛХ = 10э. Очень мало пар чисел будет иметь одинаковые ключи в первых 9 разрядах, так что первые 17 проходов выполнятся почти впустую.
При анализе обменной поразрядной сортировки мы обнаружили, что вовсе иеобязательно проверять много битов ключей, если просматривать их не справа налево, а слева направо. Поэтому давайте возвратимся к поразрядной сортировке, при которой ключи просматриваются, начиная со старших цифр (СЦ), а не с младших цифр (ЛЦЦ. Мы уже отмечали, что идея СЦ-поразрядной сортировки приходит в голову естествениым образом. В самом деле, нетрудно понять, почему при сортировке почты в отделениях связи пользуются имеиио этим методом. Большое количество писем можно рассортировать по отдельным мешкам, соответствующим географическим областял<. Теперь в каждом мешке содержится меньше писем, когорые Х = 100 1000 10000 100000 1000000 10г 10э Наилучшее М = 32 128 512 1024 8192 2гэ 2'т Наилучшее р = 2 2 2 2 2 2 2 д(Х) = 19-3 18.5 18.2 18.1 18.0 18.0 18.0 Здесь д(Х) — среднее число обращений к памяти на один сортируемый 10э 2)э 2 18.0 элемент 2рЛЛ Х вЂ” 1 Нм 6(Х) -„+ 8+ + Х 2ЛУг Х ' (8) эта величина ограничена при Х -э со, если взять р = 2 и М > и'Х, так что среднее время сортировки — 0(Х), а не Х 1о8 Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
