¿Qué tan grande es la brecha de rendimiento entre std::sort y std::stable_sort en la práctica?

10 minutos de lectura

Ambos deberían ejecutarse en O(n log n), pero en general la ordenación es más rápida que la ordenación_estable. ¿Qué tan grande es la brecha de desempeño en la práctica? ¿Tienes alguna experiencia al respecto?

Quiero ordenar una gran cantidad de estructuras que tienen un tamaño de aproximadamente 20 bytes. La estabilidad del resultado estaría bien en mi caso, pero no es imprescindible. Por el momento, el contenedor subyacente es una matriz simple, tal vez podría cambiarse a std::deque más adelante.

  • Tenga en cuenta que std::sort normalmente se implementa como quicksort, y std::stable_sort es una forma sofisticada de ordenar por fusión.

    –Justin Meiners

    9 de julio de 2021 a las 22:15


  • @JustinMeiners quicksort es O (n ^ 2) en el peor de los casos, por lo tanto std::sort utiliza un híbrido que incorpora heapsort cuando la ordenación rápida recurre demasiado.

    – wcochran

    28 de marzo a las 18:12

  • @wcochran buen punto, estoy simplificando mucho. La ordenación de fusión STL también tiene algunos casos diferentes como ese: justinmeiners.github.io/programacion-eficiente-con-componentes/…

    –Justin Meiners

    29 de marzo a las 4:05

avatar de usuario
Alper

Hay buenas respuestas que compararon los algoritmos teóricamente. yo comparé std::sort y std::stable_sort con google/punto de referencia por curiosidad.

Es útil señalar con anticipación que;

  • La máquina de referencia tiene 1 X 2500 MHz CPU y 1 GB RAM
  • Sistema operativo de referencia Arch Linux 2015.08 x86-64
  • Benchmark compilado con g++ 5.3.0 y clang++ 3.7.0 (-std=c++11, -O3 y -pthread)
  • BM_Base* benchmark intenta medir el tiempo de llenado std::vector<>. Ese tiempo debe restarse de los resultados de clasificación para una mejor comparación.

Primeros tipos de referencia std::vector<int> con 512k Talla.

[ 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

Segundo tipo de referencia std::vector<S> con 512k Talla (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

Cualquiera a quien le guste ejecutar el punto de referencia, aquí está el código,

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

  • +1 por seguir adelante y hacer el punto de referencia. Tu trabajo parece sólido. Sin embargo, los resultados serían más accesibles si los resumiera en una forma más fácil de digerir, como dibujar un pequeño diagrama.

    – 5gon12eder

    8 de enero de 2016 a las 2:36

avatar de usuario
moinudín

std::stable_sort realiza comparaciones NlogN cuando hay suficiente memoria disponible. Cuando no hay suficiente memoria disponible, se degrada a N((logN)^2) comparaciones. Por lo tanto, es aproximadamente de la misma eficiencia que std::sort (que realiza comparaciones O(NlogN) tanto en el promedio como en el peor de los casos) cuando hay memoria disponible.

Para aquellos interesados, sort() usa un introsorteo (quicksort que cambia a heapsort cuando la recursión alcanza una cierta profundidad) y stable_sort() usa un ordenar por fusión.

  • LogN^2 generalmente no significa log(N^2) sino (log N)^2, y especialmente si ocurre en notación O grande. Esto sucede comúnmente con algoritmos que toman pasos O (N log N) con trabajo O (log N) por paso y viceversa. Entonces, no, no es un 2 constante.

    – MSalters

    1 de mayo de 2009 a las 13:35

  • Tu dices std::sort (which performs O(NlogN) comparisons in both average and worst case). Pero el enlace a std::sort dice: O(N·log(N)) en todos los casos solo desde C++11. Antes de C++ 11 no existía el requisito O(Nlog(N)) para el peor de los casos.

    usuario184968

    5 de diciembre de 2013 a las 11:31

Lo suficientemente grande como para garantizar una función separada que realice una ordenación estable y no tenga std::sort() hazlo de forma transparente.

  • jajaja De acuerdo, tal vez no sea la respuesta técnicamente más detallada, pero ciertamente mi favorita.

    – Pedro M.

    21 de junio de 2013 a las 18:15

A veces se necesita std::stable_sort() porque mantiene el orden de los elementos que son iguales.

Y el consejo convencional es que, si mantener el orden no es importante, debe usar std::sort() en su lugar.

Sin embargo, su contexto depende. Hay muchos datos que se ordenan mejor con ordenación estable, incluso si no necesita mantener el orden:

Quicksort se convierte rápidamente en el peor de los casos de rendimiento si los datos tienen puntos de pivote constantemente deficientes.

los Transformación de Burrows-Wheeler es un algoritmo utilizado como parte de la compresión de datos, por ejemplo bzip2. Requiere ordenar todas las rotaciones del texto. Para la mayoría de los datos de texto, la ordenación por combinación (como la usa a menudo std::stable_sort()) es sustancialmente más rápida que la ordenación rápida (como la usa normalmente std::sort()).

bbb es una implementación de BWT que destaca las ventajas de std::stable_sort() sobre sort() para esta aplicación.

¿Qué tan grande es la brecha de desempeño en la práctica? ¿Tienes alguna experiencia al respecto?

Sí, pero no salió como esperabas.

Tomé una implementación en C de Burrows-Wheeler Transform y la transformé en C++. Resultó mucho más lento que el código C (aunque el código era más limpio). Así que puse la instrumentación de temporización allí y parecía que qsort funcionaba más rápido que std::sort. Esto se estaba ejecutando en VC6. Luego se volvió a compilar con stable_sort y las pruebas se ejecutaron más rápido que la versión C. Otras optimizaciones lograron impulsar la versión C++ aproximadamente un 25 % más rápido que la versión C. Creo que era posible obtener más velocidad, pero la claridad del código estaba desapareciendo.

  • Básicamente, lo que estoy tratando de decir es probar en ambos sentidos.

    – graham.reeds

    1 de mayo de 2009 a las 13:56

avatar de usuario
Narendra norte

Estaba buscando algo similar, pero me sorprendió que nadie hablara sobre el espacio auxiliar.

Como creo, se supone que la implementación tanto de stable_sort como de sort garantiza O (NlogN) para todos los casos (mejor, promedio y peor).

Sin embargo, la diferencia existe en el espacio Auxiliar utilizado. stable_sort necesita un espacio auxiliar de O(N).

Puede que la diferencia de rendimiento resida en adquirir ese espacio. 🙂
De lo contrario, en teoría, se supone que tienen el mismo rendimiento.

sort debería hacer lo que necesita a menos que necesite esto -> stable_sort conserva el orden relativo de los elementos con valores equivalentes.

  • Básicamente, lo que estoy tratando de decir es probar en ambos sentidos.

    – graham.reeds

    1 de mayo de 2009 a las 13:56

avatar de usuario
bcmpinc

Si está clasificando una gran cantidad de estructuras, la velocidad de E/S de su memoria/disco comienza a ser más importante que el tiempo de ejecución asintótico. Además, el uso de la memoria también debe tenerse en cuenta.

Probé std::stable_sort en 2 Gb de datos (64B estructuras), sin saber que std::stable_sort crea una copia interna de los datos. La basura de intercambio que siguió casi bloqueó mi PC.

El uso de std::sort inestable reduce el uso de memoria en un factor de 2, lo que es útil cuando se ordenan arreglos grandes. Terminé el std::stable_sort, por lo que no puedo determinar cuánto más lento fue. Sin embargo, si no se requiere ordenación estable, creo que es mejor usar la ordenación inestable std::sort.

  • Si bien esto es probablemente demasiado pequeño en las computadoras modernas, cuando está clasificando conjuntos de datos muy grandes, es mejor usar un algoritmo de clasificación externo que hace un buen uso del disco para almacenar resultados intermedios; como la ordenación por combinación externa.

    – Más claro

    23 de marzo de 2015 a las 7:27

  • (y, a veces, ordenar punteros es mucho más rápido que ordenar estructuras, y viceversa, según el tamaño de las estructuras, la RAM disponible, etc.)

    – Erik Aronesty

    14 de diciembre de 2015 a las 18:41


¿Ha sido útil esta solución?