Начало. Библиотека сортировки обеспечивает общую реализацию высокоскоростных алгоритмов сортировки, которые превосходят таковые в стандарте C++ как в среднем, так и в худшем случае, когда в списке есть более 1000 элементов для сортировки.

Они возвращаются кSTL std::sortна небольших наборах данных.

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

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

Эти алгоритмы кодируются общим способом и принимают функторы, что позволяет им сортировать любой объект, который может быть обработан, как эти основные типы данных. В случае<string_sort>, это включает в себя все с определенным строгим слабым упорядочением, чтоstd::sortможет сортировать, но написание эффективных функторов для некоторых сложных ключевых типов может не стоить дополнительных усилий по сравнению с просто использованиемstd::sort, в зависимости от того, насколько важна скорость для вашего приложения. Использование образцов доступно в каталоге примеров.

В отличие от многих алгоритмов, основанных на радиксе, основной алгоритм<spreadsort>разработан вокругнаихудшей производительности. Он работает лучше на кусочных данных (где он не широко распространен), так что на реальных данных он может работать значительно лучше, чем на случайных данных. Концептуально<spreadsort>может сортировать любые данные, для которых может быть определен абсолютный порядок, и<string_sort>достаточно гибок, чтобы это было возможно.

<spreadsort>——— [] — [] — [[]:

<spreadsort>——— [] — [] — [[]:

Эти функции определены в<namespace boost::sort::spreadsort>.

	Tip
	В подъёме. Сортировать C++ В справочном разделе нажмите на соответствующую перегрузку, например<float_sort(RandomAccessIter,RandomAccessIter,Right_shift,Compare);>, чтобы получить полную информацию об этой перегрузке.

Каждый из<integer_sort>,<float_sort>и<string_sort>имеет 3 основных варианта: Базовая версия, которая берет первый итератор и последний итератор, какstd::sort:

integer_sort(array.begin(), array.end());
float_sort(array.begin(), array.end());
string_sort(array.begin(), array.end());

Версия с перегруженным фанктором сдвига, обеспечивающая гибкость в случае, если<operator>>>уже делает что-то другое, кроме сдвига. Функтор правого смещения принимает два arg, сначала тип данных, а затем естественное количество битов для сдвига вправо.

Для<string_sort>этот вариант немного отличается; ему нужен скобчатый функтор, эквивалентный<operator>[], принимающий число, соответствующее смещение символа, вместе со вторым<getlength>функтором, чтобы получить длину строки в символах. Во всех случаях этот оператор должен вернуть целочисленный тип, который сравнивается с<operator<>, чтобы обеспечить предполагаемый порядок (интеграторы могут быть сведены на нет, чтобы изменить их порядок).

Другими словами (кроме отрицательных поплавков, которые инвертируются как инты):

rightshift(A, n) < rightshift(B, n) -> A < B
A < B -> rightshift(A, 0) < rightshift(B, 0)

integer_sort(array.begin(), array.end(), rightshift());

string_sort(array.begin(), array.end(), bracket(), getsize());

См.rightshiftsample.cppдля рабочего примера целочисленной сортировки с помощью функтора правого смещения.

И версия с фанктором сравнения для максимальной гибкости. Этот функтор должен обеспечивать тот же порядок сортировки, что и целые числа, возвращаемые правым смещением (кроме отрицательных поплавков):

rightshift(A, n) < rightshift(B, n) -> compare(A, B)
compare(A, B) -> rightshift(A, 0) < rightshift(B, 0)

integer_sort(array.begin(), array.end(), negrightshift(), std::greater<DATA_TYPE>());

Примерами функторов являются:

struct lessthan {
  inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    return x.a < y.a;
  }
};

struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    return x.a[offset];
  }
};

struct getsize {
  inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); }
};

И эти функторы используются таким образом:

string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan());

См.stringfunctorsample.cppдля рабочего примера сортировки струн со всеми функторами.

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

Алгоритм Spreadsort динамически выбирает либо сортировку на основе сравнения, либо сортировку на основе радикса при повторении, в зависимости от того, что обеспечивает лучшую производительность в худшем случае. Таким образом, худшая производительность гарантированно будет лучше.𝑶(N⋅log2(N))сравнения и𝑶(N⋅log2(K/S+S))операции, где

Это приводит к значительному улучшению производительности для большихN;<integer_sort>, как правило, на 50% в 2 раза быстрее, чемstd::sort, в то время как<float_sort>и _string_sort примерно в 2 раза быстрее, чемstd::sort.

В их описании представлены графики исполнения<integer_sort>,<float_sort>и<string_sort>.

Сравнения производительности и графики были сделаны на ноутбуке Core 2 Duo под управлением Windows Vista 64 с MSVC 8.0 и старом ноутбуке G4 под управлением Mac OSX с gcc.Для управления компиляцией использовался Boost bjam/b2.

Прямые сравнения производительности на более новой системе x86 под управлением Ubuntu с запасом доstd::sortпри меньших размерах ввода отключены ниже.

	Note
	Откат кstd::sortдля меньших размеров ввода предотвращает худшую производительность, наблюдаемую на левой стороне первых двух графиков.

<integer_sort>начинает становиться быстрее, чемstd::sortпримерно на 1000 целых чисел (4000 байт), а<string_sort>становится быстрее, чемstd::sortна несколько меньшем количестве байтов (всего 30 строк).

	Note
	4-поточный граф имеет 4 потока, выполняющиеотдельные сортировки одновременно(не расщепляющие один сорт) в качестве теста на столкновение кэша потока и другие многопоточные проблемы производительности.

<float_sort>раз очень похожи на<integer_sort>раз.

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

Важность кэш-дружественного гистограммирования описана вArne Maus, Adaptive Left Reflex, хотя и без худшей обработки, описанной ниже.

Время, затрачиваемое на итерацию радикса, составляет:

& #119926; (N)итерации по данным

& #119926; [N]сравнение целых типов (даже для _float_sort и<string_sort>)

& #119926; (N)свопы

& #119926; (2^S)операции бин.

Для получения& #119926; [N]худшей производительности в итерации применяется ограничениеS<= log2(N), а& #119926; [2^Sстановится& #119926; (N). Для каждой такой итерации количество несортированных битов log2 (диапазон) (называемоеK) на элемент уменьшается наS. ПосколькуSуменьшается в зависимости от количества сортируемых элементов, оно может упасть с максимумаSдо минимумаS_мин.