Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 27
Текст из файла (страница 27)
5.2-12, затратив дополиительио за чашиииых циклов.) Программа Я требует (9В+ 101т'-ЗА — 9) и, а так как В равно примерно 1№, то нетрудно видеть, что за счет дополнительного пространства памяти, выделенного для полей связи, удалось сэкоиомить примерно 22% времени выполнения. Тщательио продумав программу, можно сберечь еще 22% (см. упр. ЗЗ), ио время выполиеиия все же останется пропорциоиальиым №. Подведем итог сделанному. Мы начали с алгоритма Б — простого и очевидного алгоритма сортировки, который выполняет около -'№ сравнений и около ~1№ перемещений записей даииых в памяти.
Этот алгоритм был усовершенствовал путем использования бииариых вставок, при которых выполняется около )т !Е К сравнений и 1№ перемещений записей данных в памяти. Несколько измеиив структуру далиых, применив двухпутевые вставки, иам удалось сократить число перезаписей до -'№. При сортировке методом Шелла с убывающим смещением число еравиеиий и перезаписей снижается примерно до Хт' т1е для тех значений Ф, которые встречаются иа практике; при Л' -ь со это число можно сократить до порядка Ж(!ок Ж)х. Дальнейшее стремление улучшить алгоритм Б с помощью связкой структуры данных привело иас к методу вставки в список, который требует около 1№ сравиеиий, 0 перезаписей и 2К операций измеиеиия связи.
Можно ли объединить лучшие свойства этих методов, т. е. сократить число сравиеиий до порядка Х !она, как при бинарных вставках, и в то же время исключить перемещеиия записей в памяти, как при вставках в список? Ответ утвердительный — нужно перейти к древовидной структуре данных.
Такой вариант впервые был исследован в 1957 году Д. Дж. Уилером (П. 3. Жпее!сг), который предложил использовать двухпутевые вставки до тех пор, пока ие возникнет иеобходимость перемещать записи в памяти. Вместо операции перезаписи ои предложил вставлять указатель иа новую область памяти и рекурсивио применять ту же процедуру ко всем элемеитам, которые должны вставляться в эту иовую область памяти. Ориги- 061 08? 503 512 908 154 170 275 426 509 612 653 897 677 765 703 Рис. 13. Пример схемы Уялера для вставок э дерево.
нальный метод Унлера (см. А. 8. Поп81аэ, Со1пр. Х 2 (1959), 5] предполагал использование довольно замысловатой комбинации последовательной и связной памяти с узлами переменного размера; для тех шестнадцати чисел, которые используются в качестве примера неупорядоченной последовательности, таким способом было бы сформировано дерево, показанное па рнс. 13. Аналогичную, но более простую схему со вставками в бинарную древовидную структуру изобрел К. М. Вернере-Ли (С. М. Вегпегэ-(ле) примерно в 1958 году (см. Согпр. Х 3 (1960), 174, 184). Поскольку сам метод с использованием бинарного дерева и его модификации очень важны как для сортировки, так и для поиска, его подробное обсуждение мы отложим до раздела 6.2.2 главы 6.
Еще один путь улучшения метода простых вставок — попытаться вставлять несколько залисей одновременно. Если, например, имеется массив из 1000 элементов и 998 из них уже рассортированы, то алгоритм Я выполнит еше двэ просмотра массива (вставив сначала Яэээ, а потом )11000). Очевидно, можно сэкономить время, если сначала сравнить ключи К999 и К1аю и выяснить, какой из них больше, а затем вставить оба ключа за один просмотр массива. Комбинированная операция такого рода требует около 3Х сравнений и перезаписей (см. упр.
3.4.2-5) вместо двух просмотров, примерно по 1 Х сравнений и перезаписей каждый. Иначе говоря, обычно полезно "группировать" операции, которые требуют длительного поиска, чтобы можно бы.ю вьшолнить несколько операций сразу, Если довести эту идею до ее естественного завершения, то будет заново открыта сортировка посредством слияния, настолько важная, что ей посвящен отдельный раздел (5.2.4). Сортировка с вычислением адреса.
Ну уж теперь-то, несомненно, исчерпаны все возможные способы усовершенствования методов простых вставок! Но давайте подумаем еше. Представьте себе, что вам поручили расставить несколько дюжин книг на полке по фамилиям авторов, причем книги берутся с по:а в случайном порядке. Ставя книгу на полку, вы, естественно, попробуете прикинуть, где примерно она будет, в конце концов, стоять, н таким образом потенциально сократите число необхсдимых в будущем сравнений и перестановок.
Эффективность процесса повысится, если на полке будет немного больше места, чем это абсолютно необходимо. Такой метод для реализации компьютерной сортировки впервые предложили Исаак (13аас) и Синглтон (81пй!есоп) (см.,/АСМ 3 (1956), 169-174); он получил дальнейшее развитие в работе Тартера (Тагсег) и Кронмэла (КгошпаЦ [см. Ргос.
АСМ Маг'1 Сопб 21 (1966), 331 — 337). Сортировка с вычислением адреса обычно требует дополнительного пространства в памяти либо для того, чтобы оставить достаточно свободного места и не делать много лишних перемещений, либо для хранения вспомогательных таблиц, которые позволяли бы учитывать неравномерность распределения ключей. (См. сортировку методом подсчета распределения (алгоритм 5.20), которая является разновидностью сортировки с вычислением адреса.) Дополнительное пространство будет, по-видимому, использоваться наилучшим образом, если отвести его для полей связи, как в методе вставок в список. К тому же отпадает необходимость в выделении отдельных областей для ввода и вывода; все операции можно выполнить в одной и той же области памяти.
Основная цель — так обобщить метод вставок в список, чтобы работать не с одним списком, а с несколькими. Каждый список содержит ключи из определенного диапазона. Мы делаем важное предположение о том, что ключи распределены довольно равномерно и не скапливаются хаотически в отдельных областях значений. Множество всех возможных значений-ключей разбивается на М частей, и предполагается, что данный ключ попадает в данное подмножество с вероятностью 1/М.
Отводим дополнительную память для головных элементов М списков, а каждый список обрабатываем, как при простых вставках в список. Нет необходимости приводить здесь этот алгоритм со всеми подробностями. Достаточно вначале установить все головные элементы списков равными Л, для каждого вновь поступившего элемента предварительно решить, в какое из М подмножеств он попадает, после чего вставить его в соответствующий список, как в алгоритме Ь.
Чтобы проиллюстрировать этот метод в действии, предположим, что наши 16 ключей разделены на М = 4 поддиапззона: 0-249, 250 — 499, 500 — 749, 750-999. В процессе сортировки по мере того, как будут вставляться ключи Км Км ..., Кш, получатся следующие конфигурации. Пришли Пришли Пришли Всего 4 элемента 8 элементов 12 злемеятов Список 1: 061,087 061,087,170 061,087,154,170 061,087,154,170 Список 2: 275 275, 426 275,426 Список 3: 503, 512 503, 512 503, 509, 512, 653 503, 509, 512, 612, 653, 677, 703 Список 4: 897,908 897,908 765,897,908 (Программа М, описанная ниже, в действительности вставляет ключи в обратном порядке, Кш, ..., Кгь Км но окончательный результат тот же.) Благодаря ор~анизации в памяти структуры связных списков не возникает проблем, связанных с выделением памяти при изменении длины списка.
При желании в конце выполнения программы все списки можно объединить в один (см. упр. 35). Программа М (Вставка е несколько списков). При разработке этой программы сделано такое же предположение, как и в программе 1., но ключи должны быть яеошрицашельными, т. е. 0 < К ( (ВТТЕ812Е)з. В программе этот диапазон делится на Х равных частей посредством умножения каждого ключа на соответствующую константу. Головные элементы списков хранятся в ячейках от НЕАО+1 до НЕ30+И.
01 КЕТ ЕЦО 1: 3 08 Ь1МК ЕЦО 4:Б 08 ятйнт кита м 1 06 ЯТЗ НКАО,2 М НКАП(р) с — Л. 06 ОЕС2 1 М 06 12Р а-2 М>р>1. 07 ЕМТ1 М 1 1 ~- Ф. 06 2Н 1.ОА 1МРОТ, 1 (КЕТ) )х' 00 НОЬ -Н(1:З)- 17 гА <- (М К /ВТТЕЗТЕЕ~). 10 ЗТА а+1(1; 2) Л П ЕМТ4 0 Ж г14+- гА. И ЕМТЗ НКАО+1-1МРОТ,4 Ф д +- ЫС(МЕАП(гА) ). 13 ЬВА 1МРОТ,1 ж к +-Ку. ц Л(Р 4Р Л Переход иа установку р.
16 ЗН СИРА 1МРОТ,2(КЕУ) В +Ж вЂ” А !6 ЛЬЕ БР В+ Ф вЂ” А Переход на вставку, если К < К . 17 ЕМТЗ 0,2 В !В 4Н ЬВ2 1МРОТ,З(1.1МК) В+ )к и ь- 1ЛМК(7). 10 12Р ЗВ В + Х Переход, если не конец списка. 80 Бн Ят1 1мРОт,зО.1мк) 17 11мк(7) +- асс(В,). 81 ят2 1НРОт, 1(ьтмк) л пвк(10с(я ) ) 88 БН ВЕС1 1 Ф ЕУ 11Р 2В )7>8>1. Эта программа написана для любого значения М, но лучше зафиксировать М, положив его равным некоторому приемлемому значению; можно, например, положить М = ВТТЕЯ12Е, тогда головные элементы списков можно очистить с помощью одной-единственной команды МОЧЕ, а последовательность команд ОВ-11, реализующих умножение, заменить единственной командой ЬВЗ 1МРОТ,1(1:1).
Наиболее заметное отличие программы М от программы Ь состоит в том, что в программе М нужно принимать во внимание и возможность образования пустого списка, когда не надо делать сравнений. Сколько же времени мы экономим, имея М списков вместо однскот Общее время выполнения программы М равно 7В+31Х-ЗА+ 4М+2 машинных циклов, где М вЂ” число списков, )к' — число сортируемых записей, А и В равны соответственно числу правосторонних максимумов и числу инверсий среди ключей, принадлежащих каждому списку. (Анализируя этот алсоритм, в отличие от всех других в данном разделе, мы включаем в подсчет А и крайний справа элемент непустой перестановки, а не игнорируем его.) Мы уже проанализировали величины А и В при М = 1, когда их средние значения оказались равными соответственно Нл и 1( х ).
Согласно пре~~- положению о распределении ключей вероятность того, что данный список в конце сортировки будет содержать ровно и элементов, есть кбиномиальиая" вероятность (".Ия)" ('- Й" " Поэтому средние значения величин А и В в общем случае равны А, .=М~~~ ( )( — ) (1- — ) Н„; (14) В„„~=М~~ ( )( — ) (1 — — ) ( )/'2. Используя тождество которое представляет собой частный случай соотношения 1.2.6-(20), можно легко определить сумму в (16): (17) В упр. 37 определено стандартное отклонение для В, но суммирование в (15) вы- полняется сложнее, По теореме 1,2.7А получим (' )(М вЂ” 1) "Н„= (1 — — ) (Ни — (йМ)+с, и следовательно, Мз т 1 хи+1 А„, = М(Ни — 1пМ)+5, 0 < 5 < — (1 — — ), (18) Н+ ~ М/ (Эта формула практически бесполезна, если М м Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
