Quanto è grande il divario prestazionale tra std :: sort e std :: stable_sort in pratica?
https://stackoverflow.com/questions/810951
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Entrambi dovrebbero essere eseguiti in O (n log n), ma in genere l'ordinamento è più veloce di stable_sort. Quanto è grande il divario prestazionale in pratica? Hai qualche esperienza al riguardo?
Voglio ordinare un numero molto grande di strutture che hanno una dimensione di circa 20 byte. La stabilità del risultato sarebbe buona nel mio caso, ma non è un must. Al momento il contenitore sottostante è un array semplice, forse potrebbe essere cambiato in uno std :: deque in seguito.
Soluzione
Ci sono buone risposte che hanno confrontato gli algoritmi teoricamente. Ho confrontato std::sort e std::stable_sort con google / benchmark per motivi di curiosità.
È utile precisarlo in anticipo;
- La macchina di benchmark ha
1 X 2500 MHz CPUe1 GB RAM - Benchmark OS
Arch Linux 2015.08 x86-64 - Benchmark compilato con
g++ 5.3.0eclang++ 3.7.0(-std=c++11,-O3e-pthread) -
BM_Base*benchmark tenta di misurare il tempo di popolamentostd::vector<>. Quel tempo dovrebbe essere sottratto dai risultati dell'ordinamento per un migliore confronto.
Il primo benchmark ordina std::vector<int> con 512k dimensione.
[ 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
Il secondo benchmark ordina std::vector<S> con sizeof(Struct S) = 20 dimensioni (<=>).
[ 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
Chiunque desideri eseguire il benchmark, ecco il codice
#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();
Altri suggerimenti
std::stable_sort esegue confronti NlogN quando è disponibile memoria sufficiente. Quando la memoria disponibile è insufficiente, viene ridotta a confronto N ((logN) ^ 2). Pertanto è all'incirca della stessa efficienza di std::sort (che esegue O ( NlogN) confronti sia nella media che nel peggiore dei casi) quando la memoria è disponibile.
Per gli interessati, sort () utilizza un introsort (quicksort che passa a heapsort quando ricorsione raggiunge una certa profondità) e stable_sort () utilizza un unisci ordinamento .
Abbastanza grande da giustificare una funzione separata che fa un ordinamento stabile e non lo fa std::sort() in modo trasparente.
A volte è necessario std :: stable_sort () perché mantiene l'ordine degli elementi uguali.
E il consiglio convenzionale è che, se mantenere l'ordine non è importante, dovresti usare invece std :: sort ().
Tuttavia, dipende dal suo contesto. Esistono molti dati che vengono ordinati meglio con ordinamento stabile anche se non è necessario mantenere l'ordine:
Quicksort diventa rapidamente il caso peggiore se i dati hanno punti pivot costantemente bassi.
La Burrows-Wheeler Transform è un algoritmo utilizzato come parte della compressione dei dati, ad es. bzip2 . Richiede l'ordinamento di tutte le rotazioni del testo. Per la maggior parte dei dati di testo, unisci ordinamento (come spesso usato da std :: stable_sort ()) è sostanzialmente più veloce di quicksort (come di solito usato da std :: sort ()).
bbb è un'implementazione di BWT che rileva i vantaggi di std :: stable_sort () over sort () per questa applicazione.
Quanto è grande il gap prestazionale pratica? Hai qualche esperienza a riguardo?
Sì, ma non è andata come previsto.
Ho preso un'implementazione in C di Burrows-Wheeler Transform e C ++ - se ne sono accorto. Si è rivelato molto più lento del codice C (anche se il codice era più pulito). Quindi ho messo la strumentazione di cronometraggio lì dentro e sembrava che il qsort si stesse comportando più velocemente dello std :: sort. Questo era in esecuzione in VC6. È stato quindi ricompilato con stable_sort e i test sono stati eseguiti più velocemente della versione C. Altre ottimizzazioni sono riuscite a spingere la versione C ++ ~ il 25% più velocemente rispetto alla versione C. Penso che sia stato possibile aumentare la velocità, ma la chiarezza del codice stava scomparendo.
Se stai ordinando un gran numero di strutture, la velocità di I / O della tua memoria / disco inizia a diventare più importante del tempo di esecuzione asintotico. Inoltre, dovrebbe essere preso in considerazione anche l'uso della memoria.
Ho provato std :: stable_sort su 2Gb di dati (strutture 64B), non sapendo che std :: stable_sort crea una copia interna dei dati. Lo swash trashing che seguì ha quasi bloccato il mio pc.
L'uso di std :: sort instabile riduce l'utilizzo della memoria di un fattore 2, utile quando si ordinano array di grandi dimensioni. Ho terminato std :: stable_sort, quindi non riesco a determinare quanto sia stato più lento. Tuttavia, se non è richiesto un ordinamento stabile, penso che sia meglio usare l'instabile std :: sort.
Stava cercando qualcosa di simile - ma era sorpreso che nessuno parlasse di spazio ausiliario.
Come credo - l'implementazione di stable_sort e sort dovrebbe garantire O (NlogN) per tutti i casi (Best, Average & amp; Worst).
Tuttavia, la differenza esiste nello spazio ausiliario utilizzato. stable_sort necessita di uno spazio ausiliario di O (N).
Potrebbe essere la differenza nelle prestazioni nell'acquisizione di quello spazio. :)
Altrimenti, teoricamente - dovrebbero essere le stesse prestazioni w.r.t.
sort dovrebbe fare quello che ti serve a meno che tu non ne abbia bisogno - > stable_sort conserva l'ordine relativo degli elementi con valori equivalenti.
