Поразрядная сортировка

Разбить на страницы

Показывать лекцию целиком

Во многих приложениях сортировки ключи, используемые для упорядочения записей в файлах, могут быть весьма сложными. Представьте, например, насколько сложны ключи, используемые в телефонной книге или в библиотечном каталоге. Чтобы отделить все эти сложности от наиболее важных свойств изучаемых методов сортировки, в главах 6—9 мы почти везде ограничивались использованием только базовых операций сравнения двух ключей и обмена двух записей (скрыв в этих функциях все детали работы с ключами) как абстрактным интерфейсом между методами сортировки и приложениями. В данной главе мы рассмотрим другую абстракцию для ключей сортировки. Например, часто нет необходимости в полной обработке ключей на каждом этапе: при поиске в телефонном справочнике, чтобы найти страницу с номером какого-либо абонента, достаточно проверить лишь несколько первых букв его фамилии. Чтобы добиться такой же эффективности алгоритмов сортировки, мы перейдем от абстрактной операции сравнения ключей к абстракции, в которой ключи разбиваются на последовательность частей фиксированного размера — байтов. Двоичные числа представляют собой последовательности битов, строки — последовательности символов, десятичные числа — последовательности цифр, аналогично могут рассматриваться и многие другие (хотя и не все) типы ключей. Методы сортировки, основанные на обработке ключей по частям, называются поразрядными методами сортировки (radix sort). Эти методы не просто сравнивают ключи, а обрабатывают и сравнивают части ключей.

Алгоритмы поразрядной сортировки интерпретируют ключи как числа, представленные в системе счисления с основанием R, при различных значениях R (основание системы счисления — radix), и работают с отдельными цифрами этих чисел. Например, когда почтово-сортировочная машина обрабатывает пачку конвертов, каждый из которых помечен 5-значным десятичным числом, она распределяет эту пачку на десять отдельных пачек: в одной находятся пакеты, номера которых начинаются с 0, в другой находятся пакеты с номерами, начинающимися с 1, в третьей — с 2 и т.д. Каждая пачка может быть обработана отдельно с помощью того же метода, по следующей цифре, или более простым способом, если в пачке всего лишь несколько пакетов. Если теперь собрать пакеты из пачек в порядке от 0 до 9 и в таком же порядке внутри каждой пачки, то они окажутся упорядоченными. Эта процедура представляет собой поразрядную сортировку с R = 10, и такой метод удобен в приложениях, использующих сортировку, где ключами являются десятичные числа, содержащие от 5 до 10 цифр — наподобие почтовых кодов, телефонных номеров или идентификационных номеров. Этот метод будет подробно рассмотрен в разделе 10.3.

Для различных приложений лучше подходят различные основания системы счисления R. В этой главе мы будем рассматривать в основном ключи, представленные в виде целых чисел или строк, для которых широко применяются методы поразрядной сортировки. Для целых чисел, представляемых в компьютерах в виде двоичных чисел, мы чаще будем работать с R = 2 или с одной из степеней 2, поскольку это позволяет разбивать ключи на независимые части. Для ключей, содержащих строки символов, мы используем R = 128 или R = 256, чтобы согласовать основание системы счисления с размером байта. Вообще-то, помимо таких прямых применений, в виде двоичных чисел можно рассматривать практически все, что записано в компьютере. Это позволяет переориентировать многие приложения сортировки, которые используют другие типы ключей, на использование поразрядной сортировки, которая упорядочивает ключи, представленные в виде двоичных чисел.

Алгоритмы поразрядной сортировки основаны на абстрактной операции " извлечь i-ю цифру ключа " . К счастью, в С++ есть низкоуровневые операции, позволяющие реализовать такие действия просто и эффективно. Это очень важно, поскольку некоторые языки программирования (например, Pascal), поощряя машинно-независимое программирование, намеренно затрудняют написание программ, зависящих от способа представления чисел в конкретной машине. В таких языках трудно реализовать многие виды битовых операций, удобные для выполнения на большинстве компьютеров. В частности, жертвой этой " прогрессивной " философии стала и поразрядная сортировка. Однако создатели С и С++ поняли, что прямые операции с битами часто бывают весьма полезны, и при реализации поразрядной сортировки мы сможем воспользоваться низкоуровневыми языковыми средствами.

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

(рис 10.1) Поразрядная сортировка

Хотя в данном списке находятся 11 чисел от 0 до 1 (слева), содержащих в совокупности 99 цифр, их можно упорядочить (в центре), проанализировав лишь 22 цифры (справа).

Существуют два принципиально различных базовых подхода к поразрядной сортировке. Первый класс методов составляют алгоритмы, анализирующие цифры в ключах в направлении слева направо, при этом первыми обрабатываются наиболее значащие цифры. Все эти методы вместе называются MSD-сортировками (most significant digit radix sort — поразрядная сортировка сначала по старшей цифре). MSD-сортировки привлекательны тем, что они анализируют минимальный объем информации, необходимый для выполнения сортировки (рис 10.1). Методы MSD-сортировки являются обобщением быстрой сортировки, поскольку они разбивают сортируемый файл в соответствии со старшими цифрами ключей, а затем рекурсивно применяют тот же метод к полученным подфайлам. В самом деле, при основании системы счисления, равном 2, реализация MSD-сортировки похожа на быструю сортировку. Во втором классе методов поразрядной сортировки используется другой принцип: они анализируют цифры ключей в направлении справа налево, работая сначала с наименее значащими цифрами. Все эти методы вместе называются LSD-сортировками (least significant digit radix sort — поразрядная сортировка сначала по младшей цифре). LSD-сортировка в какой-то степени противоречит интуиции, поскольку часть процессорного времени затрачивается на обработку цифр, которые не могут повлиять на результат, однако данная проблема легко решается, и этот почтенный метод годится для работы во многих приложениях сортировки.

Биты, байты и слова

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

Определение 10.1. Байт — это последовательность битов фиксированной длины, строка — это последовательность байтов переменной длины, слово — это последовательность байтов фиксированной длины.

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

У типичной машины могут быть 8-разрядные байты и 32- и 64-разрядные слова (конкретные значения приведены в заголовочном файле <limits.h>), однако бывает удобно рассматривать и некоторые другие размеры байтов и слов (обычно небольшие кратные или части встроенных машинных размеров). Итак, в качестве числа разрядов в слове и числа разрядов в байте будут использоваться зависящие от архитектуры машины и свойств приложения константы, например:

  const int bitsword = 32;
  const int bitsbyte = 8;
  const int bytesword = bitsword/bitsbyte;
  const int R = 1 << bitsbyte;

Для последующего использования, когда мы начнем рассматривать поразрядные сортировки, в эти определения включена также константа R, равная количеству различных значений байта. При использовании таких определений обычно предполагается, что константа bitsword кратна bitsbyte, что число битов в машинном слове не меньше (обычно равно) bitsword, и что каждый байт имеет индивидуальный адрес. В различных компьютерах приняты различные соглашения по обращениям к битам и байтам. Для наших целей мы будем считать, что биты в слове пронумерованы слева направо от 0 до bitsword-1, а байты в слове пронумерованы слева направо от 0 до bytesword-1. В обоих случаях мы полагаем, что нумерация выполняется от наиболее значащих элементов к наименее значащим.

В большинстве компьютеров имеются битовые операции И и сдвиг, которые позволяют извлекать из слов отдельные байты (и биты тоже — прим. перев.).

В C++ можно прямо написать операцию извлечения B-го байта из двоичного слова A следующим образом:

  inline int digit(long A, int B)
    { return (A >> bitsbyte*(bytesword-B-1)  (R-1); }

Эта макрокоманда может, например, извлечь байт 2 (третий байт) 32-разрядного числа, сдвинув его вправо на 32 — 3 • 8 = 8 позиций и наложив маску 00000000000000000000000011111111

для обнуления всех разрядов, кроме требуемого байта, который занимает 8 правых разрядов.

Во многих машинах основание системы счисления согласовано с размером байта, что позволяет быстро получить правые биты числа. Эта операция непосредственно поддерживается в С++ для строк в стиле С:

  inline int digit(char* A, int B)
    { return A[B]; }

При использовании структуры-оболочки, наподобие рассмотренной в разделе 6.8 , можно записать:

  inline int digit(Item A, int B)
    { return A.str[B]; }

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

На несколько другом уровне абстракции можно рассматривать ключи как числа, а байты как цифры. Если дано число (т.е. ключ в виде числа), то для реализации поразрядной сортировки необходима базовая операция извлечения цифры из этого числа. Если в качестве основания системы счисления выбрана степень 2, то цифрами являются группы битов, к которым легко обратиться непосредственно одним из рассмотренных выше методов. Основной причиной использования степени 2 в качестве основания системы счисления как раз и является легкость доступа к группам битов. В некоторых вычислительных средах можно выбирать и другие основания систем счисления. Например, если а — положительное целое число, то b-я цифра числа а в системе счисления R есть $$$$\lfloor{a/R^{b}}\rfloor \mod {R}$$$$.

На машинах, предназначенных для высокопроизводительных численных расчетов, это вычисление может выполняться для произвольного значения R так же быстро, как и для R = 2.

Еще одна точка зрения — рассматривать ключи как числа в диапазоне от 0 до 1, с неявной десятичной точкой слева, как показано на рис 10.1. В этом случае b-ой цифрой числа a будет $$$$\lfloor{aR^{b}}\rfloor \mod {R}$$$$.

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

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

Определение 10.2. Ключ — это число в системе счисления с основанием R, цифры которого пронумерованы слева направо (начиная с 0).

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

Мы предполагаем, что ключи достаточно длинные, так что операция извлечения из них битов имеет смысл. Если же ключи короткие, то можно воспользоваться методом распределяющего подсчета из . Напомним, что этот метод позволяет отсортировать N ключей, представляющие собой целые числа в диапазоне от 0 до R — 1, за линейное время, используя для этой цели одну вспомогательную таблицу размером R для подсчета и другую таблицу, размером N, для переупорядочения записей. Значит, если есть возможность использовать таблицу размером 2w, то сортировку w-разрядных ключей легко выполнить за линейное время. На самом деле метод распределяющего подсчета лежит в основе базовых методов MSD- и LSD-сортировок. Поразрядная сортировка нужна лишь тогда, когда ключи настолько длинны (скажем, w = 64), что использование таблицы размером 2w невозможно.

Упражнения

10.1. Сколько цифр нужно для представления 32-разрядного числа в системе счисления с основанием 256? Опишите, как можно извлечь каждую цифру этого числа. Ответьте на этот же вопрос, если основанием системы счисления будет число 2¹⁶.

10.2. Для N = 10³, 10⁶ и 10⁹ приведите наименьший размер байта, позволяющий представить любое число в диапазоне от 0 до N в виде 4-байтового слова.

10.3. Напишите перегруженную операцию <, используя абстракцию digit (например, чтобы выполнять эмпирические сравнения алгоритмов из глав 6 и 9 с методами, описанными в данной главе, для одних и тех же данных).

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

10.5. Напишите программу, которая для заданного набора случайных десятичных чисел (. Выполните эту программу для N = 10³, 10⁴, 10⁵ и 10⁶.

10.6. Выполните упражнение 10.5 для R = 2, используя случайные 32-разрядные числа.

10.7. Выполните упражнение 10.5 для нормально распределенных чисел (распределение Гаусса).

Бинарная быстрая сортировка

Предположим, что мы можем переупорядочить записи в файле таким образом, что все ключи, начинающиеся с бита 0, будут расположены перед ключами, начинающимися с бита 1. Тогда можно воспользоваться рекурсивным методом сортировки, который является одним из вариантов быстрой сортировки (см. ): разбиваем файл этим способом и потом независимо сортируем оба подфайла. Для переупорядочения файла мы просматриваем его слева до обнаружения ключа, который начинается с бита 1, затем просматриваем справа до обнаружения ключа, который начинается с бита 0, обмениваем их и продолжаем этот процесс до перекрещивания указателей. В литературе (включая и более ранние издания данной книги) этот метод часто называют поразрядной обменной сортировкой, а здесь мы будем называть его бинарной быстрой сортировкой (binary quicksort), чтобы подчеркнуть, что это лишь простой вариант алгоритма, изобретенного Хоаром, хотя он был открыт раньше быстрой сортировки (см. раздел ссылок).

В программе 10.1 представлена полная реализация этого метода. Применяемый в ней процесс разбиения по существу тот же, что и в программе 7.2, только в качестве центрального элемента используется число 2^b, а не некоторый ключ из файла. Поскольку в файле может и не быть числа 2^b, то нет и гарантии того, что в процессе разбиения хотя бы один элемент попадет в свою окончательную позицию. Данный алгоритм отличается и от обычной быстрой сортировки, поскольку рекурсивные вызовы выполняются для ключей размером на 1 бит меньше. Это различие существенно влияет на эффективность алгоритма. Например, если попадется вырожденное разбиение файла из N элементов, то будет выполнен рекурсивный вызов для подфайла размером N, но для ключей длиной на 1 разряд меньше. Поэтому число таких вызовов ограничено количеством разрядов в ключе. А последовательное использование центральных элементов, отсутствующих в файле, может ввести обычную быструю сортировку в бесконечный рекурсивный цикл.

Программа 10.1. Бинарная быстрая сортировка

Эта программа разбивает файл по ведущим битам ключей и затем рекурсивно сортирует полученные подфайлы. Переменная d содержит позицию анализируемого бита, начиная с 0 (самого левого). Разбиение завершается при j, равном i, после чего у всех элементов справа от a[i] в d-ой позиции находится 1, а у всех элементов слева от a[i] в d-ой позиции находится 0. Сам элемент a[i] содержит в d-ой позиции 1, кроме того случая, когда все ключи файла содержат в d-ой позиции нули. На этот случай сразу после цикла разбиения вставлена дополнительная проверка.

  template <class Item>
  void quicksortB(Item a[], int l, int r, int d)
    { int i = l, j = r;
      if (r <= l || d > bitsword) return;
      while (j != i)
        { while (digit(a[i], d) == 0  (i < j)) i++;
          while (digit(a[j], d) == 1  (j > i)) j--;
          exch(a[i], a[j]);
        }
      if (digit(a[r], d) == 0) j++;
      quicksortB(a, l, j-1, d+1);
      quicksortB(a, j, r, d+1);
    }
  template <class Item>
  void sort(Item a[], int l, int r)
    { quicksortB(a, l, r, 0); }

Как и в случае стандартной быстрой сортировки, возможны различные варианты реализации внутреннего цикла. В программе 10.1 проверка, не пересеклись ли значения индексов, включена в оба внутренних цикла. Такая проверка приводит к лишнему обмену в случае, когда i = j; этого можно избежать с помощью оператора break, как сделано в программе 7.2, хотя там обмен элемента a[i] сам с собой вполне безобиден. Другой способ — использовать сигнальный ключ.

На рис 10.2 показано выполнение программы 10.1 на небольшом файле, которое можно сравнить с рис 7.1 для быстрой сортировки. Этот рисунок показывает, как перемещаются данные, но не объясняет, почему производятся те или иные перемещения — это зависит от двоичного представления ключей. Более подробное представление данного примера дано на рис 10.3. Здесь считается, что буквы закодированы простым 5-разрядным кодом, в котором i-я буква алфавита представлена двоичным представлением числа i. Такая кодировка представляет собой упрощенную версию настоящих символьных кодировок, в которых для представления большего количества символов (буквы верхнего и нижнего регистров, цифры и специальные символы) используется большее число битов (7, 8 или даже 16).

(рис 10.2) Пример бинарной быстрой сортировки

Разбиение по старшему разряду еще не гарантирует того, что хотя бы одно значение займет свое окончательное место; оно лишь обеспечивает, что все ключи с 0 в старшем разряде предшествуют ключам с 1 в старшем разряде. Можно сравнить эту диаграмму с рис 7.1 для быстрой сортировки, хотя принцип разбиений совершенно непонятен, если ключи не представлены в двоичном виде. На рис. 10.3 рис 10.3 приведены все детали, которые проясняют, по каким позициям производится разбиение.

Для ключей в виде полных слов, состоящих из случайных битов, программа 10.1 должна начинать работу с самого левого бита слова, т.е. нулевого. В общем случае начальный бит напрямую зависит от приложения, от количества битов в машинном слове и от внутреннего представления целых (в том числе отрицательных) чисел. Для однобуквенных 5-разрядных ключей с рис 10.2 и рис 10.3 на 32-битовой машине начальным должен быть бит 27.

Этот пример показывает потенциальную проблему, которая может возникнуть при использовании бинарной быстрой сортировки в реальных ситуациях: довольно часто могут встречаться вырожденные разбиения (когда все ключи имеют одно и то же значение разряда, по которому производится разбиение). Сортировка небольших чисел (в которых много нулевых старших разрядов), как в рассмотренных нами примерах, не является чем-то необычным. Эта же проблема возникает и для символьных ключей: допустим, мы строим 32-разрядные ключи, объединяя четыре символа, каждый из которых представлен в стандартной 8-битовой кодировке. Тогда весьма вероятно появление вырожденных разбиений в начальной позиции каждого символа, поскольку, например, все буквы нижнего регистра начинаются с одних и тех же битов. С этой проблемой часто приходится сталкиваться при сортировке кодированных данных; аналогичные проблемы возникают и в других видах поразрядной сортировки.

(рис 10.3) Пример бинарной быстрой сортировки (с битовым представлением ключей)

Эта диаграмма построена на основании рис 10.2, только здесь значения ключей приведены в двоичном представлении, а таблица сжата так, чтобы показать сортировку независимых подфайлов, как будто они выполняются параллельно, и для удобства транспонирована. На первом этапе файл разбивается на подфайл, все ключи которого начинаются с 0, и подфайл, все ключи которого начинаются с 1. Затем первый подфайл разбивается на подфайл, все ключи которого начинаются с 00, и подфайл, все ключи которого начинаются с 01; независимо от этого в произвольный момент времени второй подфайл разбивается на подфайл, все ключи которого начинаются с 10, и подфайл, все ключи которого начинаются с 11. Этот процесс прекращается при исчерпании разрядов (для повторяющихся ключей в данном примере) или когда размер подфайлов станет равным 1.

После того как ключ можно отличить по его левым разрядам от всех остальных, никакие другие разряды больше не анализируются. Это свойство в одних ситуациях является достоинством, в других — недостатком. Если ключи представляют собой действительно случайные совокупности битов, то в каждом ключе анализируются только lg N битов, что обычно намного меньше числа битов в ключах. Этот факт рассматривается в разделе 10.6, а также в упражнении 10.5 и на рис 10.1. Например, сортировка файла из 1000 записей со случайными ключами может потребовать анализа всего лишь 10 или 11 битов каждого ключа (даже если ключи, скажем, 64-разрядные). А вот для одинаковых ключей проверяются все биты. Поразрядная сортировка не способна хорошо работать на файлах с большим числом длинных повторяющихся ключей. Бинарная быстрая сортировка и стандартный метод работают достаточно быстро, если сортируемые ключи состоят из абсолютно случайных битов (различие между ними состоит в основном в разнице затрат на операции извлечения битов и сравнения), но стандартный алгоритм быстрой сортировки легче приспособить к обработке неслучайных последовательностей ключей, а трехпутевая быстрая сортировка идеально подходит для случаев с преобладанием повторяющихся ключей.

Как и в случае быстрой сортировки, структуру разбиения удобно описывать в виде бинарного дерева (как на рис 10.4): корень дерева соответствует сортируемому файлу, а два его поддерева — подфайлам после разбиения. В случае стандартной быстрой сортировки известно, что по крайней мере одна из записей при разбиении попадает в свою окончательную позицию, так что этот ключ помещается в корневой узел.

(рис 10.4) Дерево разбиения для бинарной быстрой сортировки

Это дерево описывает структуру разбиения для бинарной быстрой сортировки, соответствующую рис 10.2 и 10.3. Поскольку элементы не обязательно занимают свои окончательные позиции, ключи соответствуют внешним узлам дерева. Такая структура обладает следующим свойством: если на пути от корня к любому ключу обозначить разветвления влево за 0, а вправо — за 1, то получим значения старших разрядов этого ключа. Именно эти значения и отличают во время сортировки данный ключ от всех остальных. Черные квадратики означают пустые части разбиения (когда все ключи переходят в другую часть, поскольку значения их старших разрядов совпадают). В данном примере это происходит только на нижних уровнях дерева, но в принципе возможно и выше: например, если бы среди ключей не было I или X, то их узлы на рисунке были бы заменены пустым узлом. Обратите внимание, что повторяющиеся ключи (A и E) не могут быть разделены (сортировка поместит их в один подфайл только после исчерпания всех их битов).

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

(рис 10.5) Динамические характеристики бинарной быстрой сортировки на большом файле

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

Разделы разбиений в быстрой сортировке зависят от двоичного представления диапазона ключей и количества сортируемых элементов. Например, если файлы представляют собой случайные перестановки целых чисел, меньших 171 = 10101011₂, то разбиение по первому биту эквивалентно разбиению по значению 128, и подфайлы получаются разновеликими (размер одного — 128, а другого — 43). Ключи на рис 10.5 являются случайными 8-разрядными значениями, поэтому здесь такой эффект не наблюдается, но знать о нем надо, чтобы не было неприятных сюрпризов при столкновении с ним на практике.

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

Упражнения

10.8. Начертите, в стиле рис 10.2, trie-дерево, соответствующее процессу разбиений при поразрядной быстрой сортировке ключей E A S Y Q U E S T I O N.

10.9. Сравните количество обменов, используемых бинарной быстрой сортировкой, с количеством обменов, используемых обычной быстрой сортировкой, для 3-разрядных двоичных чисел 001, 011, 101, 110, 000, 001, 010, 111, 110, 010.

о 10.10. Почему сортировка меньшего из двух под-файлов первым менее важна в бинарной быстрой сортировке, чем в обычной быстрой сортировке?

о 10.11. Опишите, что происходит на втором уровне разбиения (когда разбивается левый подфайл и когда разбивается правый подфайл) при использовании бинарной быстрой сортировки для упорядочения случайных перестановок неотрицательных целых чисел, меньших 171.

10.12. Напишите программу, которая за один предварительный проход определяет число старших разрядов, одинаковых у всех ключей, а затем вызывает бинарную быструю сортировку, модифицированную так, что она игнорирует эти разряды. Сравните время выполнения этой программы со временем выполнения стандартной реализации для N = 10³, 10⁴, 10⁵ и 10⁶, если входными данными являются 32-разрядные слова следующего формата: крайние правые 16 битов — равномерно распределенные случайные значения, а крайние левые 16 битов равны 0, кроме единицы в i-ой позиции, если в правой половине имеется i единиц.

10.13. Внесите в бинарную быструю сортировку явную проверку ситуаций, когда все ключи равны. Сравните время выполнения этой программы с аналогичным показателем для стандартной реализации при N = 10³, 10⁴, 10⁵ и 10⁶ и входных данных, описанных в упражнении 10.12.

Поразрядная MSD-сортировка

Использование в поразрядной быстрой сортировке лишь одного разряда соответствует тому, что ключи считаются числами в двоичной системе счисления, и сначала рассматриваются наиболее значащие цифры. Обобщая этот подход, предположим, что нам нужно отсортировать числа, представленные в системе счисления по основанию R, рассматривая сначала наиболее значащие байты. Это требует разбиения массива не на 2, а на R различных частей. Традиционно эти части называются контейнерами, и мы будем представлять себе, что алгоритм работает с группой из R контейнеров, по одному для каждого возможного значения первой цифры, как показано на следующей диаграмме:

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

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

(рис 10.6) Динамические характеристики поразрядной MSD-сортировки

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

Как было сказано в разделе 10.2, одной из наиболее привлекательных особенностей поразрядной сортировки является интуитивный и прямолинейный характер ее адаптации к приложениям сортировки, в которых ключами являются символьные строки. Это особенно ярко проявляется в С++ и других средах программирования с прямой поддержкой обработки строк. Для MSD-сортировки просто используется основание системы счисления, соответствующее размеру байта. Чтобы извлечь цифру, достаточно загрузить байт, а для перехода к следующей цифре нужно увеличить на единицу указатель строки. Пока мы рассматриваем ключи фиксированной длины, а чуть позже увидим, что эти же базовые механизмы позволяют работать и с ключами в виде строк переменной длины.

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

(рис 10.7) Пример поразрядной MSD-сортировки

Все слова распределяются по 26 контейнерам соответственно первой букве. Затем тем же методом сортируется содержимое каждого контейнера, начиная со второй буквы.

Сначала слова разбиваются таким образом, что те из них, которые начинаются с буквы а, расположены раньше слов, начинающихся с буквы b, и т.д. Затем слова, начинающиеся с буквы а, в свою очередь рекурсивно сортируются, далее сортируются слова, начинающиеся с буквы b, и т.д.

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

Как мы уже убедились на примере быстрой сортировки в и разделе 10.2, а также сортировки слиянием в , производительность большинства рекурсивных программ можно повысить, используя для сортировки небольших файлов простой алгоритм. Использование другого метода для сортировки небольших файлов (контейнеров с небольшим количеством элементов) в поразрядной сортировке имеет большое значение, ведь их так много!

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

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

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

Этот процесс реализован в программе 10.2. Ее рекурсивная структура обобщает структуру быстрой сортировки, так что все вопросы, рассмотренные в разделе 7.3 , необходимо рассмотреть и здесь. Нужно ли обрабатывать больший из подфайлов последним, во избежание излишней глубины рекурсии? Скорее всего, нет, поскольку глубина рекурсии ограничена длиной ключей. Нужно ли применять для сортировки небольших подфайлов простые методы, вроде сортировки вставками? Конечно, поскольку таких подфайлов будет очень много.

Программа 10.2. Поразрядная MSD-сортировка

Эта программа написана на основе программы 8.17 (сортировка распределяющим подсчетом) путем замены ссылок на ключи ссылками на цифры ключей и добавления в конце цикла, выполняющего рекурсивные вызовы для каждого под-файла ключей, начинающихся с одной и той же цифры. Для ключей переменной длины, оканчивающихся нулевым байтом (т.е. строк в стиле С) первый оператор if и первый рекурсивный вызов не нужны. В этой реализации используется вспомогательный массив (aux) достаточного размера, чтобы хранить копию входного файла.

  #define bin(A) l+count[A]
  template <class Item>
  void radixMSD(Item a[], int l, int r, int d)
    { int i, j, count[R+1];
      static Item aux[maxN];
      if (d > bytesword) return;
      if (r-l <= M) { insertion(a, l, r); return; }
      for (j = 0; j < R; j++) count[j] = 0;
      for (i = l; i <= r; i++)
        count[digit(a[i], d) + 1]+ + ;
      for (j = 1; j < R; j++)
        count[j] += count[j-1];
      for (i = l; i <= r; i++)
        aux[l+count[digit(a[i], d)]++] = a[i];
      for (i = l; i <= r; i++) a[i] = aux[i];
      radixMSD(a, l, bin(0)-1, d+1);
      for (j = 0; j < R-1; j++)
        radixMSD(a, bin(j), bin(j + 1)-1, d+1);
    }

Для выполнения разбиения в программе 10.2 используется вспомогательный массив, размер которого равен размеру сортируемого файла. В качестве альтернативы можно воспользоваться обменным методом распределяющего подсчета (см. упражнения 10.17 и 10.18). Особенно большое внимание следует уделить использованию памяти, поскольку рекурсивные обращения могут расходовать очень много памяти для размещения локальных переменных. В программе 10.2 временный буфер для перемещения ключей (aux) может быть глобальным, но массив, в котором хранятся счетчики и позиции точек разбиения (count) должен быть локальным.

Использование дополнительной памяти для вспомогательного массива — не самый серьезный вопрос во многих приложениях, использующих поразрядную сортировку для длинных ключей или записей, поскольку для работы с такими данными обычно применяются указатели. Поэтому дополнительная память нужна только для переупорядочения указателей, и ее объем мал по сравнению с памятью, отведенной под сами ключи и записи (хотя все-таки заметен). Если памяти достаточно, и важно в первую очередь быстродействие (обычная ситуация при использовании поразрядной сортировки), можно также сэкономить время на копирование массива с помощью рекурсивных переключений направления просмотра, как это было сделано для сортировки слиянием в разделе 8.4 .

Пример поразрядной MSD-сортировки (с пустыми контейнерами) Уже на втором этапе сортировки небольших файлов получается множество пустых корзин

(рис 10.8) Пример поразрядной MSD-сортировки (с пустыми контейнерами) Уже на втором этапе сортировки небольших файлов получается множество пустых корзин

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

Другой естественный путь реализации MSD-сортировки — использование связных списков. Каждый контейнер представляется отдельным связным списком: на первом проходе по сортируемым элементам каждый элемент вставляется в соответствующий связный список, определяемый старшей цифрой. Далее подсписки сортируются, после чего объединяются в единое отсортированное целое. Такой подход представляет собой достаточно трудную задачу программирования (см. упражнение 10.36). Объединение связных списков требует отслеживания начала и конца каждого из этих списков, и, естественно, специальной обработки пустых списков, которых, очевидно, будет много.

Чтобы добиться высокой производительности поразрядной сортировки в каком-либо приложении, нужно ограничить число пустых контейнеров с помощью выбора соответствующего значения как основания системы счисления, так и размера отсекаемых небольших подфайлов. В качестве конкретного примера предположим, что требуется отсортировать 224 (около шестнадцати миллионов) 64-разрядных целых чисел. Чтобы использовать таблицу счетчиков, меньшую по размеру, чем размер файла, можно выбрать основание R = 216, соответствующее проверке 16 разрядов ключа. Но после первого разбиения средний размер файла составит всего лишь 2²⁸, а основание системы счисления 2¹⁶ слишком велико для таких небольших файлов. Что еще хуже, таких файлов может быть очень много: в рассматриваемом случае порядка 216. Для каждого из этих 2¹⁶ файлов процедура сортировки обнуляет 2¹⁶ счетчиков, затем проверяет, какие из них не равны нулю и так далее — выполняя по меньшей мере 2³² арифметических операций. Программа 10.2, реализованная в предположении, что большая часть контейнеров не пуста, выполняет достаточно большое число арифметических операций для каждого пустого контейнера (например, она выполняет рекурсивные вызовы для всех пустых контейнеров), так что для рассматриваемого примера время выполнения окажется очень большим. Более подходящим основанием для второго уровня может быть 28 или 24. Короче говоря, для MSD-сортировки небольших файлов не стоит использовать большие основания систем счисления. Этот вопрос будет подробно рассмотрен в разделе 10.6, при изучении производительности различных методов.

Если положить R = 256 и отказаться от рекурсивного вызова для контейнера 0, то программа 10.2 становится эффективным методом сортировки строк в стиле С. Если также известно, что длина всех строк не превышает некоторой фиксированной величины, то можно ввести специальную переменную bytesword для хранения этой величины, либо отказаться от сравнения с bytesword и выполнять сортировку обычных символьных строк переменной длины. Для сортировки строк мы обычно будем реализовывать абстрактную операцию digit в виде единственной ссылки на массив, как описано в разделе 10.1. С помощью подбора значений R и bytesword (и их проверки) программу 10.2 можно легко модифицировать для работы со строками символов из нестандартных алфавитов, со строками нестандартных форматов, с учетом ограничений по длине или других вариантов.

Сортировка строк еще раз показывает важность правильной обработки пустых контейнеров. На рис 10.8 показан процесс разбиения для примера наподобие рис. 10.7 рис 10.7, но для слов из двух букв и с явно показанными пустыми контейнерами. В этом примере с помощью поразрядной сортировки по основанию 26 сортируются двухбуквенные слова, поэтому на каждой стадии сортировки имеется 26 контейнеров. На первом этапе число пустых контейнеров невелико, однако на втором этапе пустые контейнеры преобладают.

Функция MSD-сортировки выполняет разбиение файла по первой цифре ключей, затем рекурсивно вызывает себя для обработки подфайлов, соответствующих каждому значению. На рис. 10.9 рис 10.9 представлена структура рекурсивных вызовов MSD-сортировки для примера, показанного на рис 10.8. Структура вызовов соответствует многопутевому trie-дереву — прямому обобщению структуры trie-дерева для бинарной быстрой сортировки, показанной на рис 10.4. Каждый узел соответствует рекурсивному вызову MSD-сортировки некоторого подфайла. Например, поддерево корня с буквой o в корне соответствует сортировке подфайла из трех ключей: of, on и or.

Из этих рисунков легко видеть, что в процессе MSD-сортировки строк появляется значительное число пустых контейнеров. В разделе 10.4 мы рассмотрим способ решения этой проблемы, а в главе 15 изучим явное использование trie-структур в приложениях, применяющих обработку строк. В общем случае мы будем работать с компактными представлениями trie-структур, которые не содержат узлов, соответствующих пустым контейнерам, и в которых метки перенесены с ребер на их нижние узлы (как на .

Основная трудность в достижении на практике максимальной эффективности MSD-сортировки ключей, представляющих собой длинные строки, состоит в недостаточной случайности сортируемых данных. Часто эти ключи содержат длинные последовательности одинаковых или ненужных элементов, либо их части находятся в узком диапазоне. Например, приложение, обрабатывающее записи с данными о студентах, может иметь дело с ключами, поля которых содержат год выпуска (четыре байта, но только одно из четырех значений), название штата (максимум 10 байтов, но только одно из 50 возможных значений) и пол (1 байт с одним из двух возможных значений), а также поле фамилии студента (это больше похоже на случайную строку, но оно не обязательно короткое, буквы не распределены равномерно и, если длина фиксирована, то в конце может быть много пробелов). Все эти ограничения приводят к образованию в процессе MSD-сортировки большого количества пустых контейнеров (см. упражнение 10.23).

(рис 10.9) Рекурсивная структура поразрядной MSD-сортировки

Это дерево соответствует выполнению рекурсивной MSD-сортировки из программы 10.2 для примера упорядочения двухбуквенных ключей методом MSD-сортировки, представленного на рис 10.8. Если размер файла равен 0 или 1, рекурсивные вызовы не выполняются. В остальных случаях выполняются 26 вызовов, по одному на каждое возможное значение текущего байта.

(рис 10.10) Рекурсивная структура поразрядной MSD-сортировки (с игнорированием пустых подфайлов)

Данное представление рекурсивной структуры MSD-сортировки более компактно, чем представление на рис 10.9. Каждый узел этого дерева помечен значением (i — 1)-ой цифры соответствующего ключа, где i — расстояние от узла до корня. Каждый путь от корня до нижнего уровня дерева соответствует какому-либо ключу, который получается слитной записью меток узлов. Данное дерево соответствует представленному на 10.7примеру MSD-сортировки трехбуквенных ключей.

Один из практических способов решения этой проблемы заключается в разработке более сложной реализации абстрактной операции доступа к байтам, которая учитывает любые специальные сведения о сортируемых строках. Другой метод, который достаточно просто реализуется и называется эвристикой распределения контейнеров (bin-span heuristics), заключается в отслеживании на стадии подсчета начального и конечного значений диапазона значений непустых контейнеров, и использовании в дальнейшем только контейнеров, попадающих в этот диапазон (возможно, включая некоторые специальные случаи, вроде нулевых или пробельных ключей). Такое усовершенствование удобно для ситуаций, описанных в предыдущем абзаце. Например, в случае алфавитноцифровых данных с основанием системы счисления 256 можно работать в одном разделе с числовыми ключами и получить лишь 10 непустых контейнеров, соответствующих цифрам, а в другом разделе — с заглавными английскими буквами и получить 26 непустых контейнеров, соответствующих этим буквам.

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

Упражнения

10.14. Начертите компактную trie-структуру (без пустых контейнеров и с ключами в узлах, как на рис 10.10), соответствующую рис 10.9.

10.15. Сколько узлов содержит полное trie-дерево, соответствующее рис 10.10?

10.16. Покажите, как выполняется разбиение MSD-сортировкой набора ключей now is the time for all good people to come the aid of their party.

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

10.18. Напишите программу, которая решает задачу обобщенного R-путевого разбиения с помощью метода, описанного в общих чертах в упражнении 10.17.

10.19. Напишите программу, которая генерирует случайные 80-байтовые ключи, а потом сортирует их методом поразрядной MSD-сортировки для N = 10³, 10⁴, 10⁵ и 10⁶. Добавьте возможность вывода общего количества байтов, проверенных в процессе каждой сортировки.

10.20. Чему равно ожидаемое крайнее правое положение байта ключа, к которому обратится программа из упражнения 10.19 для каждого заданного значения N? Если вы сделали упражнение 10.19, вставьте в программу вывод этого значения и сравните результаты теоретических расчетов с результатами, полученными опытным путем.

10.21. Напишите генератор ключей, который порождает ключи путем перетасовки случайной 80-байтной последовательности. Воспользуйтесь полученной реализацией для генерации N случайных ключей, затем упорядочьте их методом MSD-сортировки для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните полученную производительность с аналогичным результатом для действительно случайных ключей (см. упражнение 10.19).

10.22. Чему равно ожидаемое крайнее правое положение байта ключа, к которому обратится программа из упражнения 10.21 для каждого значения N? Если вы сделали упражнение 10.21, сравните результаты теоретических расчетов с результатами, полученными опытным путем.

10.23. Напишите генератор ключей, который порождает случайные 30-байтовые строки, состоящие из четырех полей: 4-байтовое поле, содержащее одну из 10 заданных строк; 10-байтовое поле, содержащее одну из 50 заданных строк; 1-байтовое поле, содержащее одно из двух возможных значений; и 15-байтовое поле, содержащее случайную выровненную влево строку длиной от 4 до 15 символов (с равной вероятностью). Воспользуйтесь полученной реализацией для генерации N случайных ключей, а затем упорядочьте их методом MSD-сортировки для N = 10³, 10⁴, 10⁵ и 10⁶. Добавьте в генератор возможность вывода общего количества проверенных байтов ключей. Сравните достигнутую производительность с аналогичным результатом для действительно случайных ключей (см. упражнение 10.19).

10.24. Реализуйте в программе 10.2 эвристику распределения контейнеров. Проверьте работу программы на данных из упражнения 10.23.

Трехпутевая поразрядная быстрая сортировка

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

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

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

Программа 10.3. Трехпутевая поразрядная быстрая сортировка

Данная MSD-сортировка по существу эквивалентна коду быстрой сортировки с трехпутевым разбиением (программа 7.5), но отличается от нее следующим: (1) обращения к ключам заменены обращениями к байтам ключей, (2) текущая позиция байта передается рекурсивной программе в виде параметра, и (3) рекурсивные вызовы для среднего подфайла переходят к следующему байту. Чтобы индексы не выходили за пределы строк, перед рекурсивными вызовами с переходом к следующему байту выполняется проверка, равно ли 0 центральное значение. Если центральное значение равно 0, то левый подфайл пуст, средний под-файл соответствует найденным равным ключам, а правый подфайл соответствует более длинным строкам, которые требуют дальнейшей обработки.

  #define ch(A) digit(A, d)
  template <class Item>
  void quicksortX(Item a[], int l, int r, int d)
    { int i, j, k, p, q; int v;
      if (r-l <= M) { insertion(a, l, r); return; }
      v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
      while ( i < j )
        { while (ch(a[ + + i]) < v) ;
          while (v < ch(a[-- j ] ) ) if (j == l) break;
          if (i > j) break;
          exch(a[i], a[j]);
          if (ch(a[i]) == v) { p++; exch(a[p], a[i]); }
          if (v == ch(a[j])) { q—; exch(a[j], a[q]); }
        }
      if (p == q)
       { if (v != '\0') quicksortX(a, l, r, d+1); return; }
      if (ch(a[i]) < v) i++;
      for (k = l; k <= p; k+ + , j--) exch(a[k], a[j]);
      for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
      quicksortX(a, l, j, d);
      if ((i == r)  (ch(a[i]) == v)) i+ + ;
      if (v != '\0') quicksortX(a, j + 1, i-1, d+1);
      quicksortX(a, i, r, d);
    }

(рис 10.11) Трехпутевая поразрядная быстрая сортировка

Файл делится на три части: слова, начинающиеся с букв от a до i, слова, начинающиеся c буквы j, и слова, начинающиеся с букв от к до z. Затем сортировка рекурсивно продолжается.

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

На рис 10.11 приведен пример действия этого метода при сортировке трехбуквенных слов, представленных на рис 10.7, а на рис 10.12 показана структура рекурсивных вызовов. Каждый узел соответствует в точности трем рекурсивным вызовам: для ключей с меньшим значением первого байта (левый потомок), для ключей с тем же значением первого байта (средний потомок) и для ключей с большим значением первого байта (правый потомок).

Если сортируемые ключи соответствуют абстракции из раздела 10.2, стандартную быструю сортировку и все другие методы сортировки, рассмотренные в главах 6—9, можно рассматривать как MSD-сортировку, поскольку функция сравнения осуществляет доступ сначала к наиболее значащей части ключа (см. упражнение 10.3).

(рис 10.12) Рекурсивная структура трехпутевой поразрядной быстрой сортировки

Данная комбинация обычного и trie-дерева соответствует замене 26-путевыхузлов в trie-дереве, изображенном на рис 10.10, на тернарные деревья бинарного поиска, как показано на рис 10.13. Любой путь от корня вниз, который оканчивается средней связью, определяет ключ файла — с помощью символов, указанных средними ссылками на этом пути. На рис 10.10 имеется 1035 не показанных пустых ссылок, на данном рисунке показаны все 155 пустых ссылок этого дерева. Каждая пустая ссылка соответствует пустому контейнеру, так что это различие показывает, как существенно трехпутевоеразбиение может сократить число пустых контейнеров, которые появляются при MSD-сортировке.

(рис 10.13) Пример узлов trie-дерева трехпутевой поразрядной быстрой сортировки

Трехпутевая поразрядная быстрая сортировка решает проблему пустых корзин, характерную для MSD-сортировки, с помощью выполнения трехпутевого разбиения: значение одного байта устраняется, а остальные обрабатываются дальше. Это действие соответствует замене каждого M-путевого узла trie—дерева, описывающего рекурсивную структуру вызовов MSD-сортировки (см. рис.10.9), на троичное дерево, в котором каждому непустому контейнеру соответствует внутренний узел. Для полных узлов (слева) такое изменение требует затрат времени и почти не экономит память, но для пустых узлов (справа) затраты времени минимальны, а экономия памяти значительна.

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

Рассмотрим случай, когда ключи имеют большую длину (для простоты — фиксированную), но большинство старших байтов совпадают. В такой ситуации время выполнения обычной быстрой сортировки пропорционально длине слова, помноженной на 2 Nln N, тогда как время выполнения поразрядной версии пропорционально N, умноженному на длину слова (чтобы обнаружить все равные между собой старшие байты) плюс 2 Nln N (для сортировки оставшихся коротких ключей). Иначе говоря, этот метод может работать в ln N раз быстрее, чем обычная быстрая сортировка, если учитывать только затраты на сравнения. На практике в приложениях сортировки подобные характеристики ключей не являются чем-то необычным (см. упражнение 10.25).

Другим интересным свойством трехпутевой поразрядной быстрой сортировки является то, что ее характеристики не зависят напрямую от значения основания системы счисления. Для других методов поразрядной сортировки необходим вспомогательный массив, индексированный по основанию системы счисления, и нужно, чтобы размер этого массива не был намного больше размера самого файла. Для данного метода такой массив не нужен. Если в качестве основания взять очень большое значение (больше длины слова), то рассматриваемый метод превращается в обычную быструю сортировку, а если в качестве основания взять число 2, то в обычную бинарную быструю сортировку. Промежуточные же значения основания системы счисления позволяют эффективно делить ключи на равные части.

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

Трехпутевая быстрая сортировка успешно применяется и в тех случаях, когда сортируемыми ключами являются векторы (или в математическом смысле, или в смысле стандартной библиотеки шаблонов C++). Другими словами, если ключи составлены из независимых компонентов (каждый из которых сам является абстрактным ключом), можно упорядочить записи таким образом, что они будут располагаться в порядке возрастания первых компонентов ключей и в порядке возрастания вторых компонентов ключей, если равны их первые компоненты и т.д. Сортировку векторов можно рассматривать как обобщение поразрядной сортировки, в котором R может быть произвольно большим. После соответствующей модификации программа 10.3 будет называться многомерной быстрой сортировкой (multikey quicksort).

Упражнения

10.25. Пусть ключи состоят из d байтов (d > 4), причем последние 4 байта принимают случайные значения, а все остальные равны 0. Оцените количество просмотренных байтов при упорядочении с помощью трехпутевой поразрядной быстрой сортировки (программа 10.3) и стандартной быстрой сортировки (программа 7.1) больших файлов размером N, и вычислите отношение значений времени выполнения сортировок.

10.26. Определите опытным путем размер байта, для которого время выполнения трехпутевой сортировки случайных 64-разрядных ключей минимально, при N = 10³, 10⁴, 10⁵ и 10⁶.

10.27. Разработайте реализацию трехпутевой поразрядной быстрой сортировки для связных списков.

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

10.29. Используя генератор ключей из упражнения 10.19, выполните трехпутевую поразрядную быструю сортировку для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните ее производительность с производительностью MSD-сортировки.

10.30. Используя генератор ключей из упражнения 10.21, выполните трехпутевую поразрядную быструю сортировку для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните ее производительность с производительностью MSD-сортировки.

10.31. Используя генератор ключей из упражнения 10.23, выполните трехпутевую поразрядную быструю сортировку для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните ее производительность с производительностью MSD-сортировки.

Поразрядная LSD-сортировка

Другой метод поразрядной сортировки просматривает байты в направлении справа налево. На рис 10.14 показано, как задача сортировки трехбуквенных слов решается за три прохода по файлу.

(рис 10.14) Пример поразрядной LSD-сортировки

Метод LSD-сортировки упорядочивает трехбуквенные слова за три прохода (слева направо).

Файл сначала сортируется по последней букве (методом распределяющего подсчета), потом по средней букве, а затем по первой.

Сначала не так легко поверить, что этот метод работает — вообще-то он и не работает, если используемый метод сортировки неустойчив (см. определение 6.1). После того, как определена необходимость устойчивости, уже нетрудно доказать, что LSD-сортировка работает: мы знаем, что после сортировки ключей по i последним байтам (при соблюдении устойчивости) любые два ключа в файле упорядочены (по просмотренным на текущий момент байтам) — либо потому, что первые из i последних байтов отличны друг от друга (и упорядочены по этому байту), либо потому, что первые из i последних байтов совпадают, (и они уже упорядочены в силу устойчивости).

Иначе говоря, если w — i еще не просмотренных байтов какой-либо пары ключей идентичны, то любое различие между этими ключами определяется уже просмотренными i байтами, так что эти ключи должным образом упорядочены, и сохранят этот порядок в силу свойства устойчивости. Если же w — i еще не просмотренных байтов различны, то уже просмотренные i байтов не играют никакой роли, и какой-то из следующих проходов правильно упорядочит эту пару по одному из более значащих байтов.

Требование устойчивости означает, например, что метод разбиения, используемый в бинарной быстрой сортировке, не может быть использован в бинарной версии такой сортировки справа налево. С другой стороны, метод распределяющего подсчета является устойчивым, что сразу же приводит нас к классическому и эффективному алгоритму. Программа 10.4 представляет собой реализацию этого метода. Очевидно, здесь для перераспределения ключей нужен вспомогательный массив — способы, описанные в упражнениях 10.19 и 10.20 и выполняющие распределение без использования дополнительной памяти, не используют дополнительный массив за счет устойчивости.

Метод LSD-сортировки использовался в старых машинах для сортировки перфокарт. Такие машины могли распределять колоду перфокарт по 10 карманам в соответствии с отверстиями, пробитыми в каком-то столбце. Если в некотором наборе столбцов пробиты определенные числа, оператор может отсортировать перфокарты, пропустив их через машину по крайней правой цифре, затем, собрав все перфокарты в одну колоду, снова пропустить их через машину, по предпоследней цифре, и т.д. Физическая сортировка перфокарт представляет собой устойчивый процесс, который и имитирует сортировка методом распределяющего подсчета. Эта версия LSD-сортировки не только широко использовалась в коммерческих целях в пятидесятых и шестидесятых годах прошлого столетия, но ей пользовались и многие осторожные программисты, которые пробивали в последних колонках перфокарт их порядковые номера в колоде — чтобы можно было механически упорядочить перфокарты, если колода случайно рассыплется.

Программа 10.4. Поразрядная LSD-сортировка

Данная программа реализует распределяющий подсчет по байтам слов, но продвигаясь справа налево. Реализация метода распределяющего подсчета должна быть устойчивой. Если R равно 2 (то есть bytesword и bitwords равны), данная программа является прямой поразрядной сортировкой, т.е. поразрядной сортировкой с просмотром битов справа налево (см. рис 10.15).

  template <class Item>
  void radixLSD(Item a[], int l, int r)
    { static Item aux[maxN];
      for (int d = bytesword-1; d >= 0; d—)
        { int i, j, count[R+1];
          for (j = 0; j < R; j + +) count[j] = 0;
          for (i = l; i <= r; i++)
            count[digit(a[i], d) + 1]++;
          for (j = 1; j < R; j++)
            count[j] += count[j-1];
          for (i = l; i <= r; i++)
            aux[count[digit(a[i], d)]++] = a[i];
          for (i = l; i <= r; i++) a[i] = aux[i];
        }
    }

(рис 10.15) Пример (бинарной) LSD-сортировки (показаны разряды ключей)

На данной диаграмме показано выполнение поразрядной сортировки справа налево на нашем бессменном примере. i-й столбец вычисляется из (i — 1)-го столбца путем извлечения (сохраняя устойчивость) всех ключей с 0 в i-ом разряде, а затем всех ключей с 1 в i-ом разряде. Если перед операцией извлечения (i — 1)-й столбец был упорядочен по (i — 1) последним разрядам ключей, то после операции i-й столбец будет упорядочен по i последним разрядам ключей. Здесь явно показано перемещение ключей на третьем этапе.

На рис 10.15 показана работа бинарной LSD-сортировки на примере упорядочения тех же ключей, что и на рис 10.3. Для рассматриваемых 5-разрядных ключей полное упорядочение достигается за пять проходов по ключам справа налево. Сортировка записей с одноразрядным ключом сводится к разбиению файла таким образом, что все записи с ключом 0 находятся перед записями с ключом 1. Как уже было сказано, стратегия разбиения, рассмотренная в начале данной главы в программе 10.1, не может быть использована в силу ее неустойчивости, хотя она вроде бы решает ту же задачу. Имеет смысл рассмотреть поразрядную сортировку с основанием 2, поскольку во многих случаях ее удобно реализовать на высокопроизводительных машинах или с помощью специальной аппаратуры (см. упражнение 10.38). В программах мы используем максимально возможное число разрядов, чтобы уменьшить число проходов, и ограничены только размерами массива счетчиков (см. рис 10.16).

(рис 10.16) Динамические характеристики поразрядной LSD-сортировки

На этой диаграмме показаны этапы LSD-сортировки случайных 8-разрядных ключей, по основанию 2 (слева) и 4 (справа); последняя включает в себя каждый второй этап из диаграммы для основания 2. Например, когда остаются два разряда (второй этап с конца на левой диаграмме, предпоследний на правой диаграмме), сортируемый файл состоит из четырех перемежающихся отсортированных подфайлов, которые состоят из ключей, начинающихся с 00, 01, 10 и 11.

Применение LSD-подхода к сортировке строк обычно затруднено из-за переменной длины ключей. В случае MSD-сортировки достаточно легко сравнивать ключи по их старшим байтам, но LSD-сортировка предполагает постоянную длину ключа, при этом ведущие байты используются только на заключительном проходе. Даже в случае ключей (большой) фиксированной длины LSD-сортировка, очевидно, выполняет бесполезную работу на последних байтах ключей, поскольку, как мы уже убедились, в процессе сортировки обычно важны только левые части ключей. Способ решения этой проблемы будет показан в разделе 10.7, после подробного изучения свойств поразрядной сортировки.

Упражнения

10.32. Используя генератор ключей из упражнения 10.19, выполните LSD-сортировку для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните показатели этой сортировки с параметрами MSD-сортировки.

10.33. Используя генератор ключей из упражнений 10.21 и 10.23, выполните LSD-сортировку для N = 10³, 10⁴, 10⁵ и 10⁶. Сравните показатели этой сортировки с параметрами MSD-сортировки.

10.34. Приведите (несортированный) результат выполнения LSD-сортировки на основе разбиения бинарной быстрой сортировки, для примера, представленного на рис.10.15.

10.35. Приведите результат применения LSD-сортировки для упорядочения по двум первым символам совокупности ключей now is the time for all good people to come the aid of their party.

10.36. Разработайте реализацию LSD-сортировки для связных списков.

10.37. Найдите эффективный метод, который (1) переупорядочивает записи файла таким образом, что записи, начинающиеся с бита 0, находятся перед записями, начинающимися с бита 1, (2) использует объем дополнительной памяти, пропорциональный квадратному корню из количества записей (или менее), и (3) устойчив.

10.38. Реализуйте метод, который сортирует массив 32-разрядных слов, используя лишь следующую абстрактную операцию: для заданной позиции i и указателя на элемент массива a[k] упорядочить (с сохранением устойчивости) элементы a[k], a[k+1], ..., a[k+63] таким образом, чтобы слова с битом 0 в i-ой позиции находились перед словами с битом 1 в i-ой позиции.

Характеристики производительности поразрядных сортировок

Время выполнения LSD-сортировки при упорядочении N записей с ключами, состоящими из w байтов, пропорционально Nw, поскольку алгоритм совершает w проходов по всем N ключам. Как показано на рис.10.17, это свойство не зависит от характера входных данных.

Для случая длинных ключей и коротких байтов это время сравнимо с Nlg N: например, если бинарная LSD-сортировка используется для сортировки 1 миллиарда 32-разрядных ключей, то и w, и lg N примерно равны 32. Для более коротких ключей и более длинных байтов время выполнения сравнимо с N: например, если 64-разрядные ключи рассматриваются по 16-разрядному основанию системы счисления, то w равно небольшой константе — 4.

(рис 10.17) Динамические характеристики поразрядной LSD-сортировки для различных видов файлов

На данных диаграммах представлены этапы LSD-сортировки для файлов с 200 записями: случайных с равномерным распределением, случайных с нормальным распределением, почти упорядоченных, почти обратно упорядоченных и случайно упорядоченных с 10 различными ключами (слева направо). Время выполнения не зависит от исходного порядка входных данных. Три файла с одним и тем же набором ключей (первый, третий и четвертый файлы — перестановки целых чисел от 1 до 200) имеют на завершающих этапах сортировки похожий вид.

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

Лемма 10.1. В худшем случае поразрядная сортировка выполняет проверку всех байтов во всех ключах.

Другими словами, различные виды поразрядной сортировки являются линейными в том смысле, что затрачиваемое время не более чем пропорционально количеству цифр во входных данных. Это утверждение непосредственно следует из анализа программ: ни одна из цифр не проверяется дважды. Для всех рассмотренных программ худшим случаем является ситуация, когда все ключи одинаковы. $$$\blacksquare$$$

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

Лемма 10.2. При сортировке ключей, состоящих из случайных битов, бинарная быстрая сортировка в среднем проверяет Nlg N разрядов.

Если размер файла равен степени 2, а биты принимают случайные значения, то можно ожидать, что одна половина старших битов равна 0, а другая половина — 1, поэтому, как и в случае быстрой сортировки в , данная ситуация описывается рекуррентным соотношением C_N = 2C_N/2 + N. Опять-таки, это описание ситуации недостаточно точно, поскольку точка разбиения попадает в середину файла только в среднем (и поскольку количество битов в ключе конечно). Однако для бинарной быстрой сортировки вероятность попадания точки разбиения в окрестность центра выше, чем для стандартной быстрой сортировки, поэтому старший член выражения, определяющего время выполнения сортировки, тот же, что и для идеальных разбиений. Подробный анализ, доказывающий этот результат, впервые выполнен Кнутом в 1973 г. и представляет собой классический пример анализа алгоритмов (см. раздел ссылок). $$$\blacksquare$$$

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

Лемма 10.3. MSD-сортировка с основанием системы счисления R требует выполнения по меньшей мере 2N + 2R шагов для упорядочения файла размером N.

MSD-сортировка требует выполнения по меньшей мере одного прохода распределяющего подсчета, а распределяющий подсчет состоит из не менее двух проходов по записям (один для подсчета, другой для распределения) — это минимум 2N шагов, и еще двух проходов по счетчикам (один для их обнуления в начале, а другой для определения концов подфайлов) — еще минимум 2R шагов.$$$\blacksquare$$$

Данное свойство выглядит тривиальным, но оно играет весьма важную роль в понимании MSD-сортировки. В частности, из него следует, что нельзя утверждать, что время выполнения сортировки снижается при уменьшении N, поскольку R может быть намного больше, чем N. Короче говоря, для сортировки небольших файлов следует использовать другие методы. Этот вывод является решением проблемы пустых контейнеров, которая была рассмотрена в конце раздела 10.3. Например, если R равно 256, а N равно 2, то MSD-сортировка будет в 128 раз медленнее, чем более простой метод с обычным сравнением элементов. Рекурсивная структура MSD-сортировки приводит к тому, что рекурсивная программа будет многократно вызывать себя для большого количества небольших файлов. Поэтому игнорирование проблемы пустых контейнеров в рассматриваемом примере может привести к замедлению всей поразрядной сортировки в 128 раз. Что касается промежуточных ситуаций (например, если R равно 256, а N равно 64), то затраты будут не столь катастрофичными, но все же существенными. Использовать сортировку вставками не стоит, поскольку ее N₂/4 сравнений — это слишком медленно; игнорировать проблему пустых контейнеров не стоит, поскольку их очень много. Простейший путь решения этой проблемы состоит в использовании основания системы счисления, которое меньше размера сортируемого файла.

Лемма 10.4. Если основание системы счисления всегда меньше размера файла, то число шагов, выполняемых MSD-сортировкой, равно в среднем N log_RN с небольшим постоянным множителем (для ключей, состоящих из случайных байтов), а в худшем случае — количеству байтов в ключе с небольшим постоянным множителем.

Результат для худшего случая непосредственно следует из предыдущих рассуждений, а оценка для среднего случая следует из обобщения анализа, выполненного для леммы 10.2. При больших R множитель log_RN мал, поэтому для практических целей можно считать, что общее время пропорционально N. Например, если R = 216, то log_RN меньше 3 для всех N < 2⁴⁸, что охватывает все практически возможные размеры файлов. $$$\blacksquare$$$

Как и лемма 10.2, лемма 10.4 позволяет сделать важный для практических приложений вывод о том, что MSD-сортировка случайных ключей достаточно большой длины фактически является сублинейной функцией от общего количества разрядов в ключах. Например, при сортировке 1 миллиона 64-разрядных случайных ключей потребуется проверка 20—30 старших разрядов ключей, т.е. менее половины всех данных.

Лемма 10.5. При упорядочении N ключей (произвольной длины) трехпутевая поразрядная быстрая сортировка выполняет в среднем 2N lnN сравнений байтов.

Возможны два поучительных толкования этого результата. Во-первых, если считать рассматриваемый метод эквивалентным разбиению быстрой сортировкой по старшему разряду, и затем (рекурсивному) использованию этого метода к полученным подфайлам, то неудивительно, что общее число операций примерно такое же, как и в случае нормальной быстрой сортировки — но это сравнения отдельных байтов, а не полных ключей. Во вторых, рассматривая этот метод с точки зрения, показанной на рис 10.13, можно ожидать, что время выполнения Nlog_RN из свойства 10.3 следует умножить на 2 lnR, поскольку для упорядочения R байтов требуется 2R lnR шагов быстрой сортировки — в отличие от R шагов для тех же байтов в trie-дереве. Полное доказательство мы опускаем (см. раздел ссылок). $$$\blacksquare$$$

Лемма 10.6. LSD—сортировка может упорядочить N записей с w-разрядными ключами за w / lg R проходов, используя дополнительную память для R счетчиков (и буфера для переупорядочения файла).

Доказательство этого факта непосредственно вытекает из реализации. В частности, если взять R = 2^w/4, получится четырехпроходная линейная сортировка. $$$\blacksquare$$$

Упражнения

10.39. Предположим, что входной файл состоит из 1000 копий каждого из чисел от 1 до 1000, каждое в виде 32-разрядного слова. Опишите, как воспользоваться этими сведениями, чтобы получить быстрый вариант поразрядной сортировки.

10.40. Предположим, что входной файл состоит из 1000 копий каждого из тысячи различных 32-разрядных чисел. Опишите, как воспользоваться этими сведениями, чтобы получить быстрый вариант поразрядной сортировки.

10.41. Каково общее количество байтов, проверяемых в худшем случае трехпутевой поразрядной быстрой сортировкой при упорядочении строк байтов фиксированной длины?

10.42. Эмпирически сравните количество байтов, проверяемых трехпутевой поразрядной быстрой сортировкой при упорядочении длинных строк для N = 10³, 10⁴, 10⁵ и 10⁶, с количеством сравнений в случае стандартной быстрой сортировки тех же файлов.

о 10.43. Приведите количество байтов, проверяемых при выполнении MSD-сортировки и трехпутевой поразрядной быстрой сортировки для файла с N ключами А, АА, ААА, АААА, ААААА, АААААА, ... .

Сортировки с сублинейным временем выполнения

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

Реализация LSD-сортировки, приведенная в разделе 10.5, выполняет bytesword проходов по файлу. Увеличив R, мы получим эффективный метод сортировки — для достаточно больших N и при наличии достаточной памяти для R счетчиков. Как отмечалось при доказательстве свойства 10.5, лучше сделать так, чтобы значение lg R (количество битов в байте) было равно примерно четверти размера слова — тогда поразрядная сортировка будет состоять из четырех проходов распределяющей сортировки. Проверяется каждый бит каждого ключа, но каждый ключ содержит всего четыре цифры. Этот пример является прямой аналогией архитектуры многих компьютеров: в типичной организации используются 32-разрядные слова, состоящие из четырех 8-разрядных байтов. Мы извлекаем из слов байты, а не биты, и на многих компьютерах этот подход гораздо более эффективен. Теперь каждый проход распределяющего подсчета линеен по времени, а поскольку их всего четыре, то и вся сортировка линейна — вряд ли для сортировки можно надеяться на лучший результат.

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

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

(рис 10.18) Динамические характеристики LSD-сортировки по MSD-разрядам

Если ключи представляют собой последовательности случайных битов, то сортировка файла по старшим разрядам ключей почти упорядочивает файл. На этой диаграмме шестипроходная LSD-сортировка (слева) файла со случайными 6-разрядными ключами сравнивается с трехпроходной LSD-сортировкой, после которой может быть еще один проход сортировки вставками (справа). Второй способ быстрее почти в два раза.

Для некоторых размеров файлов, возможно, имеет смысл использовать дополнительную память (которая иначе была бы отведена под вспомогательный массив), чтобы попытаться обойтись всего лишь одним проходом распределяющего подсчета, выполняя переупорядочение на месте. Например, сортировка 1 миллиона 32-разрядных случайных ключей может быть выполнена за один проход распределяющего подсчета по 20 старшим разрядам с последующей сортировкой вставками. Для этого требуется память только для (1 миллиона) счетчиков — значительно меньше, чем нужно для вспомогательного массива. Использование этого метода равносильно использованию стандартной MSD-сортировки при R=2²⁰, хотя для сортировки таким методом небольших файлов важно применять небольшие основания системы счисления (см. обсуждение леммы 10.4).

LSD-подход к поразрядной сортировке получил широкое распространение в силу того, что ему нужны лишь исключительно простые управляющие структуры, а его базовые операции очень удобны для реализации в машинных командах и могут быть легко адаптированы к использованию специализированных высокопроизводительных аппаратных средств. В такой среде наибольшее быстродействие может быть достигнуто при использовании полной LSD-сортировки. Ценой затрат дополнительной памяти лишь для размещения N дополнительных ссылок (и R счетчиков) можно получить метод, который может сортировать случайно упорядоченные файлы всего за три-четыре прохода.

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

Алгоритмы общего назначения, такие как быстрая сортировка, нашли более широкое применение, чем поразрядная сортировка, поскольку они могут быть адаптированы к более широкому диапазону приложений. Основная причина такого положения дел заключается в том, что абстракция ключа, на которой построена поразрядная сортировка, обладает меньшей универсальностью, чем та, которая использовалась в главах 6—9 (с функцией сравнения). Например, один из широко распространенных способов взаимодействия со служебной программой сортировки заключается в том, что клиент сам обеспечивает функцию сравнения. Примером может служить интерфейс, используемый программой qsort из библиотеки программ на C++. Это соглашение не только годится в ситуациях, когда клиент может, воспользовавшись специальными сведениями о составных ключах, реализовать быстрое сравнение, но и позволяет выполнять сортировку, используя отношения порядка, которые могут вообще обходиться без ключей. Один такой алгоритм будет рассмотрен в .

Если возможно использование быстрой сортировки и различных алгоритмов поразрядной сортировки из рассмотренных в данной главе, то выбор между ними (и различными родственными версиями быстрой сортировки!) будет зависеть не только от свойств приложения (таких как размеры ключей, записей и файла), но также и от свойств среды программирования и аппаратуры, которые определяют эффективность доступа и использования отдельных битов и байтов. В таблица 10.1 и таблица 10.2 приведены эмпирические результаты, которые подтверждают вывод, что линейная или сублинейная производительности, рассмотренные нами для различных приложений поразрядной сортировки, делают эти методы сортировки привлекательными для различных подходящих приложений.

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

Эмпирическое сравнение поразрядных сортировок (целочисленные ключи)
N	Q	4-разрядные байты		8-разрядные байты			16-разрядные байты
N	Q	M	L	M	L	L*	M	L	M*
12500	2	7	11	28	4	2	52	5	8
25000	5	14	21	29	8	4	54	8	15
50000	10	49	43	35	18	9	58	15	39
100000	21	77	92	47	39	18	67	30	77
200000	49	133	185	72	81	39	296	56	98
400000	102	278	377	581	169	88	119398	110	297
800000	223	919	732	6064	328	203	1532492	219	2309

Обозначения:
Q	Быстрая сортировка, стандартная (программа 7.1)
M	MSD-сортировка, стандартная (программа 10.2)
L	LSD-сортировка (программа 10.4)
M*	MSD-сортировка, с адаптацией основания системы счисления под размер файла
L*	LSD-сортировка по MSD-разрядам.

Эмпирическое сравнение поразрядных сортировок (строковые ключи)
N	Q	T	M	F	R	X	X*
12500	7	6	9	9	8	6	5
25000	14	12	18	19	15	11	10
50000	34	26	39	49	34	25	24
100000	83	61	87	114	71	57	54

Обозначения:
Q	Быстрая сортировка, стандартная (программа 7.1)
T	Быстрая сортировка с трехпутевым разбиением (программа 7.5)
M	Сортировка слиянием (программа 8.2)
F	Пирамидальная сортировка с усовершенствованием Флойда (см. раздел 9.4 )
R	MSD-сортировка (программа 10.2)
X	Трехпутевая поразрядная быстрая сортировка (программа 10.3)
X*	Трехпутевая поразрядная быстрая сортировка (с отсечениями)

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

Упражнения

10.44. Каков основной недостаток выполнения LSD-сортировки по старшим битам ключей с последующей " зачисткой " сортировкой вставками?

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

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

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

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

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

Страницы:

(рис 10.1) Поразрядная сортировка

Биты, байты и слова

  const int bitsword = 32;
  const int bitsbyte = 8;
  const int bytesword = bitsword/bitsbyte;
  const int R = 1 << bitsbyte;

В C++ можно прямо написать операцию извлечения B-го байта из двоичного слова A следующим образом:

  inline int digit(long A, int B)
    { return (A >> bitsbyte*(bytesword-B-1)  (R-1); }

для обнуления всех разрядов, кроме требуемого байта, который занимает 8 правых разрядов.

  inline int digit(char* A, int B)
    { return A[B]; }

При использовании структуры-оболочки, наподобие рассмотренной в разделе 6.8 , можно записать:

  inline int digit(Item A, int B)
    { return A.str[B]; }

Упражнения

10.6. Выполните упражнение 10.5 для R = 2, используя случайные 32-разрядные числа.

10.7. Выполните упражнение 10.5 для нормально распределенных чисел (распределение Гаусса).

Бинарная быстрая сортировка

Программа 10.1. Бинарная быстрая сортировка

  template <class Item>
  void quicksortB(Item a[], int l, int r, int d)
    { int i = l, j = r;
      if (r <= l || d > bitsword) return;
      while (j != i)
        { while (digit(a[i], d) == 0  (i < j)) i++;
          while (digit(a[j], d) == 1  (j > i)) j--;
          exch(a[i], a[j]);
        }
      if (digit(a[r], d) == 0) j++;
      quicksortB(a, l, j-1, d+1);
      quicksortB(a, j, r, d+1);
    }
  template <class Item>
  void sort(Item a[], int l, int r)
    { quicksortB(a, l, r, 0); }

(рис 10.2) Пример бинарной быстрой сортировки

(рис 10.3) Пример бинарной быстрой сортировки (с битовым представлением ключей)

(рис 10.4) Дерево разбиения для бинарной быстрой сортировки

(рис 10.5) Динамические характеристики бинарной быстрой сортировки на большом файле

Упражнения

Поразрядная MSD-сортировка

(рис 10.6) Динамические характеристики поразрядной MSD-сортировки

(рис 10.7) Пример поразрядной MSD-сортировки

Программа 10.2. Поразрядная MSD-сортировка

  #define bin(A) l+count[A]
  template <class Item>
  void radixMSD(Item a[], int l, int r, int d)
    { int i, j, count[R+1];
      static Item aux[maxN];
      if (d > bytesword) return;
      if (r-l <= M) { insertion(a, l, r); return; }
      for (j = 0; j < R; j++) count[j] = 0;
      for (i = l; i <= r; i++)
        count[digit(a[i], d) + 1]+ + ;
      for (j = 1; j < R; j++)
        count[j] += count[j-1];
      for (i = l; i <= r; i++)
        aux[l+count[digit(a[i], d)]++] = a[i];
      for (i = l; i <= r; i++) a[i] = aux[i];
      radixMSD(a, l, bin(0)-1, d+1);
      for (j = 0; j < R-1; j++)
        radixMSD(a, bin(j), bin(j + 1)-1, d+1);
    }

(рис 10.9) Рекурсивная структура поразрядной MSD-сортировки

(рис 10.10) Рекурсивная структура поразрядной MSD-сортировки (с игнорированием пустых подфайлов)

Упражнения

10.15. Сколько узлов содержит полное trie-дерево, соответствующее рис 10.10?

10.16. Покажите, как выполняется разбиение MSD-сортировкой набора ключей now is the time for all good people to come the aid of their party.

Трехпутевая поразрядная быстрая сортировка

Программа 10.3. Трехпутевая поразрядная быстрая сортировка

  #define ch(A) digit(A, d)
  template <class Item>
  void quicksortX(Item a[], int l, int r, int d)
    { int i, j, k, p, q; int v;
      if (r-l <= M) { insertion(a, l, r); return; }
      v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
      while ( i < j )
        { while (ch(a[ + + i]) < v) ;
          while (v < ch(a[-- j ] ) ) if (j == l) break;
          if (i > j) break;
          exch(a[i], a[j]);
          if (ch(a[i]) == v) { p++; exch(a[p], a[i]); }
          if (v == ch(a[j])) { q—; exch(a[j], a[q]); }
        }
      if (p == q)
       { if (v != '\0') quicksortX(a, l, r, d+1); return; }
      if (ch(a[i]) < v) i++;
      for (k = l; k <= p; k+ + , j--) exch(a[k], a[j]);
      for (k = r; k >= q; k--, i++) exch(a[k], a[i]);
      quicksortX(a, l, j, d);
      if ((i == r)  (ch(a[i]) == v)) i+ + ;
      if (v != '\0') quicksortX(a, j + 1, i-1, d+1);
      quicksortX(a, i, r, d);
    }

(рис 10.11) Трехпутевая поразрядная быстрая сортировка

(рис 10.12) Рекурсивная структура трехпутевой поразрядной быстрой сортировки

(рис 10.13) Пример узлов trie-дерева трехпутевой поразрядной быстрой сортировки

Упражнения

10.27. Разработайте реализацию трехпутевой поразрядной быстрой сортировки для связных списков.

Поразрядная LSD-сортировка

(рис 10.14) Пример поразрядной LSD-сортировки

Метод LSD-сортировки упорядочивает трехбуквенные слова за три прохода (слева направо).

Программа 10.4. Поразрядная LSD-сортировка

  template <class Item>
  void radixLSD(Item a[], int l, int r)
    { static Item aux[maxN];
      for (int d = bytesword-1; d >= 0; d—)
        { int i, j, count[R+1];
          for (j = 0; j < R; j + +) count[j] = 0;
          for (i = l; i <= r; i++)
            count[digit(a[i], d) + 1]++;
          for (j = 1; j < R; j++)
            count[j] += count[j-1];
          for (i = l; i <= r; i++)
            aux[count[digit(a[i], d)]++] = a[i];
          for (i = l; i <= r; i++) a[i] = aux[i];
        }
    }

(рис 10.15) Пример (бинарной) LSD-сортировки (показаны разряды ключей)

(рис 10.16) Динамические характеристики поразрядной LSD-сортировки

Упражнения

10.36. Разработайте реализацию LSD-сортировки для связных списков.

Характеристики производительности поразрядных сортировок

(рис 10.17) Динамические характеристики поразрядной LSD-сортировки для различных видов файлов

Лемма 10.1. В худшем случае поразрядная сортировка выполняет проверку всех байтов во всех ключах.

Упражнения

Сортировки с сублинейным временем выполнения

(рис 10.18) Динамические характеристики LSD-сортировки по MSD-разрядам

Эмпирическое сравнение поразрядных сортировок (целочисленные ключи)
N	Q	4-разрядные байты		8-разрядные байты			16-разрядные байты
N	Q	M	L	M	L	L*	M	L	M*
12500	2	7	11	28	4	2	52	5	8
25000	5	14	21	29	8	4	54	8	15
50000	10	49	43	35	18	9	58	15	39
100000	21	77	92	47	39	18	67	30	77
200000	49	133	185	72	81	39	296	56	98
400000	102	278	377	581	169	88	119398	110	297
800000	223	919	732	6064	328	203	1532492	219	2309

Обозначения:
Q	Быстрая сортировка, стандартная (программа 7.1)
M	MSD-сортировка, стандартная (программа 10.2)
L	LSD-сортировка (программа 10.4)
M*	MSD-сортировка, с адаптацией основания системы счисления под размер файла
L*	LSD-сортировка по MSD-разрядам.

Эмпирическое сравнение поразрядных сортировок (строковые ключи)
N	Q	T	M	F	R	X	X*
12500	7	6	9	9	8	6	5
25000	14	12	18	19	15	11	10
50000	34	26	39	49	34	25	24
100000	83	61	87	114	71	57	54

Обозначения:
Q	Быстрая сортировка, стандартная (программа 7.1)
T	Быстрая сортировка с трехпутевым разбиением (программа 7.5)
M	Сортировка слиянием (программа 8.2)
F	Пирамидальная сортировка с усовершенствованием Флойда (см. раздел 9.4 )
R	MSD-сортировка (программа 10.2)
X	Трехпутевая поразрядная быстрая сортировка (программа 10.3)
X*	Трехпутевая поразрядная быстрая сортировка (с отсечениями)

Упражнения

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

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

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Поразрядная сортировка

Биты, байты и слова

Бинарная быстрая сортировка

Поразрядная MSD-сортировка

Трехпутевая поразрядная быстрая сортировка

Поразрядная LSD-сортировка

Характеристики производительности поразрядных сортировок

Сортировки с сублинейным временем выполнения

Биты, байты и слова

Бинарная быстрая сортировка

Поразрядная MSD-сортировка

Трехпутевая поразрядная быстрая сортировка

Поразрядная LSD-сортировка

Характеристики производительности поразрядных сортировок

Сортировки с сублинейным временем выполнения

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!