Ich habe eine Frage, die sehr einfach erscheinen mag, aber in einem Kontext, in dem "jeder CPU-Tick zählt" (das ist ein Teil eines größeren Algorithmus, der auf Supercomputern verwendet wird).
Das Problem ist ziemlich einfach: Wie sortiere ich am schnellsten eine Liste von unsignierten langen langen int-Zahlen und ihren ursprünglichen Indizes? (Zu Beginn sind die vorzeichenlosen langen langen int-Zahlen in einer völlig zufälligen Reihenfolge.)
%Vor%Mit "schnellster Weg" meine ich: Welchen Algorithmus soll man verwenden: std :: sort, C qsort oder einen anderen im Web verfügbaren Sortieralgorithmus? Welcher Container (C-Array, std :: vector, std :: map ...)? Wie sortiere ich die Indizes zur selben Zeit (benutze Strukturen, std :: pair, std :: map ...)?
Vielen Dank!
BEARBEITEN: Wie viele Elemente müssen sortiert werden? - & gt; in der Regel 4o von Zahlen
Der naheliegende Ausgangspunkt wäre eine Struktur, für die operator< definiert ist:
... und ein std :: Vektor um die Daten zu speichern:
%Vor% und std::sort für die Sortierung:
Die einfache Tatsache ist, dass die normalen Container (und solche) so effizient sind, dass ihre Verwendung Ihren Code nicht wesentlich weniger effizient macht. Sie könnten in der Lage sein, etwas besser zu machen, indem Sie einen Teil auf eine andere Weise schreiben, aber Sie könnten vielleicht genauso leicht schlechter werden. Beginnen Sie mit einem soliden und lesbaren Test und testen Sie nicht (versuchen Sie es), vorzeitig zu optimieren.
Edit: natürlich in C ++ 11, können Sie stattdessen einen Lambda-Ausdruck verwenden:
%Vor% Dies ist im Allgemeinen ein wenig bequemer zu schreiben. Lesbarkeit hängt davon ab - für etwas Einfaches wie dieses würde ich sagen, sort ... by_number ist ziemlich lesbar, aber das hängt (schwer) von dem Namen ab, den Sie dem Vergleichsoperator geben. Mit dem Lambda lassen sich die eigentlichen Sortierkriterien leichter finden. Sie müssen also keinen Namen auswählen, damit der Code lesbar ist.
std::pair und std::sort passen ideal zu Ihren Anforderungen: Wenn Sie den Wert in pair.first und den Index in pair.second eingeben, können Sie einfach sort für einen Vektor von pair s aufrufen. so:
std::sort hat sich aufgrund des Mangels an Indirection und der Möglichkeit, kritische Operationen einzubinden, als schneller als die alte qsort herausgestellt.
Die Implementierungen von std::sort sind wahrscheinlich sehr optimiert und schwer zu übertreffen, aber nicht unmöglich. Wenn Ihre Daten fest und kurz sind, finden Sie Radix sort , um schneller zu sein. Timsort ist relativ neu und hat gute Ergebnisse für Python geliefert.
Sie können das Indexarray von dem Wertearray getrennt halten, aber ich denke, das zusätzliche Level der Indirektion wird sich als Geschwindigkeitsmörder erweisen. Besser, sie in einer Struktur oder std::pair zusammen zu halten.
Wie immer bei jeder geschwindigkeitskritischen Anwendung müssen Sie einige tatsächliche Implementierungen ausprobieren und vergleichen, um sicher zu wissen, welche die schnellste ist.
Es könnte es wert sein, Zahlen und Indizes zu trennen und dann nur Indizes zu sortieren , etwa so:
%Vor%Dies druckt:
%Vor% Die Idee ist, dass die zu sortierenden Elemente klein sind und sich daher während der Sortierung schnell bewegen. Bei modernen CPUs könnten die Auswirkungen des indirekten Zugriffs auf numbers auf das Caching jedoch diese Gewinne verderben. Daher empfehle ich, Benchmarks für realistische Datenmengen zu erstellen, bevor eine endgültige Entscheidung getroffen wird.
Verwenden Sie std::vector und std::sort . Das sollte die schnellste Sortiermethode bereitstellen. Um den ursprünglichen Index zu finden, erstellen Sie eine Struktur.
Dann erstellen Sie Ihr eigenes Vergleichsprädikat für sort, das die Zahl in der Struktur vergleicht.
%Vor% std::sort(vec.begin(), vec.end(), Predicate())
Vielleicht finden Sie dies , um eine interessante Lektüre zu sein. Ich würde mit der Art von STL anfangen und nur dann versuchen, es zu verbessern, wenn ich könnte. Ich bin nicht sicher, ob Sie Zugriff auf einen C ++ 11-Compiler (wie gcc4.7) auf diesem Supercomputer haben, aber ich würde vorschlagen, dass std :: sort mit std :: futures und std :: threads Sie ziemlich bekommen würde ein Stück vom Weg dahin, um das Problem in einer wartbaren Weise zu parallelisieren.
Hier ist eine weitere Frage , die std :: sort mit qsort vergleicht.
Schließlich gibt es diesen Artikel in Dr. Dobbs, der die Leistung von vergleicht parallele Algorithmen.