2010-01-20 8 views
15

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

  1. 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.

  2. 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.

  3. 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.

+2

Bitte teilen Sie mir mit, dass Sie Kompilierung und Profiling mit aktivierten Optimierungen durchgeführt haben. – GManNickG

+1

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. –

+0

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. –

Antwort

11

Wenn Sie Vertrauen in Ihre Arbeit haben, versuchen Sie es auf jeden Fall so schnell wie möglich mit jemandem zu besprechen, der sich an Ihrer Universität auskennt. Es reicht nicht aus, zu zeigen, dass Ihr Code schneller als eine andere Prozedur auf Ihrem Computer ausgeführt wird. Sie müssen mathematisch beweisen, welchen Leistungsgewinn Sie durch die Analyse Ihres Algorithmus erreicht haben. Ich würde sagen, das erste, was zu tun ist, ist sicherzustellen, dass beide Algorithmen, die Sie vergleichen, optimal implementiert und kompiliert werden - Sie könnten sich hier nur etwas vormachen. Die Wahrscheinlichkeit, dass ein Individuum eine so deutliche Verbesserung bei einer so wichtigen Sortiermethode erzielt, ohne bereits gründliche Kenntnisse über die akzeptierten Varianten zu besitzen, erscheint nur winzig. Lassen Sie mich jedoch nicht entmutigen. Es sollte sowieso interessant sein. Wären Sie bereit, den Code hier zu posten? ...Da Quicksort besonders anfällig für Worst-Case-Szenarien ist, können die Tests, die Sie ausführen möchten, eine große Wirkung haben, ebenso wie die Wahl der Pivots. Im Allgemeinen würde ich sagen, dass jeder Datensatz mit einer großen Anzahl von gleichwertigen Elementen oder einem bereits sehr sortierten Element nie eine gute Wahl für Quicksort ist - und es gibt bereits bekannte Möglichkeiten, diese Situation zu bekämpfen, und bessere alternative Sortiermethoden .

+0

Ich arbeite seit einigen Monaten verschiedene Verbesserungen an QuickSorts ein und aus. Ich habe das Gefühl, dass mir die wichtigsten Verbesserungen, einschließlich der besseren Pivotauswahl (Median-of-3 oder Randomization), sehr wohl bewusst sind. Ich benutze Iteration anstelle von Rekursion (die ich aus Vereinfachungsgründen zunächst ignoriere und nur rekursive Funktionen vergleiche), sortiere die kleinere Partition zuerst, mit Insertion Sortierung, wenn die Größe eines Arrays klein genug wird, Sedgewicks konvergierende Zeiger Methode und einige andere. Es gibt auch die Methoden für den Umgang mit wiederholten Elementen (Dutch National Flag und Bentley-McIlroy) –

+0

Ich habe auch versucht, meine Verbesserung zu finden, weil ich dachte, dass jemand anderes es sich ausgedacht haben muss, aber ich konnte es nirgends finden . –

+0

@Justin Ich finde es merkwürdig, dass Sie so viel Wissen zum Thema Quicksort haben, genug, um Sie glauben zu lassen, Sie hätten den Algorithmus verbessert, wissen aber nicht, wie Sie Ihre Verbesserungen richtig testen können, selbst wenn sie nicht isoliert werden Skalare Verbesserungen, die von Ihren Entwicklungs- und Betriebsumgebungen angeboten werden. –

7

Wenn Sie wirklich einen Durchbruch gemacht haben und die Mathematik haben, um es zu beweisen, sollten Sie versuchen, es in der Journal of the ACM veröffentlicht zu bekommen. Es ist definitiv eine der renommiertesten Fachzeitschriften für Informatik.

Die zweitbeste wäre eine der wie Transactions on Software Engineering.

+0

Ja, machen Sie zuerst eine Analyse auf Ihrem Algorithmus. Genauer gesagt: Berechnen Sie die erwartete Anzahl an Vergleichen und Swaps und führen Sie eine Worst-Case-Analyse durch. Wenn du deine Idee einsendest, ohne richtig geforscht zu haben, dann bezweifle ich, dass sie deine Idee ernst nehmen wird. – marcusklaas