Как я написал алгоритм сортировки, который быстрее std::sort. Часть 3

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

Прим. Wunder Fund: ну, вы наверное, и сами догадываетесь, как мы любим быстрые алгоритмы и оптимизации. Если вы тоже такое любите — вы знаете, что делать)

Проблемы

Ska Sort — это не идеальный алгоритм, проблемы есть и у него. Я действительно считаю, что он будет быстрее std::sort при сортировке практически любых данных, и что ему почти всегда стоит отдавать предпочтение перед std::sort.

Самая большая проблема моего алгоритма заключается в сложности его кода. Особенно ярко это проявляется в использовании хитросплетений шаблонов при сортировке последовательных байтов. Например, сейчас, когда мы сортируем std::pair<int, int>, система создаст восемь экземпляров механизма сортировки, так как тут будет восемь разных функций для извлечения байта из этих данных. Я могу придумать способы уменьшения этого числа, но все эти способы будут связаны с дополнительной нагрузкой на систему во время выполнения кода. Этот вопрос нуждается в дополнительных исследованиях, но сложность кода, кроме прочего, усложняет и выполнение изменений такого рода. Пока же, если используются сложные ключи сортировки, можно столкнуться с увеличением времени компиляции. Легче всего можно это обойти, попытавшись использовать более простые ключи сортировки.

Ещё одна проблема заключается в том, что я точно не знаю, что мне делать с данными, которые я не могу отсортировать. Например, мой алгоритм не может отсортировать вектор значений std::set. Причина заключается в том, что у std::set нет оператора, позволяющего обращаться к элементам в произвольном порядке. А мне нужен такой оператор при обработке одного элемента за раз. Я могу написать код, который позволит сортировать значения std::set с использованием std::advance в итераторах, но такой подход может оказаться медленным. Ещё я могу просто переходить на std::sort. Прямо сейчас я не обрабатываю такие данные ни тем, ни другим способом, просто выдавая ошибку компиляции. Причина этого заключается в том, что я предоставляю пользователям моего кода возможность настройки его работы — функцию to_radix_sort_key(), которая позволяет им написать собственный код, превращающий их структуры в данные, поддающиеся сортировке. Если бы я выполнял автоматический переход на другой механизм сортировки в том случае, когда мой алгоритм не способен что-то отсортировать, то использование подобных возможностей настройки принесло бы пользователям больше неприятностей.

Сейчас, когда надо предоставить моему коду подобную функцию, а пользователь этого не сделал, выдаётся ошибка. Когда она предоставлена — ошибка исчезает. Если бы я просто переходил на std::sort, получая данные, которые не могу отсортировать, единственным последствием этого, которое было бы видно пользователю, было бы некоторое замедление сортировки. Тогда понадобилось бы либо профилировать код, сравнивая его с производительностью std::sort, либо пришлось бы пошагово выполнять функцию сортировки, чтобы удостовериться в том, что она действительно использует пользовательскую реализацию to_radix_sort_key(). Поэтому сейчас я решил выдавать сообщение об ошибке в тех случаях, когда не могу отсортировать данные некоего типа. После этого пользователь может принять решение о том, реализовывать ли ему to_radix_sort_key(), или использовать std::sort.

Ещё одна проблема заключается в том, что сейчас, при сортировке данных некоего типа, можно применять лишь одну схему поведения алгоритма сортировки. Пользователь должен дать моему коду ключ сортировки, и если этот ключ будет целым числом — данные будут отсортированы в порядке возрастания. Если нужно, чтобы сортировка велась в порядке убывания — сейчас мой код не даёт простого в использовании интерфейса для того, чтобы это сделать. В случае с целыми числами решить эту проблему можно, обратив знак в функции, выдающей ключ, поэтому эту ситуацию можно назвать не слишком тяжёлой. Но при сортировке строк задача усложняется. А именно, если мой код получает строку, то сортировка будет осуществляться по строке, с учётом регистра, в возрастающем порядке. Сейчас в моём коде нет механизма сортировки строк без учёта регистра символов. (Вот ещё пример: скажем, надо сортировать строки с учётом встречающихся в них численных значений, так, чтобы строка bar100 шла бы после строки bar99. Сейчас мой код этого не умеет). Полагаю, что это — проблема вполне решаемая, я просто ещё её не решил. Так как интерфейс моего алгоритма работает не так, как интерфейсы существующих алгоритмов, мне нужно изобрести новые способы его настройки.

Исходный код и использование Ska Sort

Я загрузил код реализации моего алгоритма, под лицензией Boost, на GitHub.

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

std::sort(enemies.begin(), enemies.end(), [](const Enemy & lhs, const Enemy & rhs)
{
    return std::make_tuple(!is_in_combat(lhs), distance_to_player(lhs))
         < std::make_tuple(!is_in_combat(rhs), distance_to_player(rhs));
});

При применении ska_sort вместо этого надо будет поступить так:

ska_sort(enemies.begin(), enemies.end(), [](const Enemey & enemy)
{
    return std::make_tuple(!is_in_combat(enemy), distance_to_player(enemy));
});

Как видите, при переходе от обычного алгоритма к моему, выполняется довольно-таки простая и понятная трансформация кода. Или, предположим, что имеется список неких людей, который надо отсортировать сначала по фамилии, а потом — по имени. Сделать это можно так:

ska_sort(contacts.begin(), contacts.end(), [](const Contact & c)
{
    return std::tie(c.last_name, c.first_name);
});

Тут есть один важный момент, который заключается в использовании std::tie. Делается так из-за того, что, предположительно, last_name и first_name — это строки, и при этом не нужно создавать их копии. С помощью std::tie можно воспользоваться ссылками на них.

И, конечно, если имеется обычный вектор с данными простых типов, можно отсортировать эти данные без лишних движений:

ska_sort(durations.begin(), durations.end());

Тут я исхожу из предположения о том, что durations — это вектор, содержащий значения типа double, который может понадобиться отсортировать для нахождения медианы, 90 перцентиля, 99 перцентиля и так далее. Так как ska_sort умеет сортировать значения типа double, пользователю не нужно предоставлять ему собственный код.

Есть ещё одна ситуация, последняя, о которой я расскажу. Она возникает при сортировке коллекций, содержащих данные пользовательских типов. Ska Sort принимает лишь одну функцию, позволяющую настраивать сортировку. Но что делать, если имеется пользовательский тип, в котором используются вложенные структуры? В подобном случае моему алгоритму придётся рекурсивно работать с типом верхнего уровня, а потом сталкиваться с типом, который ему непонятен. Когда это происходит — выдаётся сообщение об ошибке, в котором говорится об отсутствии функции, перегружающей to_radix_sort_key(). В такой ситуации пользователю нужно предоставить моему коду реализацию функции to_radix_sort_key(), которую можно найти для пользовательского типа с использованием ADL:

struct CustomInt
{
    int i;
};
int to_radix_sort_key(const CustomInt & i)
{
    return i.i;
}
 
//... где-нибудь потом
 
std::vector<std::vector<CustomInt>> collections = ...;
ska_sort(collections.begin(), collections.end());

В данном случае ska_sort будет обращаться к to_radix_sort_key() при работе с вложенными CustomInt. Поступать нужно именно так из-за того, что не существует эффективного способа предоставления коду собственной реализации функции extract_key на верхнем уровне. (На верхнем уровне пришлось бы конвертировать std::vector<CustomInt> в std::vector<int>, а это требует выполнения копирования).

И наконец, у меня ещё есть функция, выполняющая поразрядную сортировку с копированием, ska_sort_copy, которая будет гораздо быстрее основного алгоритма для маленьких ключей. Для её использования нужно предоставить системе второй буфер того же размера, что и входной буфер. Затем значение, которое возвратит функция, сообщит о том, находится ли итоговая отсортированная последовательность во втором буфере (тогда функция возвратит true), или в первом (тогда она возвратит false).

std::vector<int> temp_buffer(to_sort.size());
if (ska_sort_copy(to_sort.begin(), to_sort.end(), temp_buffer.begin()))
    to_sort.swap(temp_buffer);

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

Вопросы и ответы

Я кое с кем об этом говорил. Обычно мне задавали вопросы, указывающие на то, что люди не верят в то, что мой алгоритм и правда быстрее std::sort.

? Вопрос

Разве временная сложность алгоритма поразрядной сортировки не O(n+m), где m — большое значение, что, на самом деле, хуже, чем O(n log n)? (Ещё один вариант этого вопроса указывает на временную сложность алгоритма поразрядной сортировки O(nm), где m — больше, чем log n.)

> Ответ

Да, на временную сложность алгоритма поразрядной сортировки влияют большие постоянные значения, но в моих тестах производительности ska_sort начинает обходить std::sort на 128 элементах. А если имеется большая коллекция, скажем, состоящая из тысячи элементов, преимущество алгоритма поразрядной сортировки при её обработке совершенно очевидно.

? Вопрос

Не скатывается ли временная сложность алгоритма поразрядной сортировки до O(n log n)? (Или так: «Не демонстрирует ли алгоритм поразрядной сортировки, в худшем случае, временную сложность O(n log n), или, может, даже O(n^2)?».)

> Ответ

Реализация алгоритма поразрядной сортировки, в определённом смысле, вынуждена производить log(n) проходов по данным. При сортировке значений типа int16 надо сделать два прохода по данным. При сортировке значений типа int32 надо уже четыре прохода. А в случае со значениями типа int64 требуется уже восемь проходов. Этот список можно продолжить. Но это не даёт временную сложность алгоритма, равную O(n log n), так как это — постоянный фактор, который не зависит от количества элементов. При сортировке тысячи значений типа int32 нужно выполнить четыре прохода по данным. При сортировке миллиона таких значений надо, как и прежде, сделать те же четыре прохода. Объём работы, таким образом, растёт линейно. И если все сортируемые целые числа отличаются друг от друга первым байтом — мне даже не придётся выполнять второй, третий и четвёртый проходы. Мне нужно сделать лишь столько проходов, сколько требуется для того чтобы все их различить.

В результате худший случай для поразрядной сортировки имеет временную сложность O(nb), где b — количество байтов, которые нужно обработать до тех пор, пока можно будет различить сортируемые значения. Если мне придётся сортировать множество длинных строк — тогда количество байтов может быть довольно большим, в результате поразрядная сортировка может замедлиться. Это — тот самый «худший случай», который мы рассматривали. Если у вас есть данные, на которых поразрядная сортировка работает медленнее, чем std::sort — пожалуйста дайте мне об этом знать (я, кстати, таких данных найти не смог, а видел я их разве что тогда, когда сам создавал наборы «плохих» данных). Мне было бы интересно узнать о том, можно ли как-то оптимизировать мой алгоритм в расчёте на такие данные. Я, когда пытался создавать наборы строк, близкие к тем, которые могут встретиться в реальности, всегда выяснял, что ska_sort явно быстрее std::sort.

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

? Вопрос

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

> Ответ

Графики верны. Не знаю что и сказать. Код выложен на GitHub, поэтому вы можете попробовать его сами. И — да, я ожидаю, что всё вокруг будут сортировать с использованием алгоритма поразрядной сортировки. Я, честно говоря, не знаю о том, почему вышло так, что когда-то все ухватились за алгоритм быстрой сортировки.

Дальнейшая работа

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

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

2. Когда я переключаюсь на std::sort, я начинаю сортировку с самого начала. Как я уже говорил, переход на std::sort осуществляется тогда, когда мне нужно разбить последовательность на разделы, размеры которых меньше 128 элементов. Но, предположим, что содержимое одного из таких разделов — это исключительно строки, которые начинаются с warning, а содержимое другого — строки, начинающиеся с error. В таком случае, если я перейду на std::sort, я мог бы пропустить общий префикс сортируемых строк. У меня есть сведения о количестве байтов, по которым данные уже отсортированы. Подозреваю, что тот факт, что std::sort приходится начинать сортировку с самого начала, является причиной параллельности линий графиков для ska_sort и std::sort при сортировке строк. Эта оптимизация позволит значительно ускорить сортировку в ситуациях, когда мой алгоритм, какое-то время поработав, вынужден переключаться на std::sort.

3. Ещё я, возможно, напишу функцию, которая способна принимать либо функцию сравнения, либо функцию extract_key. Вот как она может работать. Если ей передают объект функции, которая принимает два аргумента — система будет выполнять сортировку, основанную на сравнениях элементов. А если ей передают объект функции, принимающей один аргумент — будет использоваться поразрядная сортировка. Причина такого подхода к созданию подобной функции заключается в том, что так она может быть обратно совместимой с std::sort.

Итоги

В итоге могу сказать, что у меня имеется алгоритм сортировки, который, для большинства наборов входных данных, быстрее std::sort. Код реализации этого алгоритма находится на GitHub. Он выложен под лицензией Boost, поэтому, если хотите — можете его попробовать.

Моя работа над этим алгоритмом, в основном, сводится к двум вещам:

1. Я оптимизировал внутренний цикл поразрядной сортировки на месте, что привело к созданию алгоритма ska_byte_sort.

2. Я создал алгоритм, ska_sort, который способен выполнять поразрядную сортировку данных произвольного типа или произвольной комбинации типов.

Для того чтобы сортировать с помощью этого алгоритма данные пользовательских типов, нужно передать ska_sort функцию, которая предоставляет ему «ключ сортировки». Это должно быть целое число, число с плавающей точкой, логическое значение, вектор, строка, кортеж или пара значений, в состав которых входят значения вышеперечисленных простых типов. Список поддерживаемых алгоритмом типов достаточно велик. Это — любые примитивные типы, всё, к элементам чего можно обращаться в произвольном порядке. То есть — с помощью ska_sort можно сортировать std::array, std::deque и другие наборы значений.

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

Главные уроки, которые я из всего этого вынес, заключаются в следующем. Во-первых, даже к «решённым» задачам, вроде сортировки, стоит время от времени возвращаться. Во-вторых — всегда полезно как следует изучить базовые вещи. Я не ожидал, что узнаю что-то особенное, освоив курс «Введение в алгоритмы», но я уже создал этот алгоритм, и я испытываю искушение ещё раз попытаться написать хеш-таблицу, которая быстрее существующих.

Если вы используете мой алгоритм в своём коде — расскажите мне о том, как он себя показал на ваших задачах. Спасибо!

О, а приходите к нам работать? ?

Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

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

Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.

Присоединяйтесь к нашей команде.