Median-Funktion in der C-Math-Bibliothek?

Hier geht's .

Konventionelle Methode: (nicht empfohlen, wenn Sie an der Bildverarbeitung arbeiten)

Es gibt jedoch zwei Funktionen, um den Medianwert am schnellsten zu berechnen, ohne das Array der Kandidaten zu sortieren. Die folgenden sind mindestens 600% schneller als herkömmliche Methoden zur Berechnung des Medians. Leider sind sie kein Teil von C Standard Library oder C ++ STL.

Schnellere Methoden:

In C ++ mache ich diese Template-Funktionen und wenn die Zahlen für solche Funktionen größer oder kleiner werden (eine Richtung), verwende int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; Typen anstelle von regulären [stdint.h] -Typen (z. B. uint16_t; uint32_t usw.)

Nein, in der Standard-C-Bibliothek gibt es keine solche Funktion.

Sie können jedoch einen implementieren (oder sicher Code online finden). Ein effizienter O (n) -Algorithmus zum Auffinden eines Medians wird als "Auswahlalgorithmus" bezeichnet und steht in Zusammenhang mit Quicksort. Lesen Sie alles hier .

Um den Median mit der Standard-C-Bibliothek zu berechnen, verwenden Sie die Standardbibliotheksfunktion qsort() und nehmen Sie dann das mittlere Element. Wenn das Array a und n Elemente hat, dann:

Sie müssen Ihre eigene compare -Funktion schreiben, die vom Typ eines Array-Elements abhängt. Für Details konsultiere die Manpage für qsort oder schaue im Index von Kernighan und Ritchie nach.

Nein, in der Standard-C-Bibliothek gibt es keine Median-Funktion.

Was ist mit std::nth_element ? Wenn ich die Art des Median richtig verstehe, würde dies Ihnen eine für eine ungerade Anzahl von Elementen geben.

Um den Median zu erhalten, können Sie das Zahlenfeld sortieren und nehmen:

1) wenn die Anzahl der Elemente ungerade ist - die Zahl in der Mitte

2) wenn die Anzahl der Items gerade ist - der Durchschnitt zweier Zahlen in der Mitte