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

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

10.42. Эмпирически сравнить число байтов, проверяемых в процессе трехпутевой поразрядной быстрой сортировки длинных строк для 7V = 10, 10 и 10, при этом число выполняемых операций сравнений должно быть таким же, как и в случае стандартной быстрой сортировки для тех же файлов.

о 10.43. Найти количество байтов, просматриваемых в процессе выполнения поразрядной сортировки MSD и трехпутевой поразрядной быстрой сортировки для файла с 7V ключами А, АА, AAA, АААА, ААААА, ...

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

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

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

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

Этот метод представляет собой тривиальную модификацию программы 10.4. Чтобы выполнить сортировку слава направо, воспользовавшись для этой цели старшей половиной ключей, мы просто запускаем внешний цикл со значения byteword/2-l, а не с byteword-1. Затем мы применяем метод сортировки простыми вставками к почти упорядоченному файлу, который к этому моменту получаем. Рисунки 10.3 и 10.18 представляют собой убедительное доказательство того, что файл, отсортированный по старшим разрядам, достаточно хорошо упорядочен. Сортировка методом вставки выполняет всего лишь шесть операций обмена для сортировки файла, изображенного в четвертом столбце диаграммы на рис. 10.3, а на рис. 10.18 показано, что достаточно большие файлы, отсортированные только по старшей половине разрядов, могут быть эффективно упорядочены простыми вставками.

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

Г :.V...V;:;

.

У.

. .1. - 1

РИСУНОК 10.18. ДИНАМИЧЕСКИЕ ХАРАКТЕРИСТИКИ ПОРАЗРЯДНОЙ СОРТИРОВКИ LSD НА РАЗРЯДАХ. ИСПОЛЬЗУЕМЫХ ПОРАЗРЯДНОЙ СОРТИРОВКОЙ MSD Когда ключами служат биты, принимающие случайные значения, сортировка файла по старшим разрядам ключей устанавливает на файле порядок, близкий к искомому. На этой диаграмме сортировка LSD с шестью проходами (слева) на файле со случайными 6-разрядными ключами сравнивается с трехпроходной поразрядной сортировкой, после которой может последовать еще один проход, на этот раз сортировки простыми вставками (справа). Последняя стратегия приводит к увеличению быстродействия примерно в два раза.

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

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

Алгоритмы общего назначения, такие как быстрая сортировка, нашли на практике более широкое применение, чем поразрядная сортировка, поскольку они могут адаптироваться к более широкому диапазону приложений. Основная причина подобного положения дел заключается в том, что абстракция ключа, на которой построена поразрядная сортировка обладает меньшей универсальностью, чем та, которая использовалась в главах 6-9. Например, один из широко распространенных способов установления интерфейса со служебной программой сортировки заключается в том, чтобы клиент сам выбирал функцию сравнения. Таким интерфейсом является интерфейс, используемый программой qsort из библиотеки программ на С++. Это программное средство не только годится в ситуации, когда клиент может воспользоваться специальными сведениями о сложных ключах с целью реализации быстрого сравнения, но также позволяет выполнять сортировку, используя отношения порядка, которые вообще могут обходиться без ключей. Мы рассмотрим один такой алгоритм в главе 2L

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