Was ist der effizienteste Weg, um Duplikate zu löschen und einen Vektor zu sortieren?

Question

Ich muss einen C++ Vektor mit potenziell vielen Elementen nehmen, Duplikate löschen und sortieren.

Derzeit habe ich den unten stehenden Code, aber er funktioniert nicht.

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

Wie kann ich das richtig machen?

Ist es außerdem schneller, zuerst die Duplikate zu löschen (ähnlich wie oben codiert) oder zuerst die Sortierung durchzuführen? Wenn ich zuerst sortiere, bleibt es dann garantiert nach dem Ausführen von std::unique sortiert?

Oder gibt es einen anderen (vielleicht effizienteren) Weg, all das zu tun?

Answer 1

Ich stimme mit R. Pate und Todd Gardner überein; ein std::set könnte hier eine gute Idee sein. Selbst wenn Sie gezwungen sind, Vektoren zu verwenden, kann es besser sein, einen Satz zu erstellen, um die Arbeit zu erledigen, wenn Sie genug Duplikate haben.

Vergleichen wir drei Ansätze:

Nur Vector verwenden, sortieren + eindeutig

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

In Satz konvertieren (manuell)

set s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

In Satz konvertieren (mit einem Konstruktor)

set s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

So funktioniert es, wenn sich die Anzahl der Duplikate ändert:

Zusammenfassung: Wenn die Anzahl der Duplikate groß genug ist, ist es tatsächlich schneller, in einen Satz umzuwandeln und dann die Daten zurück in einen Vektor zu dumpen.

Und aus irgendeinem Grund scheint die manuelle Umwandlung in einen Satz schneller zu sein als die Verwendung des Satzkonstruktors - zumindest bei den Spielzeugzufallsdaten, die ich verwendet habe.

Answer 2

Ich habe das Profiling von Nate Kohl neu gemacht und habe unterschiedliche Ergebnisse erhalten. In meinem Testfall ist das direkte Sortieren des Vektors immer effizienter als die Verwendung eines Sets. Ich habe eine neue, effizientere Methode hinzugefügt, die ein unordered_set verwendet.

Bedenken Sie, dass die Methode unordered_set nur funktioniert, wenn Sie eine gute Hashfunktion für den Typ haben, den Sie eindeutig und sortiert benötigen. Für ints ist das einfach! (Die Standardbibliothek bietet eine Standard-Hashfunktion, die einfach die Identitätsfunktion ist.) Vergessen Sie außerdem nicht am Ende zu sortieren, da unordered_set, naja, ungeordnet ist :)

Ich habe einige Nachforschungen in der Implementierung von set und unordered_set gemacht und festgestellt, dass der Konstruktor tatsächlich für jedes Element einen neuen Knoten erstellt, bevor er den Wert überprüft, um zu bestimmen, ob es tatsächlich eingefügt werden sollte (zumindest in der Visual Studio-Implementierung).

Hier sind die 5 Methoden:

f1: Nur Verwendung von Vektor, sort + eindeutig

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

f2: Umwandlung in ein Set (Verwendung eines Konstruktors)

set s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3: Umwandlung in ein Set (manuell)

set s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4: Umwandlung in ein unordered_set (Verwendung eines Konstruktors)

unordered_set s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5: Umwandlung in ein unordered_set (manuell)

unordered_set s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

Ich habe den Test mit einem Vektor von 100.000.000 zufällig aus den Bereichen [1,10], [1,1000] und [1,100000] gewählten ints durchgeführt

Die Ergebnisse (in Sekunden, kleiner ist besser):

Bereich         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

Answer 3

std::unique entfernt nur doppelte Elemente, wenn sie benachbart sind: Du musst den Vektor zuerst sortieren, bevor es so funktioniert, wie du es beabsichtigst.

std::unique ist so definiert, dass es stabil ist, daher wird der Vektor nach dem Ausführen von unique immer noch sortiert sein.

Answer 4

Ich bin mir nicht sicher, wofür du das verwendest, also kann ich das nicht mit 100%iger Sicherheit sagen, aber normalerweise denke ich bei einem "sortierten, eindeutigen" Container an einen std::set. Das könnte besser zu deinem Anwendungsfall passen:

std::set foos(vec.begin(), vec.end()); // bereits sowohl sortiert als auch eindeutig

Ansonsten ist das Sortieren vor dem Aufruf von unique (wie es die anderen Antworten nahegelegt haben) der richtige Weg.

Answer 5

std::unique funktioniert nur bei aufeinanderfolgenden Duplikaten, daher sollten Sie besser zuerst sortieren. Es ist jedoch stabil, sodass Ihr Vektor sortiert bleibt.