sort和std::stable_sort在实践中的性能差距有多大？

Question

两者的运行速度都应该是O( n )，但一般情况下排序比stable_sort快。在实践中，性能差距有多大？你有这方面的经验吗？

我想要对大小约为20字节的大量结构进行排序。在我的情况下，结果的稳定性会很好，但这不是必须的。目前，底层容器是一个普通数组，也许以后可以将其更改为std::deque。

Answer 1

与理论上的算法相比，有一些很好的答案。出于好奇心，我用google/benchmark对std::sort和std::stable_sort进行了基准测试。

提前指出是有用的；

• Benchmark计算机具有使用g++ 5.3.0和clang++ 3.7.0编译的1 X 2500 MHz CPU和1 GB RAM
• Benchmark OS Arch Linux 2015.08 x86-64
• Benchmark (-std=c++11、-O3和-pthread)
• BM_Base* benchmark尝试测量填充std::vector<>的时间。为了更好地比较，应该从排序结果中减去该时间。

First benchmark使用512k大小对std::vector<int>进行排序。

[ 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

第二个基准测试使用512k大小(sizeof(Struct S) = 20)对std::vector<S>进行排序。

[ 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();

Answer 2

当有足够的内存可用时，std::stable_sort会执行NlogN比较。当内存不足时，它会降级为N((logN)^2)个比较。因此，当内存可用时，它与std::sort (在平均和最坏情况下都执行O(NlogN)比较)具有大致相同的效率。

对于感兴趣的人，sort()使用introsort (快速排序，当递归达到一定深度时切换到堆排序)，而stable_sort()使用merge sort。

Answer 3

大到足以保证一个单独的函数进行稳定的排序，而不是让std::sort()透明地进行排序。