Schnellster Sortieralgorithmus für eine bestimmte Situation

Question

Was ist der schnellste Sortieralgorithmus für eine große Anzahl (Zehntausende) von Gruppen mit 9 positiven Werten mit doppelter Genauigkeit, wobei jede Gruppe einzeln sortiert werden muss? Es muss also schnell eine kleine Anzahl von möglicherweise wiederholten Werten mit doppelter Genauigkeit, oft hintereinander, sortiert werden. Die Werte befinden sich im Intervall [0..1]. Ich interessiere mich nicht für Raumkomplexität oder Stabilität, nur für Geschwindigkeit.

Answer 1

Sortierung jeder Gruppe einzeln, Zusammenführen Sortierung wäre wahrscheinlich am einfachsten mit guten Ergebnissen zu implementieren.

Sortier Netzwerk wäre wahrscheinlich die schnellste Lösung sein: http://en.wikipedia.org/wiki/Sorting_network

Answer 2

Gute Frage, da dies zu kommt down „Der schnellste Weg, eine Reihe von 9 Elemente zu sortieren“, und die meisten Vergleiche zwischen und Analyse von Sortiermethoden sind etwa großer N. Ich nehme an, die "Gruppen" sind klar definiert und spielen hier keine wirkliche Rolle.

Sie werden wahrscheinlich ein paar Kandidaten benchmarken müssen, weil hier viele Faktoren (Lokalität) ins Spiel kommen.

In jedem Fall klingt es wie eine gute Idee parallel zu machen. Verwenden Sie Parallel.For(), wenn Sie NET4 verwenden können.

Answer 3

Ich denke, Sie müssen ein paar Beispiele ausprobieren, um zu sehen, was am besten funktioniert, da Sie ungewöhnliche Bedingungen haben. Meine Vermutung, dass das Beste aus

• Sortier Netzwerk
• Art Einfügen
• schnelle Art wird (eine Ebene - eine Art unter Insertion)
• Mergesort

dass Doppel Gegeben Genauigkeitszahl sind relativ lang Ich vermute, dass Sie nicht besser mit einer Radix-Sortierung tun, aber fühlen Sie sich frei, es hinzuzufügen.

Für Was es wert ist, Java verwendet schnelle Sortierung nach Doppel, bis die Anzahl der zu sortierenden Objekte unter 7 fällt, bei denen Insertion Sort verwendet wird. Die dritte Option ahmt diese Lösung nach.

Auch Ihr Gesamtproblem ist embarrassingly parallel, so dass Sie die Parallelität verwenden möchten, wenn möglich. Das Problem sieht für eine verteilte Lösung zu klein aus (im Netzwerk wird mehr Zeit verloren als gespart), aber wenn es richtig eingerichtet ist, kann Ihr Problem sehr effektiv mehrere Kerne nutzen.

Answer 4

Es sieht so aus, als ob Sie den zyklusigsten Weg wünschen, 9 Werte zu sortieren. Da die Anzahl der Werte begrenzt ist, würde ich (wie Kathy vorgeschlagen hat) zuerst eine entrollte Sortierung an den ersten 4 Elementen und den zweiten 5 Elementen vornehmen. Dann würde ich diese beiden Gruppen zusammenführen.

Hier ist ein abgerollt Insertionsort aus 4 Elementen:

if (u[1] < u[0]) swap(u[0], u[1]); 
if (u[2] < u[0]) swap(u[0], u[2]); 
if (u[3] < u[0]) swap(u[0], u[3]); 

if (u[2] < u[1]) swap(u[1], u[2]); 
if (u[3] < u[1]) swap(u[1], u[3]); 

if (u[3] < u[2]) swap(u[2], u[3]); 

Hier ist ein Merge-Schleife. Der erste Satz von 4 Elementen ist in u und der zweite Satz von 5 Elementen in v. Das Ergebnis ist r.

i = j = k = 0; 
while(i < 4 && j < 5){ 
    if (u[i] < v[j]) r[k++] = u[i++]; 
    else if (v[j] < u[i]) r[k++] = v[j++]; 
    else { 
    r[k++] = u[i++]; 
    r[k++] = v[j++]; 
    } 
} 
while (i < 4) r[k++] = u[i++]; 
while (j < 5) r[k++] = v[j++];