РИСУНОК 10.9. РЕКУРСИВНАЯ СТРУКТУРА ПОРАЗРЯДНОЙ СОРТИРОВКИ MSD

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

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

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

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

РИСУНОК 10.10. РЕКУРСИВНАЯ СТРУКТУРА ПОРАЗРЯДНОЙ СОРТИРОВКИ MSD (ПУСТЫЕ ФАЙЛЫ ИГНОРИРУЮТСЯ)

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

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

Упражнения

> 10.14. Начертить компактную древовидную структуру (пустые корзины отсутствуют, ключи узлов такие же, как и на рис. 10.10), соответствующую рис. 10.9.

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

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

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

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

10.19. Написать программу, генерирующую произвольные 80-байтные ключи, после чего сортирует их методом поразрядной сортировки MSD для Л = 10, 10**, 10 и 10. Снабдите профамму инструментальными средствами для распечатки общего количества байтов, проверенных в процессе каждой сортировки.

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

10 программой FinePnn

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

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

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

10.23. Написать программу генератора ключей, которая порождает случайные 30-байтные ключи, состоящие из трех полей: поле размером в четыре байта, содержащее одну из 10 заданных строк, поле размером 10 байтов, содержащее одну из 50 заданных строк, однобайтное поле с одним из двух возможных значений, и поле размером 15 байтов, содержащее выровненную слева строку случайных символов, которая с равной вероятностью может содержать от четырех до 15 символов. Используйте полученный генератор ключей для генерации Л случайных ключей, затем выполните их упорядочение методом поразрядной сортировки MSD для N= 10 Ю *, 10 и 10. Снабдите программу инструментальными средствами для распечатки общего количества байтов, проверенных в процессе сортировки. Сравните достигнутую производительность с аналогичным результатом для произвольного случая (см. упражнение 10.19).

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

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

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

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