Целочисленные сортировки

dmitriy@izvolov.ru
dmitriy@izvolov.ru

Как показывает практика, правильно написанные целочисленные сортировки быстры не только теоретически, но и вполне практически. Разница в скорости сортировки может достигать нескольких порядков. Жаль, что такие полезные алгоритмы до сих пор не стандартизированы.

 

Предлагается следующий интерфейс поразрядной сортировки:

template <RandomAccessIterator I, RandomAccessIterator J, UnaryFunction Map>
void radix_sort (I first, I last, J buffer, Map to_integer);

[first, last) — сортируемый диапазон.

buffer — дополнительная память, требуемая для поразрядной сортировки. Её должно быть не менее чем distance(first, last).

to_integer — отображение элементов сортируемого диапазона в целые числа. В соответствии с ним и будет происходить сортировка.

Результат — отсортированный диапазон [first, last).

 

Относительно недавно появился boost::integer_sort, но этот алгоритм не нравится по следующим причинам:

1. Он медленнее.

2. Он менее гибок, т.к. не позволяет передать буфер снаружи, то есть самостоятельно производит аллокации.

3. Он гибридный. Иначе говоря, сводится к std::sort на маленьких массивах. В результате в интерфейсе алгоритма есть две функции — shift и compare, которые могут быть рассогласованы, что потенциально может приводить к разным результатам сортировки в зависимости от размера сортируемого массива.

 

Все подробности, замеры, графики, идеи и обоснования тут: https://habrahabr.ru/post/271677/

8
рейтинг
6 комментариев
yndx-antoshkka
Идея огонь!

Пара хотелок:
* constexpr void radix_sort
* так же предложить в proposal добавить параллельные версии
* burst не указывает лицензию для использования. Нужно либо добавить пермессивную лицензию, либо сделать отдельный репозиторий только с radix_sort, либо pull-request в Boost с radix_sort

Попробуйте написать proposal, следуя инструкции. По любым вопросам - обращайтесь, помогу.
yndx-antoshkka
dmitriy@izvolov.ru
yndx-antoshkka, спасибо.
Над параллельной версией уже работаю.

А по вопросам как обращаться? Писать на cpp-proposal@yandex-team.ru?
Или в этой теме?
dmitriy@izvolov.ru
yndx-antoshkka
Можно на личную почту, можно на cpp-proposal@yandex-team.ru, можно тут. Как удобнее.
yndx-antoshkka
zamazan4ik@tut.by
Я очень сильно рекомендую заглянуть вот в этот репозиторий на гитхабе: github.com/Morwenn/cpp-sort

Здесь вы найдёте очень много сортировок под самые разные случаи жизни.

На самом деле в Boost.Sort реализована одна суепр-сортировка, которая состоит из 3 (или 4, не помню уже). Вы просто вызываете boost::spreadsort, а она в зависиомсти от того, что пришло на вход, вызывает либо integer_sort, либо float_sort, либо string_sort. Касательно boost::integer_sort - там реализована сортировка spreadsort, автором коей является сам мейнтейнер Boost.Sort. Она не прям чтобы слишком быстрая, но в среднем случае работает очень неплохо.

Основная проблема здесь в том, сколько сортировок стоит добавлять в Стандарт. Я вот например хочу pdqsort вместо introsort. А ещё я хочу count_sort, потому что на моих кейсах это будет быстрее. А ещё где count_sort не подходит я хотел бы radix_sort, который тоже хорош. Если я знаю, что мои данные почти отсортированы, я хочу TimSort, который очень быстрый на таких вот кейсах. Так где стоит остановиться?
zamazan4ik@tut.by
dmitriy@izvolov.ru
zamazan4ik@tut.by,
0. За ссылку спасибо. Но целочисленные сортировки оттуда не обладают всеми качествами, которые я здесь предлагаю.
1. Я сравниваюсь конкретно с boost::integer_sort, о чём я писал и здесь, и в публикации на Хабре. Она почти всегда медленнее моей. Графики в публикации по ссылке.
2. Целочисленные сортировки — это совершенно иной класс алгоритмов по сравнению с сравнивающими сортировками. Я считаю, что стандарту только выиграет от того, что появится сортировка, требующая дополнительной памяти, но работающая гораздо быстрее, чем std::sort и не требующая порядка на сортируемых элементах.
dmitriy@izvolov.ru
zamazan4ik@tut.by
dmitriy@izvolov.ru, проблема в том, что надо найти границу, когда нам стоит остановиться. Я бы предпочёл иметь просто набор стандартных сортировок, которыми можно пользоваться. Но на такое Комитет скорее всего не пойдёт примерно по тем же причинам, почему автор Boost.Sort не хочет принимать новые сортировки: "Нет смысла принимать все подряд сортировки, потому что только в некоторых случаях они дают выигрыш". Я не согласен с такой точкой зрения, но что ж поделать. Стандарт описывает только интерфейсы, а вся подкапотная реализация ложится на плечи STL-писателей.

По поводу целочисленной сортировки - есть ещё ska_sort, она тоже довольно быстрая.
zamazan4ik@tut.by
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).