Таблица 10.1. Эмпирический анализ поразрядных сортировок (ключи в виде целых чисел)

Приводимые в таблице в относительных единицах временные показатели различных поразрядных сортировок применительно к файлам с N 32-разрядных чисел произвольной организацией (во всех применяется отсечение для N меньше 16 для последующей сортировки методом простой вставки) показывают, что поразрядные сортировки входят в число самых быстрых, если соблюдать осторожность при их использовании. Если мы используем огромное основание системы счисления для крошечных файлов, мы просто сводим на нет все преимущества поразрядной сортировки MSD, однако если мы выберем в качестве такого основания величину, которая меньше размера файла, то все ее достоинства восстанавливаются. Самый быстрый метод сортировки ключей в виде целых чисел является поразрядная сортировка, примененная к старшей половине ключей, быстродействие которого мы можем повысить еще больше, если уделим надлежащее внимание внутреннему циклу (см. упражнение 10.45).

адаптируется под размер файла

Поразрядная сортировка LSD на разрядах MSD.

Таблица 10.2. Эмпирические исследования поразрядных сортировок (строковые ключи)

Приводимые в таблице в относительных единицах временные показатели различных поразрядных сортировок первых слов N слов из книги Моби Дик (Mobby Dick) (все виды сортировок, за исключением пирамидальной сортировки, с отсечением при N меньше 16 для последующего выполнения сортировки простыми вставками) показывают, что подход сначала MSD эффективен применительно к строковым данным. Отсечение малых подфайлов менее эффективен в условиях трехпутевой поразрядной быстрой сортировки, чем другие методы, и совсем не эффективен, если не проводить модификацию сортировки методом вставки во избежание прохода через старшие разряды ключей (см. упражнение 10.46).

Обозначения:

Q Быстрая сортировка, стандартная (программа 7.1)

Т Быстрая сортировка с трехпутевым разбиением (программа 7.5)

М Сортировка слиянием (программа 8.2)

F Пирамидальная сортировка с усовершенствованием Флойда (см. раздел 9.4)

R Поразрядная сортировка MSD (программа 10.2)

X Трехпутевая поразрядная быстрая сортировка MSD (программа 10.3)

X* Трехпутевая поразрядная быстрая сортировка MSD (с отсечениями)

Упражнения

t> 10.44. Каким является основной недостаток выполнения на старших битах ключей с последующей подчисткой нарушений искомого порядка при помощи сортировки простыми вставками?

10.45. Разработать программную реализацию поразрядной сортировки LSD на 32-разрядных ключах с минимально возможным числом команд во внутреннем цикле.

10.46. Реализовать трехпутевую поразрядную быструю сортировку таким образом, чтобы сортировка методом вставок файлов небольших размеров не использовала старшие байты, о которых известно, что они равны.

10.47. Имея 1 миллион 32-разрядных ключей, найти такой размер байта, для которого время выполнения сортировки будет минимальным в условиях, когда используется метод, предусматривающий поразрядную сортировку LSD по двум первым байтам и последующую подчистку нарушений искомого порядка через сортировку простыми вставками.

10.48. Выполнить упражнение 10.47 для 1 миллиарда 64-разрядных ключей.

10.49. Выполнить упражнение 10.48 для трехпутевой поразрядной сортировки LSD.

Методы сортировки

специального

назначения

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

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