различных средств решения такого рода задач с 1985 года стала сортировка миллиона 100-символьных записей с равномерно распределенными случайными 10-сим-вольными ключами. Предполагается, что исходная последовательность и результат должны храниться на диске, а целью является минимизация времени обработки, включая время загрузки и запуска програм.мы. В работе R. С. Agarwal, SIGMOD Record 25,2 (June, 1996), 240-246, описан эксперимент, проведенный на компьютере IBM RS/6000, моде.г1ь 39Н, в котором используется процессор с RISC-архитектурой. Методом поразрядной сортировки обрабатывались файлы, распределенные между восемью дисками, и задача была решена за 5.1 с. В подобных экспериментах узким местом является скорость ввода-вьшода. Процессору для решения этой задачи понадобилось всего 0.6 с! Можно получить еще более высокую скорость, если параллельно использовать несколько процессоров. Сеть из 32 рабочих станций UltraSPARC I, каждая из которых была оснащена двумя собственными дисками, может сортировать миллион записей за 2.41 с, используя гибридный метод, названный NOW-Sort [А. С. Arpaci-Dusseau, R. Н. Arpaci-Dusseau, D. Е. Culler, J. М. Hellerstein, D. А. Patterson, SIGMOD Record 26, (June, 1997), 243-254].

Изложенное выше подводит нас к выводу, что предлагаемый тест сортировки миллиона записей является, скорее, оценкой времени ввода-вывода, чем эффективности метода собственно сортировки; входные последовательности большей длины потребуют других, более "значимых" тестов. Например, последовательность поистине глобального масштаба для терабайтовой сортировки - Ю" записей по 100 символов - была рассортирована за 2.5 ч. Этот результат получен в сентябре 1997 года на системе Silicon Graphics Origin2000, включающей 32 процессора, 8 Гбайт оперативной памяти и 559 дисков по 4 Гбайт. Массив был рассортирован с помощью доступной на рынке программного обеспечения программы Nsort™, разработанной К. Нибергом (С. Nyberg), Ч. Койстером (С. Koester) и Дж. Греем (J. Gray), в которой используется неопубликованный до сих пор метод обработки.

Но даже тест сортировки терабайтовых массивов может по нынешним временам оказаться недостаточно емким показателем. Наилучший из имеющихся на сегодняшний день претендентов на звание "универсального" теста эффективности сортировки, который обещает жить вечно (во всяком случае, так нам хотелось бы), - это так называемый критерий Мипут-Сорт. Суть его состоит в выяснении, сколько 100-символьных записей можно рассортировать за 60 с. Когда данная книга была на последней стадии готовности к печати, рекордсменом по этому критерию был метод NOW-Sort; 30 марта 1997 года 95 рабочим станциям, объединенным в сеть, понадобилось всего 59.21 с на сортировку 90.25 млн записей. Но и результаты, полученные на самых современных системах, не опровергли ни одну из основополагающих оценок, полученных теоретически.

Подводя итог, можно с уверенностью заявить, что проблема эффективности сортировки остается сегодня такой же злободневной, как и ранее.

УПРАЖНЕНИЯ

1. [05] Подведите итог этой главе; сформулируйте обобщение теоремы 5.4.6А.

2. [20] Взяв за основу табл. 1, скажите, какой из методов сортировки списков с шестиразрядными ключами будет наилучшим для машины MIX.

3. [57] {Устойчивая сортировка с минимальным объемом памяти.) Считается, что алгоритм сортировки требует минимальной памяти, если он использует для своих переменных только 0((logiV)) бит памяти сверх пространства, необходимого для размещения N записей. Алгоритм должен быть общим в том смысле, что он должен работать при любых N, а не только при определенном значении N, если, конечно, предполагается, что при вызове алгоритма для сортировки обеспечивается достаточное количество памяти с произвольным доступом. Во многих изученных нами алгоритмах сортировки это требование минимальной памяти нарушается; в частности, запрещено использование N полей связи. Быстрая сортировка (алгоритм 5.2.2Q) удовлетворяет требованию минимальной памяти, но время выполнения в наихудшем случае пропорционально Л. Пирамидальная сортировка (алгоритм 5.2.3Н) является единственным среди изученных нами алгоритмом типа 0(iVlog N), который использует минимальный объем памяти, хотя можно сформулировать еще один подобный алгоритм, если использовать идею из упр. 5.2.4-18.

Самым быстрым общим алгоритмом из изученных нами, который устойчиво сортирует ключи, является метод слияния списков (алгоритм 5.2.4L), однако он использует не минимальную память. Фактически единственными устойчивыми алгоритмами сортировки с минимальной памятью, которые мы анализировали, были методы типа Q{N) (простые вставки, метод пузырька и вариации на тему простого выбора).

Разработайте устойчивый алгоритм сортировки с минимальной памятью, требующий менее 0(N{logN)) машинных циклов в наихудшем случае. [Указание. Можно создать устойчивый метод слияния, удовлетворяющий критерию минимальной памяти, который затрачивает на сортировку 0{N log N) машинных циклов.]

► 4. [28] Алгоритм сортировки называется бережливым, если принимает решение только на основе сравнения ключей и никогда не выполняет тех сравнений, результат которых может быть предсказан на основе сравнений, выполненных ранее. Какие из перечисленных в табл. 1 методов являются бережливыми?

5. [46] Довольно сложно сравнивать неслучайные данные, в которых присутствует множество равных ключей. Придумайте тест для определения эффективности сортировки, который (i) был бы актуальным как сегодня, так и через 100 лет, (ii) не включал бы в рассмотрение случай равномерно распределенных случайных ключей и (iii) не использовал бы входных последовательностей данных, которые изменились бы со временем.

Я посчитал бы цель достигнутой, если бы мне удалось рассортировать и расположить в логическом порядке основную часть того огромного материала, касающегося сортировки, который появился за несколько последних лет.

- ДЖ. К. ХОСКЕН (J. С. HOSKEN) (1955)

ГЛАВА б

ПОИСК

Взглянем на запись... - ЭЛ СМИТ (AL SMITH) (1928)

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

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

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

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