Быстрая сортировка с составными ключами.


     Привожу описание этой сортировки из статьи: 'Быстрые алгоритмы сортировки и поиска строк' Jon L. Bentley. Перевод с английского М.С.Галкиной.



Введение



Раздел 2 посвящен алгоритму быстрой сортировки Хоара [9] и бинарным деревьям поиска. Мы подчеркиваем хорошо известный изоморфизм, связывающий эти два подхода, и подытоживаем основные известные факты.



Алгоритмы и структуры данных для составных ключей представлены в разделе 3. Алгоритм быстрой сортировки (Multikey Quicksort) упорядочивает множество из n векторов по k компонент каждый. Как и обычный алгоритм быстрой сортировки, он делит данные на множества с ключами, большими или равными заданному значению; как и поразрядная сортировка, он переходит к следующему полю ключа, когда выясняется, что данное поле ключа текущего элемента равно этому значению. Для краткости часто упоминание о ключе опускается и говорится просто о больших, меньших и равных элементах сортируемого множества. Изоморфной структурой является троичное дерево поиска, каждый узел которого представляет разбиение подмножества векторов расщепляющим значением и тремя указателями: один к элементам, меньшим расщепляющего значения, другой – к большим (как в бинарном дереве поиска), а третий – к равным, у них потом сравниваются последующие поля ключа (как в борах). Как правило, применяемые структуры и методы стараются изложить на высоком теоретическом уровне, далеком от практических приложений. Приведенная здесь простая схема делает очевидной реализацию алгоритма.



Алгоритмы анализируются в разделе 4. Большая часть результатов оказывается новым изложением известных фактов.



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



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



В разделе 6 мы обращаемся к более трудным задачам символьного поиска. Запросы поиска частичных совпадений допускают произвольные, «не имеющие значения», символы (например, образцу «so.a», соответствуют слова soda и sofa). Основной результат в этом разделе – это реализация алгоритма поиска частичных совпадений Ривеста (Rivest) в троичном дереве и эксперименты по исследованию его эффективности. Запросы «ближайших соседей» выдают все слова, расстояние Хемминга которых от запрашиваемого слова не превосходит заданного (например, мы может искать все слова, расстояние которых от слова soda не превосходит 2). Мы даем новый алгоритм поиска ближайших соседей в строках, представляем простые реализации на Си, и описываем результаты экспериментов по исследованию их эффективности.



Выводы и итоги – раздел 7.

История



Алгоритм быстрой сортировки QuickSort – это классический алгоритм декомпозиции. Чтобы отсортировать массив, выбирается расщепляющий элемент и производится разбиение: элементы переставляются так, чтобы меньшие элементы оказались по одну сторону, а большие по другую, а затем полученные два подмассива рекурсивно сортируются. Что происходит с элементами, равными расщепляющему значению? В методе Хоара меньшие элементы отправляются влево, а большие вправо, равные элементы могут оказаться в любой из двух сторон.



Разработчики алгоритмов давно осознали преимущества и трудности троичного разбиения. Седжвик [22] на странице 244 замечает: «В идеале, мы хотели бы разместить все равные ключи в файле так, чтобы все ключи с меньшим значением оказались слева, а с большим – справа. К сожалению, до сих пор не изобретен эффективный способ сделать это...» Дейкстра излагает эту проблему, как «Задачу о Датском национальном флаге»: требуется упорядочить последовательность красных, белых и голубых камешков так, чтобы они следовали в порядке цветов на знамени Голландии. Это соответствует разбиению в алгоритме быстрой сортировки, когда меньшие элементы окрашиваются в красный цвет, равные в белый, а большие в голубой. Троичному алгоритму Дейкстры требуется линейное время (каждый элемент рассматривается ровно один раз), однако в оценке времени работы реализующего его кода появляется гораздо больший множитель, чем для кода, реализующего быструю сортировку Хоара.



Вегнер [27] описывает более эффективные троичные схемы разбиения. Бентли и Макклоу [2] предложили троичное разбиение, основанное на следующем инварианте цикла:





Основной цикл разбиений содержит два внутренних цикла. Первый внутренний цикл увеличивает индекс b: он пропускает меньшие элементы, перемещает равные элементы к a, и останавливается, когда встречает больший элемент. Второй цикл, соответственно, уменьшает индекс c: он пропускает большие элементы, перемещает равные к d, и останавливается, когда встречает меньший элемент. Основной цикл затем меняет местами элементы, на которые указывают b и c, увеличивает b и уменьшает c; он останавливается, когда b и c совпадают. (Вегнер предложил тот же инвариант, однако, его коды сложнее). Работа завершается тем, что равные элементы перемещаются из концов в середину массива, при этом уже не нужны сравнения. Для разбиения n-элементного массива этому алгоритму требуется n-1 сравнение.



Алгоритм внутренней сортировки анализировали разные авторы, в том числе Хоар [9], ван Эмдер [26], Кнут [11] и Седжвик [23]. В формулировке точных результатов используются гармонические числа .



Теорема 1 [Хоар]. Алгоритм быстрой сортировки с расщепляющими элементами, выбираемыми случайно, сортирует n объектов, среди которых нет равных, в среднем за 2nHn + O(n) » 1.386n lg n сравнений.



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



Теорема 2 [Ван Эмден]. Быстрая сортировка с расщеплением вокруг медианы 2t+1 случайно выбранных элементов, сортирует n разных объектов в среднем за 2nHn/(H2t + 2 - Ht + 1) + O(n) сравнений.



Увеличивая t, мы можем приблизить среднее число сравнений к n ln n + O(n).



Приведенные выше теоремы имели дело только с средними характеристиками. Чтобы гарантировать разумное время в худших случаях, мы проводим расщепление вокруг истинной медианы, которую можно вычислить за cn сравнений. (В работе Шенхаге, Патерсона и Пиппендера [20] рассмотрен алгоритм для худшего случая, в котором c = 3; Флойд и Риверст [8] рассматривают алгоритм для среднего времени, у которого c = 3/2.)





Рис. 1. Быстрая сортировка и бинарное поисковое дерево



Теорема 3. Быстрая сортировка, расщепляющая вокруг медианы, поиск которой требует cn сравнений, сортирует n элементов за cn ln n + O(n) сравнений.



Доказательство основано на том, что в рекурсивном дереве около ln n уровней, и на каждом делается не более cn сравнений.



Алгоритм быстрой сортировки тесно связан со структурой бинарных деревьев поиска (о структурах данных смотрите у Кнута [11]). На рисунке 1 показано, как они оба обрабатывают последовательность «31 41 59 26 53». Дерево справа – это стандартное бинарное дерево поиска, сформированное вставкой элементов в порядке ввода. Рекурсивное дерево слева показывает «идеальное разбиение» быстрой сортировки: она проводит разбиение вокруг первого элемента подмассива и оставляет элементы в обоих подмассивах в том же относительном порядке. На первом уровне алгоритм проводит расщепление вокруг значения 31, и выдает левый подмассив «26» и правый подмассив «41 59 53», затем оба рекурсивно сортируются.



Рисунок 1 иллюстрирует фундаментальный факт – изоморфизм между быстрой сортировкой и бинарными деревьями поиска. Необведенные расщепляющие значения слева в точности соответствуют внутренним узлам справа, как в горизонтальном, так и в вертикальном направлениях. Длина внутреннего пути дерева поиска равна общему числу сравнений, сделанных обеими структурами. Совпадают не только количества, обе структуры производят один и тот же набор сравнений. Ожидаемая стоимость успешного поиска, по определению, равна длине внутреннего пути, деленной на n. Объединив это наблюдение с теоремой 1, получаем:



Теорема 4 [Хиббард]. Среднее количество сравнений, необходимых для успешного поиска в бинарном дереве поиска, построенном вставкой элементов в случайном порядке, равно 2Hn + O(1) » 1.386 lg n.



Аналогичную переформулировку допускает теорема 2: мы можем сократить цену поиска, выбрав в качестве корня поддерева медиану 2t + 1 элементов в поддереве. По аналогии с теоремой 3 сбалансированное дерево сокращает время поиска примерно до lg n.

Алгоритмы



Подобно тому, как быстрая сортировка изоморфна бинарным деревьям поиска, поразрядная сортировка изоморфна цифровым деревьям поиска (см. Кнут [11]). Этот изоморфизм описан в таблице:


Алгоритм

Структура данных


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

Бинарные деревья поиска


Быстрая сортировка с составными ключами

Троичные деревья поиска


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

Боры


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



Мы выразим задачи в терминах набора n векторов, размерности k каждый. Базисная операция – троичное сравнение двух компонент векторов. Мунро и Раман [18] описывают алгоритм для сортировки наборов векторов на месте и дают ссылки на предыдущие работы в этой области.



В разделе «Составные ключи из слов» Хоар [9] следующим образом описывает модификацию внутренней сортировки, предложенную Шеклтоном: «Когда известно, что сегмент охватывает те, и только те объекты, у которых значения первых n полей ключа совпадают с первыми n полями заданного значения, то при разбиении этого сегмента сравниваются (n+1)-е слова ключей». Хоар дает неуклюжую реализацию этой элегантной идеи; Кнут [11] представляет подробности схемы Шеклтона в решении 5.2.2.30.



Троичный алгоритм разбиения доставляет элегантную реализацию быстрой сортировки Хоара для составных ключей. Нижеследующий рекурсивный псевдокод сортирует последовательность s длины n, когда известно, что ее компоненты 1..d-1 равны друг другу; самый первый вызов – это, конечно sort(s, n, 1).

 
sort(s, n, d)

if n Ј 1 or d > k return;

выбрать расщепляющее значение v;

разбить s по значению v компоненты с номером d,

получив последовательности s<,s=,s> длины которых n<, n=, n>;

sort(s<, n<, d);

sort(s=, n=, d + 1);

sort(s>, n>, d);


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



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





Рис. 2. Троичное дерево поиска для 12 двухбуквенных слов.



В разделе 6.22 Кнут [11] строит оптимальное бинарное дерево поиска для представления множества из 31 наиболее распространенных английских слов; 12 из них содержат по 2 буквы. На рисунке 2 показано сбалансированное дерево поиска, получающееся в результате рассмотрения этих слов как набора из n = 12 векторов по k = 2 компонент каждый. Указатели к меньшим и большим значениям изображены сплошными линиями, а указатели к равным – пунктирными. Под каждым конечным узлом помещено соответствующее входное слово. Это дерево было построено расщеплением вокруг истинной медианы каждого подмножества.



При поиске слова «is» мы начинаем с корня, спускаемся по поддереву равных к узлу «s», и останавливаемся там после двух сравнений. При поиске «ax» мы делаем три сравнения с первой буквой («a») и два сравнения со второй буквой («x»), затем сообщаем, что такого слова в этом дереве нет.



Эта идея относится по крайней мере к 1964; см., например, Клампет [5]. Предыдущие авторы предлагали представлять поддеревья узла бора в виде массива или связанного списка; Клампет представляет множество поддеревьев бинарным деревом поиска; его структуру уже можно считать троичным деревом поиска. Мелхорн [17] предложил взвешенное сбалансированное троичное дерево поиска, в котором поиск, вставка и удаление элементов в множестве из n строк длины k каждая требует времени O(log n + k); похожая структура описана в разделе III.6.3 работы Мелхорна [16].



Бентли и Сакс [4] рассматривают сбалансированное троичное дерево поиска. Значением каждого узла является медиана множества элементов в подходящем измерении; дерево на рис. 1 было построено таким способом. Бентли и Сакс представляют эту структуру как решение задачи вычислительной геометрии; они выводят его многомерной декомпозицией. Троичные деревья поиска можно построить многими способами, например, вставлять элементы в порядке ввода или строить сбалансированное дерево, считая совокупность элементов полностью заданной. Вайшнави [25] и Слитор с Тарьяном [24] предлагают схемы балансировки троичных деревьев поиска.



 



 

Анализ



Мы начнем с троичных деревьев поиска, а затем применим полученные результаты к быстрой сортировке по составным ключам. Сначала рассмотрим теорему, принадлежащую Бентли и Саксу [4].



Теорема 5 [Бентли и Сакс]. Поиск среди k-мерных векторов, представленных в виде сбалансированного троичного дерева поиска, требует не больше лlg nы + k скалярных сравнений, где n – количество векторов; и это оптимально.



Набросок доказательства. Чтобы получить верхнюю границу, мы начинаем с n активных векторов и k активных измерений; каждое сравнение делит пополам активный вектор или сокращает число активных измерений. Чтобы получить нижнюю границу, рассмотрим множество векторов, в котором все элементы равны в первых k-1 измерениях, и различаются в k-м измерении.



Похожие времена поиска для суффиксных деревьев получили Манбер и Майерс [14].



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



Теорема 6. Если быстрая сортировка производит разбиение вокруг медианы, вычисленной за cn сравнений, то для сортировки n k-мерных векторов ей потребуется не более cn(ln n + k) скалярных сравнений.



Доказательство. Так как рекурсивное дерево сбалансировано, то по теореме 5 ни один узел не отстоит от корня дальше, чем на л lg nы + k. Каждый уровень дерева содержит не больше n элементов, поэтому, вследствие линейности медианного алгоритма на каждом уровне проводится не больше cn скалярных сравнений. Умножение дает требуемый результат.



По аналогии с теоремой 1 получаем, что алгоритм быстрой сортировки с составными ключами, проводящий разбиение вокруг случайно выбранного элемента, требует не больше n(2Hn + k + O(1)) сравнений,. Мы можем еще сократить это число, проводя разбиения вокруг медианы выборки.



Теорема 7. Алгоритм быстрой сортировки с составными ключами, проводящий разбиение вокруг медианы 2t + 1 случайно выбранных элементов сортирует n k-мерных векторов в среднем не больше, чем за 2nHn/(H2t + 2 - Ht + 1) + O(kn) скалярных сравнений.



Набросок доказательства. Комбинируем теорему 2 с наблюдением, что равные элементы строго сокращают число сравнений. Аддитивная цена O(kn) объясняется проверкой всех k ключей.



Увеличив объем выборки t, можно сократить время примерно до nln(n)+O(kn). (Мунро и Раман [18] описали сортировку векторов на месте с таким временем обработки.)



Перейдем теперь от сортировки к аналогичным результатам относительно построения троичных деревьев поиска. Мы можем построить дерево с нуля за примерно то же время: добавление «бухгалтерских» функций (но не дополнительных примитивных операций) слегка увеличивает расходы на построение дерева. При отсортированном входе дерево может быть построено за O(kn) сравнений.



Теорема 6 описывает цену поиска в сбалансированном дереве для худшего случая. Среднее число сравнений, требуемых для успешного поиска в случайным образом построенном дереве, равно 2Hn + k + O(1); разбиение вокруг выборочной медианы уменьшает это число.



Теорема 8. Среднее число сравнений в успешном поиске в троичном дереве поиска, полученном разбиением вокруг медианы 2t + 1 случайно выбранных элементов, равно 2Hn / (H2t + 2 - Ht + 1) + k + O(1).



Набросок доказательства. Используйте теорему 7 и изоморфизм между деревьями и алгоритмами сортировки.

Программы для строк



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



Мы предполагаем, что читатель знаком с языком программирования Си; его "библией" является книжка Кернигана и Ричи [10]. В Си символы представляются кодами – целыми числами, которые легко сравнивать. Строки представляются векторами из символов. Структуры и теоремы, приведенные ранее, применяются непосредственно к множествам строк фиксированной длины. Стандарт Си, однако, предусматривает и строки с нефиксированной длиной: конец такой строки обозначается специальным null-символом, код которого – целое число нуль.



Построим функцию на Си для быстрой сортировки строк (см. приложение А). Главная сортирующая функция имеет следующий прототип:

 
void ssort1main(char *x[], int n);


В нее передается массив x из n указателей на символьные строки; она должна переставить указатели таким образом, чтобы строки были расположены в лексикографическом порядке. Мы введем вторую функцию, параметрами которой будут оба этих аргумента плюс дополнительный аргумент целого типа h, отвечающий за "глубину" сравнений – номера сравниваемых символов. Алгоритм останавливается, когда входной вектор содержит не более одной строки, либо когда текущая глубина выйдет за границы имеющихся строк.



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

#define swap(a, b) { char *t=x[a]; \

x[a]=x[b]; x[b]=t; }

#define i2c(i) x[i][dept h]


Макрос swap переставляет два указателя в массиве, а макрос i2c («целое в символ») возвращает символ "глубины" h строки x[i]. Функции vecswap перемещает последовательности одинаковых элементов из их временных положений в концах массива на нужные места в середине.

 
void vecswap(int i, int j, int n, char *x[])

{

   do {

      swap(i, j);

      i++;

      j++;

   } while(--n);

}


Полный алгоритм сортировки вы найдете в программе 1; он близок к коду, представленному Бентли и Макилроем [2]. Вызывающая функция алгоритма:

 
void ssort1main(char *x[], int n)

{ ssort 1(x, n, 0); }


После разбиения мы рекурсивно сортируем сегменты больших и меньших, а сегмент равных сортируем, если соответствующий символ не равен нулю.



Мы можем увеличить эффективность программы 1 стандартными методами, они описаны, например, у Седжвика [21]. Алгоритмические ускорения включают сортировку вставкой маленьких подмассивов и разбиение вокруг медиан трех элементов (а в больших массивах – медианы трех медиан трех элементов), используя теорему 7. В стандартные приемы языка Си входит замена индексов массива указателями. Вот таблица, где содержится число секунд, требуемых для сортировки файла words из 72275 слов и 696436 символов (файл можно найти на сайте авторов статьи http://www.cs.princeton.edu/~rs/strings - прим. перев.).

.



Машина

MHz

Системная

Простая

Улучшенная

Поразрядная (Radix)


MIPC R4400

150

.85

.79

.44

.40


MIPC R4000

100

1.32

1.30

.68

.62


Pentium

90

1.74

.98

.69

.50


486DX

33

8.20

4.15

2.41

1.74


 



В третьем столбце содержится время работы системной функции qsort, а в четвертом – время программы 1. Наш простой код во всех случаях не медленнее, а иногда и заметно быстрее, чем системные функции (предназначенные для общих целей, однако предположительно сильно оптимизированные). Пятый столбец рапортует о времени работы нашей улучшенной сортировки, которая всегда существенно быстрее простой версии. В качестве контрольной в последнем столбце приводятся времена для сильно оптимизированной сортировки, коды которой можно найти у Макилроя, Бостика и Макилроя [15]; это самая быстрая из известных нам сортировок строк.

 
void ssort1(char *x[], int n, int depth)

{

   int a, b, c, d, r, v;

   if (n <= 1)

      return;

   a = rand() % n;

   swap(0, a);

   v = i2c(0);

   a = b = 1;

   c = d = n-1;

   for (;;) {

      while (b <= c && (r = i2c(b)-v) <= 0) {

         if (r == 0) { swap(a, b); a++; }

         b++;

      }

      while (b <= c && (r = i2c(c)-v) >= 0) {

         if (r == 0) { swap(c, d); d--; }

         c--;

      }

      if (b > c) break;

      swap(b, c);

      b++;

      c--;

   }

   r = min(a, b-a); vecswap(0, b-r, r, x);

   r = min(d-c, n-d-1); vecswap(b, n-r, r, x);

   r = b-a; ssort1(x, r, depth);

   if (i2c(r) != 0)

      ssort1(x + r, a + n-d-1, depth+1);

   r = d-c; ssort1(x + n-r, r, depth);

}


Программа 1. Сортировка строк



Мы также запустили четыре сортировки на двух наборах данных библиотечных номеров, используемых в DIMACS Implementation Challenge (файл dictcalls также можно найти на сайте http://www.cs.princeton.edu/~rs/strings - прим. перев.). Мы извлекли из каждого файла множество уникальных ключей (около 86,000 в каждом файле), каждый из который является номером карточки (например, «LAC___59.7_K_24_1976»), ключи в среднем имеют длину 22.5 символов. На машинах MIPS, наша оптимизированная сортировка оказалась на 20 процентов бы