AOP_Tom3 (1021738), страница 105
Текст из файла (страница 105)
Рач!еэ) [Ргос. ХпзС. Е1есС. ЕпВшеегэ 103В, Вирр!етессС 1 (1956), 87 — 93]. В последующие годы было опубликовано еще несколько прекрасных обзоров: Р. А. Ве!1 [Сотр. Х 1 (1958), 71-77], Л. Б. Роиб!ав [Сотр. Х. 2 (1959), 1-9]; Р. Р. МсСгас!сеп., Н. чче!эв, Т. Ьее [Ргойгаппшпй Висбпевз СоссзХзигегв (Хесч Уог!с: %!!еу, 1959), СЬарсег 15, райев 298-332], 1. Р!осев [ХАСЛХ 8 (1961), 41-80], К. Е. 1чегвоп [А Ргодгатпшсй'Х сссяспсйе (Хесч 'сот!с %!!еу, 1962), СЬарсег 6, 176 — 245], С.
С. Со!1!еЬ [САСВХ 6 (1963), 194-201]. Т. Х. Н!ЬЬагс! [САСАХ 6 (1963), 206 — 213], М, А. Оое1в [Р481са! Сотрисег Слег'в Напс1Ьоо!с, ес!!сес! Ьу М. К!егег апс! О. А, Когп (Кесч Ъог!с: МсСгасч-Н!!1, 1967), СЬаргег 1.10, райеэ 1.292 .1.320]. В ноябре 1962 года ЛСМ организовала симпозиум по сортировке (большая часть работ, представленных на этом симпозиуме, опубликована в мае 1963 года в выпуске САСМ), Они дают хорошее представление о состоянии работ в этой области на то время. Обзор К. К, Готлиба (С. С. Оо!!!еЬ) о современных генераторах сортировки, обзор Т.
Н. Хиббарда (Т. К. Н!ЬЪагб) о внутренней сортировке с минимальной памятью и раннее исследование Дж. А. Хаббарда (С. 1!. НпЪЪагб) о сортировке файлов на дисках — статьи из этого сборника, заслуживающие наиболыпего внимания. За прошедший период были открыты новые методы сортировки: вычисление адреса (1956), слияние с вставкой (1959), обменная поразрядная сортировка (1959), каскадное слияние (1959), метод Шелла с убывающим смещением (1959), многофазное слияние (1960), вставки в дерево (1960), осциллирующая сортировка (1962), быстрая сортировка Хоара (1962).
пирамидальная сортировка Уильямса (1964), обменная сортировка со слиянием Бэтчера (1964). История каждого отдельного алгоритма прослеживается в тех разделах настоящей главы, в которых этот метод описывается. Конец 60-х годов нашего столетия ознаменовался интенсивным развитием соответствующей теории. Полная библиография всех работ, изученных авто!юм прн написании и подготовке первого издания этой главы и составленная с помощью Р. Л. Ривест (В,.
Ъ. Н!- чев!), приводится в Сотрибпй Яеч!еив 13 (1972), 283 — 289. Последние достижения. Со времени выхода из печати первого издания этой книги (1970 г.) появилось много сообщений об изобретении новых алгоритмов сортировки, однако почти все они являются вариациями уже известных алгоритмов. Быстрая сортировка на множестве ключей, которая обсуждалась и упр. 5.2.2-30, представляет собой прекрасный пример таких более новых методов. Другая тенденция в этой области, представляющая, скорее, теоретический интерес, — изучение адаптивных схем сортировки. Такие схемы по замыслу разработчиков должны гарантировать более быст!юе выполнение сортировки в случаях, когда входная последовательность удовлетворяет какому-либо из заранее установленных критериев.
(См., например, Н. Мапл!!а, 1ЕЕЕ Тгвлвас!!опв С-34 (1985), 318-325; У. Ев!!ч!!1-Савгго, 11, 1%пой, Сошрп!!пя Япгзеуэ 24 (1992), 441-476; С. Ъечсороп!ов, О. Ре!егввоп, Лоигпа) оГ А!8оп!!нва 14 (1993), 395-413; А. МоЯас, С. Еооу, О. Ре!егввоп, Бойи аге Ргасбсе Зг Ехрепепсс 26 (1996), 781-797.] Разительные изменения в характеристиках аппаратного обеспечения современных компьютерных систем стимулировали интерес к исследованию проблемы эффективности алгоритмов сортировки при совершенно новых критериях стоимости затрат. (См., например, обсуждение применения виртуальной памяти в упр.
5.4.9-20.) Эффект от применения аппаратной кэш-памяти при внутренней сортировке анализировался в работе А. ЪаМагса, Н. Е. Ъабпег, 7. А18ог!йшв 31 (1999), 66-104. Ее авторы пришли к выводу, что не следует включать шаг ц9 в алгоритм 5.2.211, если для сортировки используется компьютер с современной архитектурой, хотя для компьютеров традиционной структуры, каковым является наш 81Х, алгоритм в прежнем виде вполне работоспособен. Вместо того чтобы завершать быструк> сортировку с помощью метода прямых вставок, предлагается, что, по мнению авторов, значительно лучше, заранее сортировать короткие подмассивы, сохраняя их ключи в кэш-памяти.
А что можно сказать о нынешнем состоянии в области сортировки болыпих массивов данных? Одним из распространенных тестов для сравнительной оценки различных средств решения такого рода задач с 1965 года стала сортировка миллиона 100-символьных записей с равномерно распределенными случайными 10-символьными ключами. Предполагается, что исходная последовательность и результат должны храниться на диске, в целью является минимизация времени обработки, включая время загрузки н запуска программы. В работе Н. С.
Акагв'а1, ЯСМОО Весогс( 25, 2 (Липе, 1996), 240- 246, описан эксперимент, проведенный на компьютере 1ВМ В5/6000, модель 39Н, в котором используется процессор с В1ВС-архитектурой. Методом поразрядной сортировки обрабатывались файлы, распределенные между восемью дисками, и задача была решена за 5.1 с.
В подобных экспериментах узким местом является скорость ввода-вывода. Процессору для решения этой задачи понадобилось всего 0.6 с! Можно получить еще более высокую скорость, если параллельно использовать несколько процессоров. Сеть из 32 рабочих станций Пгга5РАВС 1, каждая из которых была оснащена двумя собственными дисками, может сортировать миллион записей за 2.41 с, используя гибридный меюд, названный ХО%-Вогг (А. С.
Аграс1-17иввеаи, В. Н. Аграс1-Впввеаи, 11. Е Сийег, Л. М. Нейегвге!п, В. А. Райегвоп, ЯСМОР Весите 26, (Липе, 1997), 243 — 254]. Изложенное выше подводит нас к выводу, что предлагаемый тест сортировки миллиона записей является, скорее, оценкой времени ввода-вывода, чем эффективности метода собственно сортировки; входные последовательности большей длины потребуют друтих, более "значимых", тестов. Например, последовательность поистине глобального масштаба для терабайтовой сортировки — 10'о записей но 100 символов — бьша рассортирована за 2.5 ч, Этот результат получен в сентябре 1997 года иа системе Бьйсоп СгарЬ1св Опк1п2000, включающей 32 процессора, 8 Гбайт оперативной памяти и 559 дисков по 4 Гбайт. Массив был рассортирован с помощью доступной на рынке программного обеспечения программы 1э'вогг™, разработанной К.
Нибергом (С. ХуЬегй)., Ч. Койстером (С. Коев1ег) и Дж. Греем (Л. Сгау), в которой используется неопубликованный до сих пор метод обработки. Но даже тест сортировки терабайтовых массивов может по нынешним временам оказаться недостаточно емким показателем. Наилучший из имеющихся на сегодняшний день претендентов на звание "универсального" теста эффективности сортировки, который обещает жить вечно (во всяком случае, так нам хотелось бы), — это так называемый критерий Минут-Сорт. Суть его состоит в выяснении, сколько 100-символьных записей можно рассортировать за 60 с. Когда данная книга была на последней стадии готовности к печати, рекордсменом по этому критерию был метод 7л'ОИг-Вот~:, 30 марта 1997 года 95 рабочим станциям, объединенным в сеть, понадобилось всего 59.21 с на сортировку 90.25 млн записей.
Но н результаты, полученные на самых современных системах, не опровергли ни одну нз основополагающих оценок, полученных теоретически. Подводя итог, можно с уверенностью заявить, что проблема эффективности сортировки остается сегодня такой же злободневной, как и ранее. УПРАЖНЕНИЯ 1. (00] Подведите итог этой главе; сформулируйте обобщение теоремы 5.4.6А. 2. (00] Взяв за основу табл. 1, скажите, какой иэ методов сортировки списков с шестирвзрнднымн ключами будет наилучшим для машины й11. 3. [37) (Устпоцчпвал сортировка с жинвмальнмм обвемом памлгпп,) Считается, что алгоритм сортировки требует минимальной памяти, если он использует для своих переменных только 0((1об Х) ) бит памяти сверх пространства, необходимого для размещения АГ записей.
Алгоритм должен быть общим в том смысле, что он должен работать при любых Ж, а не только при определенном значении Х, если, конечно, предполагается, что при вызове алгоритма для сортировки обеспечивается достаточное количество памяти с произвольным доступом. Во многих изученных нами алгоритмах сортировки зто требование минимальной памяти нарушается, в частности, запрещено использование Х полей связи. Быстрая сортировка (алгоритм 5.2.2б)) удовлетворяет требованию минимальной памяти,но время выполнения в наихудшем случаепропорционально 1т' . Пирамидальная сортировка (алгоритм 5 2.3Н) является единственным среди изученных нами алгоритмом типа 0(Х 1об 1т'), который использует минимальный обьем памяти, хотя можно сформулировать еще один подобный алгоритм, если использовать идею нз упр. 5.2 4 — 18.
Самым быстрым общим алгоритмом из изученных вами, который устойчиво сортирует ключи, является метод слияния списков (алгорнтм 5.2.4Б), однако он использует не минимальную память. Фактически единственными устойчивыми алгоритмами сортировки с минимальной памятью, которые мы анализировали, были методы типа й(Х ) (простые вставки, л~етод пузырька и вариации на тему простого выбора). Разработайте устойчивый алгоритм сортировки с минимальной памятью, требующий менее О(Х(1об Ж) ) машинных циклов в наихудшем случае [Указание. Можно создать устойчивый метод слияния, удовлетворяющий критерию минимальной памяти, который затрачивает на сортировку 0(Аг1об Х) машинных циклов.[ 4. [88[ Алгоритм сортировки называется береясловь~м, если принимает решение только на основе сравнения ключей и никогда не выполняет тех сравнений, результат которых может быть предсказш» на основе сравнений, выполненных ранее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
