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.
Wenn Sie jede Gruppe einzeln sortieren, wäre die Zusammenführung der Sortierung wahrscheinlich am einfachsten mit guten Ergebnissen zu implementieren.
Ein Sortiernetzwerk wäre wahrscheinlich die schnellste Lösung: Ссылка
Gute Frage, weil es sich um "Schnellste Art, ein Array von 9 Elementen zu sortieren" handelt, und die meisten Vergleiche und Analysen von Sortiermethoden sind groß. Ich nehme an, die "Gruppen" sind klar definiert und spielen nicht eine echte Rolle hier.
Sie werden wahrscheinlich ein paar Kandidaten benchmarken müssen, weil hier viele Faktoren (Lokalität) eine Rolle spielen.
Auf jeden Fall klingt es wie eine gute Idee, es parallel zu machen. Verwenden Sie Parallel.For() , wenn Sie NET4 verwenden können.
Ich denke, Sie müssen einige Beispiele ausprobieren, um zu sehen, was am besten funktioniert, da Sie ungewöhnliche Bedingungen haben. Meine Vermutung, dass das Beste einer von
sein wirdAngesichts der Tatsache, dass die doppelte Genauigkeitszahl relativ lang ist, vermute ich, dass Sie mit einer Radix-Sortierung nicht besser werden, aber fügen Sie sie einfach hinzu.
Java verwendet für Java einen schnellen Sortiervorgang, bis die Anzahl der zu sortierenden Objekte unter 7 liegt, bei der die Sortierreihenfolge verwendet wird. Die dritte Option ahmt diese Lösung nach.
Auch Ihr Gesamtproblem ist peinlich parallel , so dass Sie, wenn möglich, die Parallelität nutzen möchten. Das Problem scheint für eine verteilte Lösung zu klein zu sein (im Netzwerk wird mehr Zeit verloren als gespart), aber wenn es richtig eingerichtet ist, kann Ihr Problem sehr effektiv mehrere Kerne nutzen.
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) zunächst eine entrollte Sortierung der ersten 4 Elemente und der zweiten 5 Elemente vornehmen. Dann würde ich diese beiden Gruppen zusammenführen.
Hier ist eine abgerollte Einfügung von 4 Elementen:
%Vor% Hier ist eine Zusammenführungsschleife. Der erste Satz von 4 Elementen ist in u und der zweite Satz von 5 Elementen in v . Das Ergebnis ist in r .
Tags und Links algorithm language-agnostic performance sorting