两者都应该在O(n log n)中运行,但一般排序比stable_sort快.实践中的性能差距有多大？你对此有一些经验吗？
我想排序大量大约20字节的结构.结果的稳定性在我的情况下会很好,但它不是必须的.目前底层容器是一个普通数组,也许稍后可以将其更改为std :: deque.
mar*_*cog 18
std::stable_sort当有足够的内存时,执行NlogN比较.当内存不足时,它会降级为N((logN)^ 2)比较.因此,std::sort当存储器可用时,它与(在平均情况和最差情况下执行O(NlogN)比较)的效率大致相同.
对于那些感兴趣的人,sort()使用一个introsort(当递归达到一定深度时切换到heapsort的quicksort)和stable_sort()使用合并排序.
Alp*_*per 16
有理由比较算法的好答案.我基准std::sort,并std::stable_sort与谷歌/基准为了好奇.
提前指出是有用的;
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>用512ksize(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(),因为它维护了相等元素的顺序.
传统的建议是,如果维护顺序不重要,则应使用std :: sort()代替.
但是,它依赖于上下文.即使您不需要维护订单,也有大量数据可以通过稳定排序进行最佳排序:
如果数据的枢轴点一直很差,Quicksort很快会变成最糟糕的表现.
在Burrows-Wheeler变换是用作数据压缩,例如的一部分的算法的bzip2.它需要对文本的所有旋转进行排序.对于大多数文本数据,合并排序(通常由std :: stable_sort()使用)比快速排序(通常由std :: sort()使用)快得多.
bbb是一个BWT实现,它注意到std :: stable_sort()优于此应用程序的sort()的优点.