Ich habe einen Weg gefunden, der den Quicksort-Algorithmus (soweit ich es getestet habe) über das bereits Erreichte hinaus verbessert. Ich arbeite daran, es zu testen, und dann möchte ich das herausfinden. Ich würde jedoch einige Hilfe bei einigen Dingen zu schätzen wissen. Also hier sind meine Fragen. Mein gesamter Code ist übrigens in C++.Einige Sortierfragen
Eine der Arten, die ich mit meinem Quicksort verglichen habe, ist die std :: sort aus der C++ - Standardbibliothek. Es scheint jedoch extrem langsam zu sein. Ich sortiere nur Arrays aus Ints und Longs, aber es scheint etwa 8-10 mal langsamer zu sein als mein Quicksort und ein Standard-Quicksort von Bentley und McIlroy (und vielleicht auch Sedgewick). Hat jemand irgendwelche Ideen, warum es so langsam ist? Der Code, den ich für die Sortierung verwende, ist nur std :: sort (a, a + numelem); Dabei steht a für das Array longs oder ints und numelem für die Anzahl der Elemente im Array. Die Zahlen sind sehr zufällig und ich habe verschiedene Größen sowie unterschiedliche Mengen wiederholter Elemente ausprobiert. Ich habe auch versucht qsort, aber es ist noch schlimmer als ich erwartet hatte. Edit: Ignorieren Sie diese erste Frage - es wurde gelöst.
Ich würde gerne mehr gute Quicksort-Implementierungen zum Vergleich mit meinem Quicksort finden. Bisher habe ich einen Bentley-McIlroy und einen Vergleich mit der ersten veröffentlichten Version von Vladimir Yaroslavskiys Dual-Pivot Quicksort. Außerdem plane ich die Portierung von timsort (was ich glaube, dass es sich um eine Merge-Sortierung handelt) und den optimierten Dual-Pivot-Quicksort aus der jdk 7-Quelle. Welche anderen guten Quicksorts-Implementierungen kennen Sie? Wenn sie nicht in C oder C++ sind, könnte das okay sein, weil ich ziemlich gut portieren kann, aber ich würde C- oder C++ - Einsen bevorzugen, wenn Sie sie kennen.
Wie empfehlen Sie, über meine Ergänzungen zum Quicksort zu informieren? Bisher scheint mein Quicksort deutlich schneller zu sein als alle anderen Quicksorts, gegen die ich ihn getestet habe. Die Hauptquelle seiner Geschwindigkeit ist, dass es wiederholte Elemente viel effizienter behandelt als andere Methoden, die ich gefunden habe. Es eliminiert das Worst-Case-Verhalten fast vollständig, ohne viel Zeit für die Überprüfung wiederholter Elemente zu investieren. Ich habe darüber in den Java-Foren gepostet, aber keine Antwort bekommen. Ich habe auch versucht, Jon Bentley zu schreiben, weil er mit Vladimir an seinem Dual-Pivot Quicksort arbeitete und keine Antwort bekam (obwohl mich das nicht so sehr überraschte). Soll ich ein Papier darüber schreiben und es auf arxiv.org setzen? Sollte ich in einigen Foren posten? Gibt es einige Mailinglisten, zu denen ich schreiben sollte? Ich arbeite seit einiger Zeit daran und meine Methode ist echt. Ich habe einige Erfahrung mit der Veröffentlichung von Forschung, weil ich ein Doktorand in Computational Physics bin. Sollte ich versuchen, jemanden in der Informatikabteilung meiner Universität anzusprechen? Übrigens habe ich auch einen anderen Dual-Pivot Quicksort entwickelt, aber er ist nicht besser als mein Single-Pivot Quicksort (obwohl es besser ist als Vladimirs Dual-Pivot Quicksort mit einigen Datensätzen).
Ich schätze Ihre Hilfe sehr. Ich möchte nur hinzufügen, was ich in der Computerwelt kann. Ich bin nicht daran interessiert, diese oder irgendeine absurde Sache so zu patentieren.
Bitte teilen Sie mir mit, dass Sie Kompilierung und Profiling mit aktivierten Optimierungen durchgeführt haben. – GManNickG
Das scheint wirklich offensichtlich, aber wenn Sie 'std :: sort' verwenden, haben Sie volle Optimierungen eingeschaltet? Ohne sie - implementierungsabhängig - kann ein erheblicher Funktionsaufruf-Overhead entstehen. Andernfalls würde es wahrscheinlich helfen, wenn Sie Ihren Code und die relativen Timings gepostet haben. Die tatsächliche Leistung von 'qsort' und' std :: sort' hängt von der Implementierung ab. –
blöde Frage (nur weil ich schon mal davon gebissen worden bin): Hast du eine Testsuite von date? Und es ist nicht ausreichend zu überprüfen, dass die Ausgabe sortiert ist. Stellen Sie außerdem sicher, dass jedes Eingabeelement in der Ausgabe vorhanden ist. –