Экспериментальная сортировка тернарным деревом
Когда-то меня заинтересовал такой вопрос: почему все самые лучшие сортировки, основанные на сравнениях, имеют асимптотику O (N log N). И почему тут логарифм двоичный? Можно ли создать сортировку, у которой асимптотика будет лучше в самом худшем случае? Я решил провести довольно любопытный эксперимент.
В википедии написано, что двоичность логарифма связана с тем, что результатом операции сравнения двух элементов может быть один из двух вариантов. И если в ходе работы алгоритма совершается 
сравнений, то всего возможно 
вариантов комбинаций ответов на них. Количество перестановок из n элементов равно n! Для того, чтобы можно было сюръективно отобразить множество комбинаций ответов на множество всех перестановок, количество сравнений должно быть не меньше, чем 
, поскольку сравнение — единственная разрешённая операция. Так дословно гласит электронная энциклопедия.
Однако ведь результат сравнения принимает 3 варианта: больше, меньше или равно. Тогда должно быть возможно 
вариантов комбинаций ответов на них при k сравнений. Может быть логарифм двоичный потому, что мы всегда сравниваем только два элемента за раз (попарно)? Тоже не так! Как показали мои эксперименты, это условие необходимое, но не достаточное. Нам нужно еще отказаться от бинарного дерева в сторону тернарного!
А что если сравнивать сразу три элемента за раз? Ну представим: у нас теоретически есть некая команда процессора, которая позволяет сравнивать сразу три элемента и возвращать нам некий код, по которому мы можем понять, как эти элементы взаимно упорядочены:
cmp3 eax, ebx, ecx, edx ; выполняет сравнение трех чисел
; ebx, ecx, edx с записью результата в eaxДля простоты, положим, что мы всегда хотим сортировать в порядке возрастания (Ascending order). Что это бы дало? Да и как, скажите на милость, тогда выполнять сортировку?
Такой команды у нас пока нет. Но давайте создадим ее эмуляцию на базе классического сравнения. Приспособим к ней какой-нибудь подходящий алгоритм сортировки со сложностью 
. И проверим:, а действительно ли количество операций сравнения станет подчиняться зависимости 
? На самом деле, некорректно писать здесь показатель логарифма. Но, надеюсь, придирчивый читатель простит меня за эту намеренную оплошность.
Честно говоря, по началу, я сломал себе мозг, думая над тем, как же с такой операцией выполнить сортировку. Перебирая подходящие кандидаты среди существующих алгоритмов наткнулся на серию первоклассных статей от @valemak (всем, интересующимся разнообразными сортировками, рекомендую почитать). Конкретно я обратил внимание на восходящую сортировку кучей. Рекомендую вначале ознакомиться с данной статьей, чтобы освежить в памяти алгоритм. К тому же там сделаны хорошие анимации.
Однако
Как оказалось позже, гораздо удобнее было бы, если процессор поддерживал, например такие команды:
max4 eax, ebx, ecx, esi, edi ; выполняет сравнение 4х чисел, на которые
; указывают регистры ebx, ecx, esi, edi
; и записывает в eax адрес максимального
max3 eax, ebx, esi, edi ; выполняет сравнение 3х чисел, на которые
; указывают регистры ebx, ecx, esi, edi
; и записывает в eax адрес максимальногоВот как восходящая сортировка работает вкратце. Массив представляется в виде дерева. При этом никакой дополнительной памяти нам не требуется. Индекс потомков узла и его родителя можно всегда вычислить по нехитрым формулам. А корень — первый элемент массива. Дерево у нас «виртуальное» и к тому же сбалансированное «из коробки». Я же объявил дерево не двоичным, а троичным: чтобы каждый родитель имел по три потомка.
Далее строится сортирующее дерево придерживаясь простого правила: родитель всегда больше своих потомков. При завершении построения, в корне у нас всегда будет самый большой элемент. Его мы помещаем в конец массива операцией обмена с последним элементом массива. После чего последний элемент оказывается в корне. И мы должны выполнить «просейку», чтобы сохранить инвариант кучи. И да, после каждой перестановки очередного корня, размер дерева уменьшается на единицу. А в конце реального массива начинают собираться максимальные элементы. Так мы поступаем до тех пор, пока в куче не останется один элемент. Все.
Сама «просейка» в моем алгоритме осуществляется следующим образом: мы сравниваем родителя со своими прямыми потомками одновременно. Т.е. на этом шаге мы сравниваем «как бы одной командой» сразу четыре! элемента. Выбираем максимальный, ставим на место родителя, и спускаемся к потомкам максимального элемента (если потомки есть). Если родитель больше всех своих потомков, ничего не делаем — завершаем просейку.
Да собственно, что я говорю! Лучше один раз увидеть наглядно:
Надеюсь, у вас отображается эта анимация. Вы можете запускать и нажимать на паузу, когда вам удобно.
А вот реализация алгоритма на Java:
public class TernaryAccentSort
{
private static final int ROOT = 0;
private int LAST;
public void sort(TernaryArray array)
{
LAST = array.size()-1;
heapify(array);
while (LAST - ROOT + 1 > 4)
{
array.swap(ROOT, LAST--);
sift(array, 0);
}
// завершающий этап, последние 4 элемента
array.swap(0, 3);
array.compareAndOrder(0, 1, 2);
}
/**
* Строим сортируемое дерево
*
* @param array сортируемый массив
*/
private void heapify(TernaryArray array)
{
int node = fixTail(array);
while ( node != ROOT )
{
int rt = node; // node всегда указывает на чей-то правый потомок
int md = node-1;
int lf = node-2;
int pr = getParent(node); // родитель этой тройки
// получим индекс максиального элемента из четверки
int mx = array.max(lf, md, rt, pr);
if ( mx != pr ) // если это не родитель
{
array.swap(pr, mx);
sift(array, mx);
}
// к следующей тройке элементов
node -= 3;
}
}
/**
* Выполняет корректировку концевика дерева. Обычно это 1 или 2 листа некоего родителя,
* замыкающего массив. Ставит на место родителя максимальный из листов.
*
* @param array массив
* @return номер узла, с котого можно продолжать heapify
*/
private int fixTail(TernaryArray array)
{
int node = LAST;
// обрабатываем край дерева
if ( isLeftChild(node) ) // у последнего родителя нет среднего и правого потомка
{
int pr = getParent(node);
int lf = node;
if ( array.compare(pr, lf) < 0 )
array.swap(pr, lf); // родитель должен быть всегда больше потомков
node--;
}
else if ( isMiddleChild(node) ) // у последнего родителя нет только правого потомка
{
int pr = getParent(node);
int lf = node-1;
int md = node;
// ставим на место родителя максимальный элемент из тройки: родитель, левый потомок и средний потомок
array.compareAndOrder(lf, md, pr);
node -= 2;
}
// на выходе node всегда будет показывать на правого потомка предпоследнего родителя
return node;
}
/**
* Выполняет просейку сортирующего поддерева дерева для сохранения инварианта:
* родитель всегда больше своих потомков. Вызывается в случае нарушения родителем node
* этого условия
*
* @param array сортируемое дерево
* @param node элемент, нарушающий инвариант
*/
private void sift(TernaryArray array, int node)
{
// сравниваем корень и два его потомка; помещаем корень куда следует
int lf, rt, md, mx, pr = node;
while ( hasLeftChild(pr) )
{
lf = getLeftChild(pr);
md = getMiddleChild(pr);
rt = getRightChild(pr);
// определим, кто из этих элементов максимальный?
if ( hasRightChild(pr) )
mx = array.max(lf, md, rt, pr);
else if ( hasMiddleChild(pr) )
mx = array.max(lf, md, pr);
else
mx = array.max(lf, pr);
if ( mx != pr ) // если это не родитель
{
array.swap(pr, mx);
pr = mx;
}
else
break;
}
}
private int getLeftChild(int node)
{
return node*3 + 1;
}
private int getMiddleChild(int node)
{
return node*3 + 2;
}
private int getRightChild(int node)
{
return node*3 + 3;
}
private int getParent(int child)
{
return (child-1) / 3;
}
private boolean isLeftChild(int node)
{
return (node % 3) == 1;
}
private boolean isMiddleChild(int node)
{
return (node % 3) == 2;
}
// private boolean isRightChild(int node)
// {
// return (node % 3) == 0;
// }
private boolean hasLeftChild(int node)
{
return getLeftChild(node) <= LAST;
}
private boolean hasMiddleChild(int node)
{
return getMiddleChild(node) <= LAST;
}
private boolean hasRightChild(int node)
{
return getRightChild(node) <= LAST;
}
}Правда просто? Я встроил счетчик сравнений в класс массива и поэтому (без плясок с бубном измерения времени) могу точно оценить, сколько сравнений и перестановок реально осуществляется. А от этого зависит и время работы.
Полный код проекта с замерами и сравнениями.
Далее я сравнил работу своего алгоритма с исходным алгоритмом восходящей сортировки. Вот графическое представление результатов измерений:
Как видно на графиках, мы действительно приближаем сложность сортировки к троичному логарифму (см. параметр: «Новых сравнений»). Что было ожидаемо. Просто мне хотелось убедиться в этом на практике. Обратите внимание, что оба алгоритма выполняют обменов и сравнений чуть меньше, чем ожидается от таких алгоритмов. Ибо это самый скоростной алгоритм из всех, для полностью разбалансированных массивов. И кстати говоря, такая реализация алгоритма совершает меньше обменов, чем исходный алгоритм. Хотя операция сравнения сильно дороже (ну если мы не сравниваем опять какие-то натуральные числа).
Если бы была аппаратно реализована нужная команда у процессора, то троичное дерево здорово бы выигрывало у двоичного на больших массивах. Хотя. Если вы инженер из, скажем, Oracle и делаете свои процессоры (раньше для них делал Sun Microsystems) заточенные на работу с СУБД, то реализация пары новых команд для вас имело бы смысл. Также, возможно, троичное дерево пригодится разработчикам специализированных FGPA / ASIC плат, если среди планируемых задач сортировка стоит не на последнем месте.
Как вы думаете, стоит ли в классических процессорах общего пользования создавать подобные команды и какой интерфейс у них должен быть?
Понятно, что глубоко на аппаратном уровне составная команда сравнения все равно будет состоять из бинарных попарных сравнений. И реальное число выполняемых сравнений такой трюк не уменьшит, а то и увеличит (мои эксперименты показали это; хотя все зависит от конкретного алгоритма). Но тут может «выстрелить» «параллельность» таких попарных сравнений. Мы за один условный такт процессора сможем выполнять операцию, на которую при классическом исполнении потратили бы больше.
В следующей статье я предложу читателям вариант гибридного алгоритма сортировки, который подойдет к уменьшению O (N log N) с несколько иной стороны. Нет, я не изобрел новый алгоритм. Я просто предложу оптимальную комбинацию из имеющихся, а также укажу на забавный феномен, который я в шутку называю «дефект масс».
взаимно упорядочены:
