¿Cuál es la forma más eficaz de borrar duplicados y ordenar un vector?
Necesito tomar un vector de C++ con potencialmente muchos elementos, borrar duplicados y ordenarlo.
Actualmente tengo el siguiente código, pero no funciona.
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
¿Cómo puedo hacer esto correctamente?
Además, ¿es más rápido borrar primero los duplicados (similar al código anterior) o realizar la clasificación primero? Si realizo la clasificación primero, ¿se garantiza que permanecerá ordenada después de std::uniqueejecutarla?
¿O hay otra forma (quizás más eficiente) de hacer todo esto?
Estoy de acuerdo con R. Pate y Todd Gardner ; Podría std::setser una buena idea aquí. Incluso si estás atascado usando vectores, si tienes suficientes duplicados, sería mejor que crearas un conjunto para hacer el trabajo sucio.
Comparemos tres enfoques:
Solo usando vector, ordenar + único
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
Convertir a conjunto (manualmente)
set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );
Convertir a conjunto (usando un constructor)
set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
Así es como se comportan a medida que cambia el número de duplicados:
Resumen : cuando la cantidad de duplicados es lo suficientemente grande, en realidad es más rápido convertir a un conjunto y luego volcar los datos nuevamente en un vector .
Y por alguna razón, hacer la conversión del conjunto manualmente parece ser más rápido que usar el constructor del conjunto, al menos en los datos aleatorios del juguete que usé.
Rehice el perfil de Nate Kohl y obtuve resultados diferentes. Para mi caso de prueba, ordenar directamente el vector siempre es más eficiente que usar un conjunto. Agregué un nuevo método más eficiente, usando un archivo unordered_set.
Tenga en cuenta que el unordered_setmétodo solo funciona si tiene una buena función hash para el tipo que necesita único y ordenado. ¡Para enteros, esto es fácil! (La biblioteca estándar proporciona un hash predeterminado que es simplemente la función de identidad). Además, no olvide ordenar al final ya que unordered_set es, bueno, desordenado :)
Investigué un poco dentro de la setimplementación unordered_sety descubrí que el constructor en realidad construye un nuevo nodo para cada elemento, antes de verificar su valor para determinar si realmente debería insertarse (al menos en la implementación de Visual Studio).
Aquí están los 5 métodos:
f1: Solo usando vector, sort+unique
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
f2: Convertir a set(usando un constructor)
set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
f3: Convertir a set(manualmente)
set<int> s;
for (int i : vec)
s.insert(i);
vec.assign( s.begin(), s.end() );
f4: Convertir a unordered_set(usando un constructor)
unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );
f5: Convertir a unordered_set(manualmente)
unordered_set<int> s;
for (int i : vec)
s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );
Hice la prueba con un vector de 100.000.000 ints elegidos aleatoriamente en los rangos [1,10], [1,1000] y [1,100000]
Los resultados (en segundos, cuanto más pequeño, mejor):
range f1 f2 f3 f4 f5
[1,10] 1.6821 7.6804 2.8232 6.2634 0.7980
[1,1000] 5.0773 13.3658 8.2235 7.6884 1.9861
[1,100000] 8.7955 32.1148 26.5485 13.3278 3.9822
std::uniquesolo elimina elementos duplicados si son vecinos: primero debes ordenar el vector antes de que funcione como deseas.
std::uniqueestá definido como estable, por lo que el vector seguirá ordenado después de ejecutarse como único en él.
