Оба должны работать в O (n log n), но в целом сортировка выполняется быстрее, чем stable_sort. Насколько велика разница в производительности на практике? Есть ли у вас некоторый опыт?
Я хочу отсортировать очень большое количество структур, размер которых составляет около 20 байт. Стабильность результата была бы приятной в моем случае, но это не обязательно. На данный момент базовый контейнер представляет собой простой массив, возможно, впоследствии он может быть заменен на std:: deque.
Есть хорошие ответы, которые теоретически сравнивают алгоритмы. Я оценил std::sort и std::stable_sort с google/benchmark ради любопытства.
Полезно указать заранее, что:
1 X 2500 MHz CPU и 1 GB RAMArch Linux 2015.08 x86-64g++ 5.3.0 и clang++ 3.7.0 (-std=c++11, -O3 и -pthread)
Тест BM_Base* пытается измерить время заполнения std::vector<>. Это время должно быть вычтено из результатов сортировки для лучшего сравнения.Первый критерий сортирует std::vector<int> с размером 512k.
[ g++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:37:43
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseInt/512k_mean 24730499 24726189 28
BM_BaseInt/512k_stddev 293107 310668 0
...
BM_SortInt/512k_mean 70967679 70799990 10
BM_SortInt/512k_stddev 1300811 1301295 0
...
BM_StableSortInt/512k_mean 73487904 73481467 9
BM_StableSortInt/512k_stddev 979966 925172 0
[ clang++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:39:07
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseInt/512k_mean 26198558 26197526 27
BM_BaseInt/512k_stddev 320971 348314 0
...
BM_SortInt/512k_mean 70648019 70666660 10
BM_SortInt/512k_stddev 2030727 2033062 0
...
BM_StableSortInt/512k_mean 82004375 81999989 9
BM_StableSortInt/512k_stddev 197309 181453 0
Второй критерий сортирует std::vector<S> с размером 512k (sizeof(Struct S) = 20).
[ g++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:49:32
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseStruct/512k_mean 26485063 26410254 26
BM_BaseStruct/512k_stddev 270355 128200 0
...
BM_SortStruct/512k_mean 81844178 81833325 8
BM_SortStruct/512k_stddev 240868 204088 0
...
BM_StableSortStruct/512k_mean 106945879 106857114 7
BM_StableSortStruct/512k_stddev 10446119 10341548 0
[ clang++ ]# benchmark_sorts --benchmark_repetitions=10
Run on (1 X 2500 MHz CPU )
2016-01-08 01:53:01
Benchmark Time(ns) CPU(ns) Iterations
----------------------------------------------------------------
...
BM_BaseStruct/512k_mean 27327329 27280000 25
BM_BaseStruct/512k_stddev 488318 333059 0
...
BM_SortStruct/512k_mean 78611207 78407400 9
BM_SortStruct/512k_stddev 690207 372230 0
...
BM_StableSortStruct/512k_mean 109477231 109333325 8
BM_StableSortStruct/512k_stddev 11697084 11506626 0
Любой, кто любит запускать тест, вот код,
#include <vector>
#include <random>
#include <algorithm>
#include "benchmark/benchmark_api.h"
#define SIZE 1024 << 9
static void BM_BaseInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
}
}
BENCHMARK(BM_BaseInt)->Arg(SIZE);
static void BM_SortInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
std::sort(v.begin(), v.end());
}
}
BENCHMARK(BM_SortInt)->Arg(SIZE);
static void BM_StableSortInt(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<int> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back(dist(mt));
}
std::stable_sort(v.begin(), v.end());
}
}
BENCHMARK(BM_StableSortInt)->Arg(SIZE);
struct S {
int key;
int arr[4];
};
static void BM_BaseStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
}
}
BENCHMARK(BM_BaseStruct)->Arg(SIZE);
static void BM_SortStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
std::sort(v.begin(), v.end(),
[](const S &a, const S &b) { return a.key < b.key; });
}
}
BENCHMARK(BM_SortStruct)->Arg(SIZE);
static void BM_StableSortStruct(benchmark::State &state) {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist;
while (state.KeepRunning()) {
std::vector<S> v;
v.reserve(state.range_x());
for (int i = 0; i < state.range_x(); i++) {
v.push_back({dist(mt)});
}
std::stable_sort(v.begin(), v.end(),
[](const S &a, const S &b) { return a.key < b.key; });
}
}
BENCHMARK(BM_StableSortStruct)->Arg(SIZE);
BENCHMARK_MAIN();
std::stable_sort выполняет сравнение NlogN, когда доступно достаточное количество памяти. Когда доступная память недоступна, она ухудшается до N ((logN) ^ 2) сравнений. Поэтому он примерно такой же эффективности, как std::sort (который выполняет сравнения O (NlogN) как в среднем, так и в худшем случае), когда доступна память.
Для тех, кого интересует, sort() использует introsort (quicksort, который переключается на heapsort, когда рекурсия достигает определенной глубины) и stable_sort() использует сортировку слияния .
Иногда требуется std:: stable_sort(), потому что он поддерживает порядок элементов, которые равны.
И обычный совет заключается в том, что если поддержание порядка не важно, вы должны использовать std:: sort().
Однако его контекст зависит. Существует множество данных, которые лучше всего сортировать со стабильной сортировкой, даже если вам не нужно поддерживать порядок:
Quicksort быстро становится наихудшим, если данные имеют неустойчивые опорные точки.
Barrows-Wheeler Transform - это алгоритм, используемый как часть сжатия данных, например. bzip2. Это требует сортировки всех поворотов текста. Для большинства текстовых данных сортировка слияния (как часто используется std:: stable_sort()) значительно быстрее, чем quicksort (как обычно используется std:: sort()).
bbb - это реализация BWT, которая отмечает преимущества std:: stable_sort() для sort() для этого приложения.
Достаточно большой, чтобы гарантировать отдельную функцию, которая имеет стабильный вид и не имеет std::sort() сделать это прозрачно.
Насколько велика разница в производительности в практика? У вас есть опыт об этом?
Да, но это не так, как вы ожидали.
Я взял реализацию C преобразования Barrows-Wheeler и С++ - ified it. Выключилось намного медленнее, чем код C (хотя код был более чистым). Поэтому я поставил там временную аппаратуру, и оказалось, что qsort работает быстрее, чем std:: sort. Это было в VC6. Затем он перекомпилировался с помощью stable_sort, и тесты выполнялись быстрее, чем версия C. Другим оптимизациям удалось вывести версию С++ на 25% быстрее, чем версия C. Я думаю, что можно было ускорить скорость, но ясность кода исчезла.
Если вы сортируете большое количество структур, скорость ввода-вывода вашей памяти/диска начинает становиться более важной, чем асимптотическое время работы. Кроме того, следует учитывать и использование памяти.
Я попробовал std:: stable_sort на 2Gb данных (64B structs), не зная, что std:: stable_sort создает внутреннюю копию данных. Сбой обмена, который последовал за мной, почти заблокировал мой компьютер.
Использование неустойчивого std:: sort уменьшает использование памяти в 2 раза, что полезно при сортировке больших массивов. Я закончил std:: stable_sort, поэтому я не могу определить, насколько он был медленнее. Однако, если стабильная сортировка не требуется, то я думаю, что лучше использовать неустойчивый std:: sort.
Ищет нечто подобное - но был удивлен, что никто не говорил об Вспомогательном пространстве.
Как я считаю - реализация как stable_sort, так и sort должна гарантировать O (NlogN) для всех (лучших, средних и худших) случаев.
Однако разница существует в используемом вспомогательном пространстве. stable_sort требуется дополнительное пространство O (N).
Может быть, разница в производительности заключается в приобретении этого пространства.:)
В противном случае, теоретически - они должны быть одинаковыми с производительностью w.r.t.
sort должен делать то, что вам нужно, если вам это нужно → stable_sort сохраняет относительный порядок элементов с эквивалентными значениями.