Ich habe 9 Werte in Form einer Matrix und muss den Median aus diesen Werten als Teil eines Simulationsprozesses berechnen.Quicksort in C++ ist langsam
Ich verwende Quicksort in C++ (d. H. Qsort()), was dazu führt, dass der Prozess langsam läuft (da dieser Prozess mehrere Male wiederholt).
Gibt es einen besseren Sortieralgorithmus, den ich verwenden könnte?
Sortierung ein Median zu bekommen sehr ineffizient Sie STL nth_element stattdessen verwenden:..
#include <algorithm>
// Assuming you keep the elements in a vector v of size len
std::nth_element(v.begin(), v.begin()+len/2, v.end());
median = v[len/2];
//... or, if the elements are in a simple array v[len], then
std::nth_element(v, v+len/2, v+len);
median = v[len/2];
Hinweis: die nth_element den Vektor ändern/Array v. Machen Sie ac opy zuerst, wenn Sie das Original bewahren müssen.
Insertion Sort ..
Auf kleine Datenmengen können Sie verschiedene Algorithmen verwenden, um optimale Leistung zu erhalten. QuickSort leuchtet, sobald der Datensatz wächst.
Es gibt verschiedene Ansätze. Sie können Datenstrukturen verwenden, in denen Sie beim Einfügen sortieren, und es gibt Onces, in denen Sie den vollständigen Datensatz sortieren. Sie müssen nur Ihren optimalen Algorithmus finden.
Einfügesortierung sollte bei zufälligen Daten schneller sein, oder? –
Tatsächlich verwenden einige Schnellsortierungen die Auswahl automatisch, wenn die Größe der Partitionen oder der Liste sehr klein wird. –
@Jeremy Vielleicht war es Insertion sort ... –
Wie schon erwähnt, muss man nicht komplett sortieren, um einen Median zu erhalten.
STL hat sort Algorithmus, der normalerweise Vergleich Inlining durchführen kann. Es hat auch einen intelligenteren Algorithmus als von qsort garantiert, mit worstcase von O (NlgN).
Hallo, Danke. Also muss ich nicht komplett sortieren, um den Median zu bekommen? In diesem Fall gibt es einen besseren Weg, um das Ergebnis zu erhalten? Vielen Dank. –
RE Punkt 2: hat wahrscheinlich einen Kompromiss im Weltraum. (wie Binärbaumsortierung) –
@Bi: Es gibt einen linearen Algorithmus für den Median - siehe den Link auf onybyone Kommentar. – EFraim
Nur 9 Werte? Quicksort ist übertrieben.
Verwenden Sie bei der Arbeit mit kleineren Datensätzen möglicherweise Einfügesortierung, Blasensortierung oder andere einfachere Sortieralgorithmen.
Leistung
Blase Art hat Worst-Case- und mittlere Komplexität sowohl О (n²), wobei n die Anzahl der Elemente ist sortiert werden. Es existieren viele Sortieralgorithmen mit der wesentlich besseren Worst-Case- oder durchschnittlichen Komplexität von O (n log n). Selbst andere О (n²) -Sortieralgorithmen, wie z. B. Insertion Sort, neigen dazu, eine bessere Leistung als Bubble Sort zu haben. Daher ist die Blasensortierung kein praktischer Sortieralgorithmus, wenn n groß ist.
Allerdings, Sie müssen nicht einmal sortieren, um den Median zu erhalten, wie andere vorgeschlagen haben.
Die Verwendung von Quicksort für nur 9 Werte wird ziemlich ineffizient sein. Bei solch einer kleinen Stichprobengröße ist es viel besser, eine Auswahlsortierung oder Ersatzsortierung zu verwenden ... bei diesen Sortiermethoden ist der Aufwand sehr gering.
Quicksort und Mergesort leuchten wirklich, wenn Ihre Stichprobengröße einen Schwellenwert erreicht, vielleicht 50+.
In diesen Situationen würde ich meinen eigenen Code schreiben, anstatt eine integrierte Funktion zu verwenden.
Bitte, bitte, bitte, empfehle niemals bubble sort, außer für Masochisten!
Für kleine Werte, Insertion Sortierung ist am besten, und es ist gut für andere Anwendungen (fast sortierte Daten beliebiger Länge).
Bearbeiten: bereinigt Formatierung, betonte die vorgeschlagene Antwort.
Ich kannte einen Professor, der ein großes Entwicklerteam eines Softwarehauses leitete, das jeder kennt. Er erzählte uns, dass er eine Reise nach Australien unternehmen musste, um die Leistungsprobleme eines Kunden zu beheben, und als er dort ankam, gab es eine Art Blase mit Kommentaren, die "schließlich zu etwas Besserem wechseln sollten". Er sagte, er habe den Mann an diesem Tag entlassen, weil er der Firma tausend Dollar an Unterstützung gekostet habe. –
@jeremy - Ich denke, der Manager und die QA hätten gefeuert werden sollen - nicht der Entwickler ... – Tim
@time Ja, ich stimme zu. Aber zumindest ist es abschreckend genug, um zu wissen, dass es Leute gibt, die dich feuern könnten, weil du das geschrieben hast. –
Sie haben nicht genug Werte mit Quicksort zu arbeiten und Sie sollten weniger hoch entwickelten Algorithmen verwenden (zB: Bubble Sort, Insertion sortieren, ... explanation here
Es gibt eine Kosten zu Quicksort das Setup zugeordnet ist und wann. Sie haben nicht genug Werte, es nutzlos ist, dieses Tier zu verwenden
Calling Quicksort ein Biest ist ... Uh ... Ich weiß es nicht. Einliner-Algorithmus kann kein Biest sein. – EFraim
Err, das einzige, was ich bekomme, wenn ich google "One Liner Quick Sort" ist eine Tonne Haskell Hits (und diese Frage: P). Kannst du mir eine Ein-Liner-Schnellsortierung in C++ geben? :) –
Der std :: sort() Algorithmus ist fast immer zu qsort() vorzuziehen. Es ist normalerweise einfacher zu benutzen und läuft schneller.
Wenn Sie ins Detail gehen wollen, gibt es tatsächlich eine Familie von Sortieralgorithmen. Stroustrup schreibt in Die C++ Programmiersprache, dass std :: sort oft nicht das genau richtige zu verwenden ist. In diesem Fall ist wahrscheinlich std :: nth_element() das, was Sie wollen.
Sie müssen die Werte nicht vollständig sortieren, um den Median zu finden: http://en.wikipedia.org/wiki/Selection_algorithm –
Also denken Sie, std :: sort würde besser funktionieren. Meine Beispielgröße ist entweder 9 oder 30. Danke. –
Wie bizarr. Ich bin fasziniert darüber, welche Datensätze immer 9 und 30 sind. :) Tut mir leid, ich bin neugierig. –