在實踐中，std :: sort和std :: stable_sort之間的性能差距有多大？

Question

兩者都應該在O（n log n）中運行，但通常排序比stable_sort快。實踐中的性能差距有多大？你有這方面的經驗嗎？

我想排序大量的大小約爲20字節的結構。結果的穩定性對我來說會很好，但這不是必須的。目前，底層容器是一個普通數組，可能稍後可能會將其更改爲std :: deque。

Answer 1

從理論上比較算法有很好的答案。爲了好奇，我將std::sort和std::stable_sort與google/benchmark進行了基準比較。

提前指出是有用的;

• 基準機具有1 X 2500 MHz CPU和1 GB RAM
• 基準OS Arch Linux 2015.08 x86-64
• 基準與g++ 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(); 

Answer 2

大到足以保證一個單獨的函數，它穩定的排序，而不是有std::sort()做到透明。

Answer 3

std::stable_sort當有足夠的內存可用時，執行NlogN比較。當內存不足時，它會降級到N（（logN）^ 2）比較。因此，當存儲器可用時，其效率與std::sort（在平均值和最差情況下執行O（NlogN）比較）的效率大致相同。對於那些有興趣的人，sort（）使用introsort（當遞歸達到特定深度時切換到堆排序的快排），而stable_sort（）使用merge sort。

Answer 4

練習中的性能差距有多大？你有什麼經驗 呢？

是的，但它並沒有去你所期望的方式。

我採用了Burrows-Wheeler Transform和C++的C實現 - ified。結果比C代碼慢得多（儘管代碼更清晰）。所以我把計時器放在那裏，看起來qsort的執行速度比std :: sort快。這是在VC6中運行。然後用stable_sort重新編譯，測試運行速度比C版本快。其他優化設法將C++版本比C版本快25％。我認爲有可能提高速度，但代碼的清晰度正在消失。

Answer 5

有時需要std :: stable_sort（），因爲它維護的元素的順序是相等的。

而傳統的建議是，如果維護順序不重要，則應該使用std :: sort（）來代替。

但是，其上下文依賴。有大量數據的最好用穩定的排序進行排序，即使你並不需要維持秩序：

快速排序很快變得最壞情況下的性能，如果該數據一貫較差支點。

的​​是用作數據壓縮，例如的一部分的算法bzip2。它需要對文本的所有旋轉進行排序。對於大多數文本數據，合併排序（通常由std :: stable_sort（）使用）比quicksort（通常由std :: sort（）使用）快得多。

bbb是BWT實現，指出（）性病的優勢:: stable_sort（）在排序這種應用。

Answer 6

如果要排序大量的結構，你的內存的IO速度/盤開始變得比漸近運行時間更重要。此外，還應該考慮內存使用情況。

我試圖在數據（64B結構）的2Gb上的std :: stable_sort，不知道std :: stable_sort創建數據的內部副本。隨後的交換垃圾幾乎鎖定了我的電腦。

使用不穩定的std :: sort會將內存使用量減少2倍，這對排序大型數組非常有用。我終止了std :: stable_sort，所以我不能確定它是多慢。但是，如果不需要穩定的排序，那麼我認爲最好使用不穩定的std :: sort。

Answer 7

一直在尋找類似的東西 - 但很驚訝沒有人談論的輔助空間。

正如我相信 - stable_sort和排序的實施應該保證O（NlogN）的所有（最好，平均最差）案件。

但是，所使用的輔助空間存在差異。 stable_sort需要O（N）的輔助空間。

可能是性能上的差異在於獲取該空間。 :)
否則，理論上 - 他們應該是相同的w.r.t表現。

排序應該做你需要的，除非你需要這個 - > stable_sort保留元素與等價值的相對順序。