Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2), страница 7

5.4.9-20.) Эффект от применения аппаратной кэш-памяти при внутренней сорткровке анализировался в работе А. )аМагса„Н. Е. Бас(пег,,у, А)йогййшз 31 (1999), 66-104. Ее авторы пришли к выводу, что не следует включать шаг Яй в алгоритм 5.2.2ц, если для сортировки используется компьютер с современной архитектурой, хотя для компьютеров традиционной структуры, каковым является наш й11, алгоритм в прежнем виде вполне работоспособен.

Вместо того чтобы завершать быструю сортировку с помощью метода прямых вставок, предлагается, что, по мнению авторов, значительно лучше, заранее сортировать короткие подмассивы, сохраняя их ключи в кэш-памяти. А что можно сказать о нынешнем состоянии в области сортировки больших массивов данных? Одним из распространенных тестов для сравнительной оценки различных средств решения такого рода зцлач с 1965 года стала сортировка миллиона 100-символьных записей с равномерно распределенными случайнымя 10-символьными ключамк. Предполагается, что иси~дная последовательность и результат должны храниться на диске, а целью является минимизация времени обработки, включая время загрузки и запуска программы.

В работе В. С. Аяагжа), ЯОЛ1ОП Весогд 25, 2 (,1ппе, 1996), 240-246, описан эксперимент, проведенный на компьютере 1ВМ Вз/6000, модель 39Н, в котором используется процессор с ЫВС-архитектурой. Методом поразрядной сортировкц обрабатывались файлы, распределенные между восемью днскамн, и задача была решена за 5.1 с.

В подобных экспериментах узким местом является скорость ввода-вывода. Процессору для решения этой задачи понадобилось всего 0.6 с! 5|ожно получить еще более высокую скорость, если параллельно использовать несколько щюпессоров. Сеть из 32 рабочих станций 1)!гга8РА11С 1„каждая нз которых была оснащена двумя собственными дисками, может сортировать миллион записей за 2.41 с, используя гибридный метод, названный ХО%-Вогс [А. С. Аграс!-Впязеац, К. Н. АграсрПнззеац, В.

Е. Сц!!ег, Э. М. Нейехз1е1п, В. А. Раэгегзоп, ЯОМОП Весогд 26, (3ппе, 1997), 243-254). Изложенное выше подводит нас к выводу, что предлагаемый тест сортировки миллиона записей является, скорее, оценкой времени ввода вывода., чем эффективности метода собственно сортировки; входные последовательности ббльшей длины потребуют других, более "'значимых', тестов. Например, последовательность поистине глобального масштаба для глерабайтоеой сортировки — 10га записей по 100 символов —. была рассортирована за 2.5 ч. Этот результат получен в сентябре 1997 года на системе Бй! соп Огарййсз Ог!51п2000, включающей 32 процессора, 8 Гбайт оперативной памяти и 559 дисков по 4 Гбайт. Массив был рассортирован с помощью доступной на рынке программного обеспечения программы азот!™, разработанной К. Нибергом (С.

ХуЬегй), Ч. Койстером (С. Коевгег) н Дж. Греем (3. Огау), в которой используется неопубликованный до сих пор метод обработки. Но даже тест сортировки терабайтовых массивов может по нынешним временам оказаться недостаточно емким показателем. Наилучший из имеюп1ихся на сегодняшний день претендентов на звание "универсального" теста эффективности сортировки, который обещает жить вечно (во всяком случае, так нам хотелось бы), — это так называемый критерий Минут-Сорю. Суть его состоит в выяснении, сколько 100-символьных записей можно рассортировать за 60 с. Когда данная книга была на погледней стадии готовности к печати, рекордсменом по этому критерию был метод КОЕМУ-Вогг; 30 марта 1997 года 95 рабочим станциям, объединенным в сеть, понадобилось всего 59.21 с на сортировку 90.25 млн записей. Но и результаты, полученные на самых современных системах, не ощюверглн ни одну из основополагающих оценок, полученных теоретически, Подводя итоц можно с уверенностью заявить, что проблема эффективности сортировки остается сегодня такой же злободневной, как и ранее.

УПРАЖНЕНИЯ 1. [05) Подведите итог этой главе; сформулируйте обобщение теоремы 5.4.6А. 2. (ОО) Взяв за основу табл. 1, скажите, какой нз методов сортировки списков с шести- разрядными ключамв будет наилучшим для машины й1Х. 3. (57] (Усгаайчнаал сортировка с монимальным абэсмом памяти.) Считается, что алгоритм сортировки требует минимальной памяти, если он использует для своих переменных только 0((1ой Аг) э) бит памяти аюрх пространства„необходимого для размещения Ж записей.

Алгоритм должен быть общим в том смысле, что он должен работать при любых Аг, а не только прн определенном значении Аг, если, конечно, предполагается, что при вызове алгоритма для сортировки обеспечивается достаточное количество памяти с произвольным доступом. Во многих изученных нами алгоритмах сортировки это требованне минимальной памяти наруглается; в частности, запрещено использование АГ полей связи. Быстрая сортировка (алгоритм 5.2.2(4) удовлетворяет требованию минимальной памяти, ио время выполнения в наихудшем случае пропорционально Аз. Пирамидальная сортировка (алгоритм 5.2.3Н) является единственным среди изученных нами алгоритмом типа 0(йг!ой лг), который использует минимальный объем памяти, хотя можно сформулировать еще один подобный алгоритм, если использовать идею из упр.

5.2.4-13. Самым быстрым общим алгоритмом из изученных нами, который усгпойчнеа сортирует ключи, является метод слияния списков (алгоритм 5.2.41,), однако ои использует не минимальную память. Фактически единственными устойчивыми алгоритмами сортировки с минимальной памятью, которые мы анализировали, бьщи методы типа й(дг~) (простые вставки, метод пузьгрька и вариации на тему простого выбора). Разработайте устойчивый алгоритм сортировки с минимальной памятью, требующий менее 0(гг(!обгг)~) машинных циклов в наихудшем случае.

(Указание. Можно создать устойчивый метод счияиия, удовлетворяющий критершо минимальной памяти, который затрачивает на сортировку 0(Х 1об А') машинных циклов.) ° 4. (58) Алгоритм сортировки называется бсреяслнамм, если принимает решение только на основе сравнения ключей и никогда не вьпюлняет тех сравнений, результат которых может быть предсказан на основе сравнений, выполненных ранее. Какие из перечисленных в табгь 1 методов являются бережливыми? 5. [4б) Довольно сложно сравнивать неслучайные данные, в которых присутствует множество равных ключей. Придумайте тест для определения эффективности сортировки, который (1) был бы актуальным как сегодня, зяк и через 100 лет, (й) не включал бы в рассмотрение случай равномерно распределенных случайных ключей и (Й) не использовал бы входных последовательностей данных, которые изменились бы со временем.

Я посчитал бы пель достигнутой, если бы мне удалось рассортировать н олсположнть я логическом порядке основную часть того огоомного матеонала, касающегося соогнровкн, который появился зэ несколько последних лег. — /РК. К. ХОСКЕН (3. С. НОЕКЕИ) (1955) ГЛАВА б поиск Взглянем на запись... — ЭЛ СМИТ (А1 ЬМП Н) (1928) Эта глава могла бы носить более претенциозное название .— "Хранение и получение информации"; с другой стороны, ее можно было бы назвать кратко и просто— "Просмотр таблиц".

В ней мы займемся вопросами накопления информации в памяти компьютера и рассмотрим способы ее быстрого извлечения. Зачастую мы сталкиваемся с избыточной информацией, и лучшее, что с ней можно сделать,— забыть о ней или уничтожить ее. Однако нередки ситуации, когда крайне важно сохранить материал и организовать его таким образом, чтобы впоследствии обеспечить к нему максимально быстрый доступ.

Основная часть этой главы посвящена изучению простейшей задачи: поиску информации, сохраненной с конкретным идентификатором. Например, в численном приложении можег понадобиться найти у(х) по данному х и таблице значений у; другим примером может послужить поиск перевода на английский язык некоторого русского слова.

В целом, мы предполагаем, что имеется набор из Ф записей и задача состоит в нахождении одной из них, Как и в случае сортировки, мы полагаем, что каждая запись включает специальное поле, именуемое ее ключом; данный термин удачен, так как, несомненно, отражает тот печальный факт, что ежедневно миллионы людей тратят время и силы на поиски собственных неизвестно куда запропастившихся ключей... В общем случае нам требуется )1' различных ключей для того, чтобы каждый из иих однозначно идентифицировал связанную с ним запись.

Набор всех записей именуется таблицей или файлом, причем слово "таблица" обычно используетгя для описания маленького файла„а слово "файл" — для описания большой таблицы. Болыпой же файл (или группу файлов) часто называют базой данных. Алгоритм поиска имеет так называемый пргдменш, К, и задача заключается в нахождении записи, для которой К служит ключом. Результатом поиска может быть одно из двух: либо поиск завершился успешно, и уникальная запись, содержащая К, найдена, либо поиск оказался неудачным, и запись с ключом К не найдена.

После неудачного поиска иногда желательно внести новую запись, содержазцую К, в таблицу. Метод, осуществляющий это, называется алгоритмом поиска н вставки. Некоторые аппаратные устройства, известные как ассоциатпанал память, решают данную проблему автоматически, путем, который можно сравнить с функционированием мозга человека, однако мы все же будем изучать технологию поиска, применяемую в обгачных цифровых компькперах общего назначения.

Хотя цель поиска — нахождение информации, хранящейся в асоэциированной с К записи, алгоритмы в этой главе предназначены для поиска К. После нахождения К поиск связанной с ним информации становится тривиальной задачей, зависящей от способа хранения информации. Например, найдя К в ТАВ1.Е+ 1, мы обнаружим связанные с ним данные в ТАЕТЕ+ 1 + 1, в ВАТА + г' или в еще каком-то месте, которое определяется способом хранения информации. Поэтому мы считаем задачу выполненной в тот момент, когда находим К (или убеждаемся в его отсутствии).

Поиск обычно является наиболее "времяемкой" частью многих программ, и замена плохого метода поиска хорошим может значительно увеличить скорость работы программы. К тому же часто представляется возможным так изменить данные или используемые структуры, что поиска удается избежать совсем. Одним из таких способов может быть связь данных (например, при использовании списка с двойнымн связями поиск предшествующего и последующего элементов данного становится совершенно излишним). В случае, когда мы можем выбирать ключи, имеется еще один способ избежать поиска: выбрать в качестве ключа натуральные числа (1,2,..., М); при этом запись с ключом К просто размещается в ТАВЕЕ+ К, Обе эти технологии были использованы, чтобы избежать поиска в алгоритме топологической сортировки, обсуждавшемся в разделе 2.2.3. Однако поиск необходим, если объекты для топологической сортировки представлены не числовыми, а символьными значениями.