Es gibt viele Möglichkeiten den Median zu berechnen. Eine wäre die Daten zu sortieren und dann das mittlere Element zu wählen.
Dazu muss man aber eine Kopie der Daten speichern, was ungünstig ist, wenn der Arbeitsspeicher schon fast voll ist. Jaaa, heutzutage hat jeder Unmengen an Arbeitsspeicher. Es gibt aber Menschen die haben "NUR" 2GB RAM und die sind durch die aufgeblasenen Standardprogramme (Browser, Office, Mail, Clould, Solzial) schon zu 85% belegt. Und wenn man dann noch etwas Arbeiten will und sich ein paar Datensätze visualisiert, können schon 50MB mehr zum Überlaufen des RAMs führen ;)
(50MB entsprechen ca. 7Millionen double Variabeln)
Es wäre doch toll, wenn man den Median berechnen könnte, ohne den Datensatz zu verändern oder zu kopieren!
Eine Runde googlen:
http://stackoverflow.com/questions/638030/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list/638713#638713
Ich hab diesen Algorithmus mal in Qt implementiert und ein wenig verändert. Bei einer grade Anzahl von Eingangsdaten berechnet er ursprüngliche Algorithmus den falschen Median. Ich habe es jetzt so geändert, dass immer das oberste der beiden mittleren Elemente im Array zurückgegeben wird. Das kann man irgendwann auch noch mal verbessern.
Noch ein Wort zur Laufzeit. Die Anzahl der Iterationen betrug bei meinem Tests meist so um die 50. Das muss eigentlich auch so sein, denn wir haben es hier mit einer binären Suche zu tun. Denn bei jeder Iteration wird der Zahlenbereich, der mit einer double precision floating number Variable dargestellt werden kann, in 2 Hälften zerlegt. So tanzt der approximierte Median immer um den echten Median herrum, bis die Zahlengenauigkeit fein genug ist.
Mit double Precision bekommt man etwa 16 Ziffern Genauigkeit. Und der 2er Logarithmus von 50 ergibt eine Zahl mit 16 Ziffern. Das passt doch :D Man muss also immer 50mal den Zahlenbereich aufteilen um an den Median zu kommen.
Bei jeder dritten Iteration bekommt man also etwa eine Ziffer an Zahlengenauigkeit dazu. Gibt man sich mit nur 8 Ziffern Genauigkeit zufrieden, braucht man auch nur 25 Iterationen.
Wir haben also einen Agorithmus dessen Laufzeit linear mit der größe des Datensatzes wächst O(n*50). Das ist doch super! Ganz anders als die Variante welches erst die Daten sortiert O(n*log(n)). In der Praxis bringt einem das aber erstmal nichts an Laufzeit. Denn wie groß muss der Datensatz werden, damit der log(n) = 50 wird? 1,125,899,906,842,624 ! Also erst ab einer Billiarden Zahlen hätten wir ein Laufzeitvorteil. Dazu bräuchte man aber auch 8000 Terrabyte an Speicherplatz :D
Gibt man sich in Qt/C++ eine Zahl in der Konsole aus, bekommt man in der Regel nur 6 Ziffern angezeigt. Das entspricht 18Iterationen. Also log(n) = 18 für n = 262,144 Hier sieht die Welt schon besser aus. Schon ab 260,000 Zahlen bekomen wir ein Laufzeitvorteil.
Wir haben also ein Algorithmus, der keinen zusätzlichen Speicherplatz braucht und auch noch in der Laufzeit einstellbar ist. Gibt man sich nur mit wenigen relevanten Ziffern des approximierten Medians zufrieden, ist die Laufzeit schon bei kleinen Datenmengen besser als die des Sortierverfahrens.
Happy coding ;)
/*
Find Min and Max of the list containing N items through linear search and name them as HighValue and LowValue Let MedianIndex = floor(N/2)
1st Order Binary Search:
Repeat the following 4 steps until LowValue < HighValue.
Get MedianValue approximately = ( HighValue + LowValue ) / 2
Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K
is K > MedianIndex ? then HighValue = MedianValue Else LowValue = MedianValue
*/
/*!
Return the median. If data has even size, not the avg of the two numbers in the
middel of the array is returned, but the upper one.
This is an improved version from
http://stackoverflow.com/questions/638030/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list/638713#638713
This algorithm need in practice 50 iterations. Like a binary search around the true median.
*/
qreal experimenalMedian(const QVector &data) {
if(data.isEmpty())
return 0.0;
QPair minmax = qMinMax(data);
int medianIdx = qFloor(data.size()/2.0);
qreal medianValue = (minmax.first + minmax.second)/2.0;
while(minmax.first < minmax.second &&
!fuzzyCompare(minmax.first, minmax.second)) {
medianValue = (minmax.first + minmax.second)/2.0;
int K = 0;
for(int i=0; i < data.size(); i++) {
if(data.at(i) <= medianValue) {
K++;
}
}
K > medianIdx ? minmax.second = medianValue : minmax.first = medianValue;
}
return medianValue;
}
