Median berechnen

mbu

Hallo,

ich habe eine Funktion geschrieben, die den Median aus einem gegebenen Vector berechnet. Die Funktion läuft auch soweit gut. Ich sortiere den Vector mit Quicksort und gebe dann halt das mittlere Element zurück.

Jetzt habe ich gestern unter http://www.devx.com/cplus/10MinuteSolution/30115/0/page/3 gelesen, dass das ganze auch noch etwas eleganter funktioniert, wenn ich aus der STL die priority_queue verwende, da diese schon geordnet ist.

Mein Code sieht wie folgt aus:

double median(const std::priority_queue<double,std::vector<double>,std::less<double> >& vec)
{
  return *( ( vec.begin() + vec.size() ) / 2 );
}

Jetzt beschwert sich der Compiler zu Recht, dass priority_queue keinen Member namens begin hat.

Unter o.g. URL wird leider nicht näher auf die priority_queue eingegangen, sondern weiter mit vector gearbeitet. Wie kann ich denn nun aber die priority_queue verwenden, um einfach das mittlere Element auszugeben?

Gruß, mbu.

CStoll

Ja, die priority_queue<> ist (grob) geordnet - aber nicht wirklich in einer Form, die du als "sortiert" bezeichnen würdest. Die PQ ist darauf ausgelegt, schnell das größte Element einer Sequenz zu liefern - und organisiert ihre Daten typischerweise in Form eines Heap.

Btw, der Verbesserungsvorschlag auf der angegebenen Seite ist nicht PQ - sondern Verwendung von nth_element() anstelle der vollständigen Sortierung

mbu

Da hast Du natürlich Recht, ich hatte das so verstanden, dass er die priority_queue zur Verwendung für Medianberechnung empfiehlt.

Im o.g. Code wäre sowieso ein Klammerfehler gewesen, nur mal so nebenbei, fällt mir gerade auf.

Ich hab den Code jetzt abgepasst, sieht jetzt so aus:

double median(std::vector<double>& vec)
{
  std::nth_element( vec.begin(), vec.begin() + vec.size() / 2, vec.end() );
  return *( vec.begin() + vec.size() / 2 );
}

Vielen Dank für die Lesehilfe, CStoll

Gruß, mbu.

Edit: Kann ich eigentlich damit rechnen, dass die o.g. Lösung mit nth_element schneller ist, als eine vollständige Sortierung des Vectors mit qsort?

Maxi

ja, nth element muss nicht alle soriteren sondern nur die hölfte, Die Zeitkomplexität wird sicherlich gleich sein, jedoch der konstante faktor kleiner als beim std::sort