median

Ist es tatsäclich so, dass der C++ Standard keine Funktion für Median (weder vector noch array) hat?

Gibt es da etwas in boost? Ich habe jetzt auf die schnelle nichts finden können.

SeppJ

Schau dir mal std::nth_element an. Das ist schon sehr nahe an der üblichen Definition von Median. Für eine ungerade Anzahl von Werten bekommst du damit direkt das Ergebnis. Für eine gerade Anzahl Werte ist die Frage, ob dir eine Definition des Median als "Eins neben der Mitte" reicht, oder ob du es genau nehmen willst und den Durchschnitt der beiden mittleren Elemente haben möchtest. In ersterem Fall liefert die nth_element ebenfalls direkt das Ergebnis. In letzterem Fall musst du erst einmal nth_element anwenden und dann (je nachdem auf welches Element du genau gezielt hast) entweder das Maximum der vorderen Hälfte oder das Minimum der hinteren Hälfte suchen und den Durchschnitt ermitteln.

SeppJ schrieb:

Schau dir mal ...

Selbst implementieren ist bei numerischen Funktionen ein No-Go. Näherungslösungen führen nur zur Verwirrung und Problemen. Ganz zu schweigen von optimaler Prozessornutzung.

Da würde ich eher das 50 Perzentil nutzen.

Wie kommt's das C++ da so hinkt?

SeppJ

Häh? Lass mich raten: Du hast nicht geschaut, was nth_element ist. nth_element ist die Verallgemeinerung des Medians auf das N'te Element. Das wird nicht magisch effizienter oder ineffizienter wenn N gleich der Hälfte der Anzahl der Elemente ist. Dass das nur auf Random Access Iteratoren arbeitet und lineare Laufzeit bezüglich der Eingabemenge hat sollte jedem, der auch nur die leiseste Ahnung hat, sofort klar machen, dass dahinter wohl Quickselect oder ein ähnlicher Algorithmus stecken wird. Viel Spaß, da eine bessere Implementierung zu finden!

SeppJ schrieb:

Häh? Lass mich raten: Du hast nicht geschaut, was nth_element ist.

Warum auch? Ich suche doch lieber gleich nach einer Lösung die so aussieht:

auto med = median( values );

Mehr als eine Zeile darf es bei einer solch grundlegenden Funktion nicht brauchen. Alles andere ist absurd. Warum sollte ich einen Median selbst implementieren wollen? Ich arbeite im medizinischen Sektor. Einen Commit mit nth element werde ich nie durchgewunken bekommen.

Habe auch schon was in der boost https://www.boost.org/doc/libs/1_67_0/doc/html/accumulators/reference.html#header.boost.accumulators.statistics.median_hpp gefunden. Früher oder später wandert es in den Standard und gut ist.

SeppJ

Lol, du hast also keine Ahnung oder willst nur trollen. Statistischer Median ist etwas völlig anderes.

asddasdasasd schrieb:

SeppJ schrieb:

Häh? Lass mich raten: Du hast nicht geschaut, was nth_element ist.

Warum auch?

Ja, du hättest ja auch was lernen können. Also besser Vorsicht!

C++ ist echt eine Schrottsprache. Die haben gar keine Klasse für die Zeichenkette "Hallo Welt!". Bloß so eine komische Klasse std::string, der man auch noch sagen muss, welche Zeichenkette man will. Das kann ja nicht einfach nicht gut sein, ich gucke das lieber gar nicht an!

SeppJ schrieb:

Lol, du hast also keine Ahnung oder willst nur trollen. Statistischer Median ist etwas völlig anderes.

Ich brauche den statistischen Median.

SeppJ schrieb:

Ja, du hättest ja auch was lernen können. Also besser Vorsicht!

Kann ich immer noch machen, danke.

SeppJ schrieb:

C++ ist echt eine Schrottsprache. Die haben gar keine Klasse für die Zeichenkette "Hallo Welt!". Bloß so eine komische Klasse std::string, der man auch noch sagen muss, welche Zeichenkette man will. Das kann ja nicht einfach nicht gut sein, ich gucke das lieber gar nicht an!

Mit string hast du dir natürlich das falsche Beispiel ausgesucht. Das ist mit Abstand die schlechteste Lösung für Zeichenketten. Wen ich schon an std::transform denken muss um lower oder uppercase zu bekommen, dann wundert es mich nicht, dass C++ in keiner neuen Technologie genutzt wird. Weder Big-Data, noch KI, noch Web Apps.

Schlangenmensch

asddasdasasd schrieb:

Mit string hast du dir natürlich das falsche Beispiel ausgesucht. Das ist mit Abstand die schlechteste Lösung für Zeichenketten. Wen ich schon an std::transform denken muss um lower oder uppercase zu bekommen, dann wundert es mich nicht, dass C++ in keiner neuen Technologie genutzt wird. Weder Big-Data, noch KI, noch Web Apps.

Wenn man keine Ahnung hat....

Schlangenmensch schrieb:

asddasdasasd schrieb:

Mit string hast du dir natürlich das falsche Beispiel ausgesucht. Das ist mit Abstand die schlechteste Lösung für Zeichenketten. Wen ich schon an std::transform denken muss um lower oder uppercase zu bekommen, dann wundert es mich nicht, dass C++ in keiner neuen Technologie genutzt wird. Weder Big-Data, noch KI, noch Web Apps.

Wenn man keine Ahnung hat....

So? Dann kläre mich mal auf wie der jetzige Stand und Kodierung? Gibt es ein string ::to_lower? Entscheiden sich die meisten immer noch für UTF16? Das ist nämlich genau so ein Armutszeugnis wie das jahrelange Fehlen von string ::to_double.

DocShoe

Stell dir vor du bist doof und jeder merkt's...

DocShoe schrieb:

Stell dir vor du bist doof und jeder merkt's...

Da helfen auch keine persönlichen Angriffe.

hustbaer

asddasdasasd schrieb:

Mehr als eine Zeile darf es bei einer solch grundlegenden Funktion nicht brauchen. Alles andere ist absurd.

ist aber trotzdem so. und die realität zu verweigern ist auch absurd.

asddasdasasd schrieb:

Warum sollte ich einen Median selbst implementieren wollen? Ich arbeite im medizinischen Sektor. Einen Commit mit nth element werde ich nie durchgewunken bekommen.

lol. und einen der ne 3rd party library mit zigtausend zeilen benötigt schon? absurd.

asddasdasasd schrieb:

Habe auch schon was in der boost https://www.boost.org/doc/libs/1_67_0/doc/html/accumulators/reference.html#header.boost.accumulators.statistics.median_hpp gefunden. Früher oder später wandert es in den Standard und gut ist.

ja, wenn das featuer nicht so dringend ist. am besten einfach warten bis das produkt für das du das machen sollst durch ein anderes ersetzt wird. und das könnt ihr dann in java programmieren. weil ja jeder weiss dass die teletubby-sprachen gerade für medizintechnik so viel besser sind.

wob

asddasdasasd schrieb:

DocShoe schrieb:

Stell dir vor du bist doof und jeder merkt's...

Da helfen auch keine persönlichen Angriffe.

Ich habe also herausgelesen: dir fehlt bei C++ die "große" Super-STL oder eine irgendwie geartete erweiterte Standardbibliothek.

Ja, die gibt es in C++ so nicht. Leider oder nicht leider, je nach dem. Würdest du das wirklich standardisieren wollen? Also im Sinne von ISO? Das wäre doch viel zu viel Aufwand. Und irgendwas kleines zu ändern, würde wieder 3-6 Jahre dauern? Das ergibt keinen Sinn.
Nicht, dass ich mir manchmal auch ne fertige Klasse für Problem XY wünschen würde.

Und dass std::string Kodierungsagnostiker ist, hat mit median schon kaum mehr was zu tun. Du kannst aber natürlich immer eine Bibliothek deiner Wahl nehmen wie zum Beispiel QString aus Qt. Wenn du das nicht magst (und ja, utf8 ist schöner&einfacher als utf16), nimm sowas wie CsString. Mir fehlt bei std::string regelmäßig "begins_with" oder "ends_with". Klar, das gibts in boost. Meine einzigen Argumente gegen die freien Funktionen (und das meine ich ernst!) ist 1. fehlende Vervollständigung in der IDE - und 2. kann ich mir einfach nicht merken, wie herum ich die Parameter angeben muss. Das ist bei member-Funktionen eindeutig.

median(liste von zahlen) ist allerdings keine einfache Operation. Wie hier ja schon gesagt wurde, müsste man 1x nth-Element und einmal max_element aufrufen. Aber diese Operationen würden die Zahlenliste noch umsortieren. Also müsste man die Inputdaten erstmal umkopieren. Oder wie auch immer. Jedenfalls: wenn man schon "mean" berechnet, will man vielleicht den zur Berechnung nötigen Aufwand auch gleich für weitere stat. Eigenschaften nutzen. Daher vermute ich mal, dass mean(const collection) möglicherweise zu unnötigem Mehraufwand in der Berechnung führen würde, insbesondere wenn ich dann auch noch irgendwelche Quantillen berechnen will... Aber naja. Musst du selbst wissen, was die Vor- und Nachteile von C++ in deinem Gebiet sind.

SeppJ

wob schrieb:

Ich habe also herausgelesen: dir fehlt bei C++ die "große" Super-STL oder eine irgendwie geartete erweiterte Standardbibliothek.

Ich möchte noch einmal darauf aufmerksam machen, dass das gefragte Feature bereits in der Standardbibliothek vorhanden war. Und zwar in einer so viel allgemein anwendbareren Form, dass man noch einen Extraschritt gehen musste, um auf die popelige, beschränkte Definition des Medians zu kommen. Der Threadersteller stellte sich bloß absichtlich quer, aus welchen Gründen auch immer.

Die Situation ist so absurd, als hätte er nach einer Funktion zum Sortieren der ersten 5 Elemente gefragt und nach dem Hinweis auf sort_n einen Schreianfall bekommen, dass es doch primitiv sei, dass man N=5 von Hand angeben müsse.

wob

SeppJ schrieb:

wob schrieb:

Ich habe also herausgelesen: dir fehlt bei C++ die "große" Super-STL oder eine irgendwie geartete erweiterte Standardbibliothek.

Ich möchte noch einmal darauf aufmerksam machen, dass das gefragte Feature bereits in der Standardbibliothek vorhanden war. Und zwar in einer so viel allgemein anwendbareren Form, dass man noch einen Extraschritt gehen musste, um auf die popelige, beschränkte Definition des Medians zu kommen.

Das sehe ich nicht so. nth_element modifiziert den Bereich, der übergeben wird. "Gib mir den Median" ist keine modifizierende Operation.

Ich würde mal sagen, man importiere numpy in Python und rechne numpy.median([3,111,4,4,5,10]) aus

SeppJ

wob schrieb:

Das sehe ich nicht so. nth_element modifiziert den Bereich, der übergeben wird. "Gib mir den Median" ist keine modifizierende Operation.

Es modifiziert (was oft ok ist), weil der Medianalgorithmus sonst O(N) im Speicherbedarf ist, was oft inakzeptabel wäre. Wenn man mit O(N) Speicherbedarf ok ist aber absolut keine Modifikation will, kann man ja vorher eine Kopie machen.

wob schrieb:

Ich würde mal sagen, man importiere numpy in Python und rechne numpy.median([3,111,4,4,5,10]) aus

Noch einfacher: Da gibts doch schon statistics.median

hustbaer schrieb:

ist aber trotzdem so. und die realität zu verweigern ist auch absurd.

Ist eben nicht so, mit Boost ist es tatsächlich nur eine Zeile. Alles andere ist nur für Geeks, die sich auf extrem kompliziertem und unleserlichem Code aufgeilen wollen.

hustbaer schrieb:

lol. und einen der ne 3rd party library mit zigtausend zeilen benötigt schon? absurd.

Boost wird so gut wie überall akzeptiert. Wenn du es selbst ordentlich programmierst, dann endest du bei nicht weniger Zeilen.

hustbaer schrieb:

ja, wenn das featuer nicht so dringend ist. am besten einfach warten bis das produkt für das du das machen sollst durch ein anderes ersetzt wird. und das könnt ihr dann in java programmieren. weil ja jeder weiss dass die teletubby-sprachen gerade für medizintechnik so viel besser sind.

Ist besser als jede noch so kleine Funktion selbst (schlecht) implementieren zu müssen. So etwas wie das Hadoop Ecosystem oder Geoserver wären mit C++ niemals mit vertretbaren Ressourcen zu bewältigen.

wob schrieb:

Würdest du das wirklich standardisieren wollen? Also im Sinne von ISO? Das wäre doch viel zu viel Aufwand. Und irgendwas kleines zu ändern, würde wieder 3-6 Jahre dauern? Das ergibt keinen Sinn.
Nicht, dass ich mir manchmal auch ne fertige Klasse für Problem XY wünschen würde.

Hier geht es nicht um GUI Funktionen sondern um einen mathematisch simplen Median. Dessen Definition blieb wahrscheinlich nach seiner Einführung unverändert. Egal wie man es dreht. Es bleibt ein Armutszeugnis der Standardisierung, dass selbst solche alltäglichen Funktionen von jedem selbst implementiert werden müssen.

SeppJ schrieb:

Ich möchte noch einmal darauf aufmerksam machen, dass das gefragte Feature bereits in der Standardbibliothek vorhanden war. Und zwar in einer so viel allgemein anwendbareren Form, dass man noch einen Extraschritt gehen musste, um auf die popelige, beschränkte Definition des Medians zu kommen. Der Threadersteller stellte sich bloß absichtlich quer, aus welchen Gründen auch immer.

Die Gründe habe ich dir genannt. Mehr als eine Zeile darf so etwas nicht brauchen. Theoretisch kannst du in C++ mit wenigen Schlüsselwörtern alles erstellen, damit hast du die noch viel allgemeinere Form. Praxisgerecht ist es nicht.

Das Thema ist für mich erledigt, die richtige Antwort ist:

#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
namespace ba = boost::accumulators;
ba::accumulator_set< uint16_t , ba::stats< ba::tag::median > > container;
container( 0u );
container( 255u );
container( 4095u );
container( 65535u );

Damit reduziert sich der Median auf eine Zeile und 0 eigenes Herumfrickeln an einer Nebenbaustelle.

auto med = ba::median( container );

Es ist schön, einfach zu lesen und übersichtlich.

wob

Und - kommt auch das richtige heraus?

In deinem Beispiel kommt hier 4095 raus, nicht (4095+255)/2.

wob schrieb:

Und - kommt auch das richtige heraus?

In deinem Beispiel kommt hier 4095 raus, nicht (4095+255)/2.

Bestimmt Der gepostete Sourcecode ist ein Ausschnitt und nicht was ich im Programmcode geschrieben habe. Da ist die Aufgabe deutlich aufwändiger.