Leistung: Sortieren von 'm' Vektoren mit N/m Elementen im Vergleich zum Sortieren eines einzelnen Vektors mit N Elementen

Question

Operation A

Ich habe N Vektoren, die jeweils eine bestimmte Anzahl von eindeutigen 3D-Punkten enthalten. Zum Beispiel: std::vector<double*> vec1; und so weiter

Ich führe Sortiervorgänge für jeden der Vektoren durch:

 std::sort(vec1.begin(), vec1.end(), sortCriteria());
 std::sort(vec2.begin(), vec2.end(), sortCriteria());
 std::sort(vec3.begin(), vec3.end(), sortCriteria());

Operation B

Angenommen, ich habe einen Vektor namens "all_point_vector", der die 3D-Punkte von vec1, vec2, vec3 ... enthält.

d.h. 3D-Punkte in all_point_vector = points_in_vec1 +.... +Punkte_im_Vektor3.

und ich führe den Sortiervorgang durch:

std::sort(all_point_vec.begin(), all_point_vec.end(), sortCriteria());

Meine Frage ist, welche der oben genannten Methoden (Operation A oder B) im Allgemeinen schneller ist: das Sortieren eines einzelnen Vektors (all_point_vector) oder das Sortieren einzelner Vektoren. Ich bin nur an der Ausführungsgeschwindigkeit dieser beiden Operationen interessiert.

Danke

Answer 1

Sortieren ist eine O(n log n) Betrieb. Sortierung N Vektoren mit m/N Elemente wird deutlich schneller sein als das Sortieren eines einzelnen Vektors von m Elemente, wenn Sie die m .

Welches ist schneller für jede feste m kann nur durch Profiling ermittelt werden.

Answer 2

Was avakar In der Theorie sollte das Sortieren einiger kurzer Vektoren schneller sein als das Sortieren des gesamten Vektors, in der Praxis sollte man messen. Ich möchte nur etwas mehr Mathematik zeigen:

Es soll sein k Sequenzen und die i -te Folge hat n _i Anzahl der Elemente. Die Gesamtzahl der Elemente sei N \= n ₁ + ... + n _k . Die Sortierung der einzelnen Sequenzen hat die Komplexität O(n ₁ logn ₁ + ... + n _k logn _k ). Das Sortieren der großen Folge hat die Komplexität O(N logN) = O((n ₁ + ... + n _k )logN) = O(n ₁ logN + ... + n _k logN). Jetzt müssen wir vergleichen

A = n ₁ logn ₁ + ... + n _k logn _k

B = n ₁ logN + ... + n _k logN

Da N > n _i für alle i , logN > logn _i für alle i . Daher ist B unbedingt größer als A, d. h. das Sortieren der gesamten Folge wird mehr Zeit in Anspruch nehmen.

Answer 3

Sortieren eines einzelnen Arrays von m Elementen ist ein anderes Problem als das Sortieren der gleichen Anzahl von Elementen, die in N Arrays, denn im geteilten Fall haben Sie immer noch keine Gesamtreihenfolge aller Elemente.

Unter der Annahme, dass m = 1024 ist, ergibt sich für den Singleton-Fall m log m = 1024*10 = 10240.

Si N=2 Sie haben 512*9 + 512*9 = 9216, aber Sie müssen immer noch einen Zusammenführungsschritt von 1024 Vergleichen durchführen, und 9216 + 1024 = 10240, es ist also dasselbe.

[Eigentlich ist auf jeder Ebene der Sortierung die Anzahl der Vergleiche um 1 geringer als die Anzahl der zusammenzuführenden Elemente, aber das Gesamtergebnis ist immer noch O(n log n)]

HINZUFÜGEN: Wenn Sie, wie Sie anmerkten, die Zusammenführung nicht durchführen müssen, ist der geteilte Fall schneller. (In diesem Fall könnten Sie natürlich auch die m Artikel in N=m Arrays und nicht einmal die Mühe des Sortierens ;-)