http:\/\/stackoverflow.com\/questions\/638030\/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list\/638713#638713<\/a><\/p>\nIch hab diesen Algorithmus mal in Qt implementiert und ein wenig ver\u00e4ndert. Bei einer grade Anzahl von Eingangsdaten berechnet er urspr\u00fcngliche Algorithmus den falschen Median. Ich habe es jetzt so ge\u00e4ndert, dass immer das oberste der beiden mittleren Elemente im Array zur\u00fcckgegeben wird. Das kann man irgendwann auch noch mal verbessern.<\/p>\n
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\u00e4ren Suche zu tun. Denn bei jeder Iteration wird der Zahlenbereich, der mit einer double precision floating number Variable dargestellt werden kann, in 2 H\u00e4lften zerlegt. So tanzt der approximierte Median immer um den echten Median herrum, bis die Zahlengenauigkeit fein genug ist.
\nMit 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.<\/p>\n
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.<\/p>\n
Wir haben also einen Agorithmus dessen Laufzeit linear mit der gr\u00f6\u00dfe des Datensatzes w\u00e4chst 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\u00df muss der Datensatz werden, damit der log(n) = 50 wird? 1,125,899,906,842,624 ! Also erst ab einer Billiarden Zahlen h\u00e4tten wir ein Laufzeitvorteil. Dazu br\u00e4uchte man aber auch 8000 Terrabyte an Speicherplatz :D<\/p>\n
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\u00fcr n = 262,144 Hier sieht die Welt schon besser aus. Schon ab 260,000 Zahlen bekomen wir ein Laufzeitvorteil. <\/p>\n
Wir haben also ein Algorithmus, der keinen zus\u00e4tzlichen 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.<\/p>\n
Happy coding ;)<\/p>\n
\r\n\r\n\/*\r\nFind Min and Max of the list containing N items through linear search and name them as HighValue and LowValue Let MedianIndex = floor(N\/2)\r\n\r\n1st Order Binary Search:\r\n\r\nRepeat the following 4 steps until LowValue < HighValue.\r\n\r\n Get MedianValue approximately = ( HighValue + LowValue ) \/ 2\r\n\r\n Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K\r\n\r\n is K > MedianIndex ? then HighValue = MedianValue Else LowValue = MedianValue\r\n\r\n\r\n *\/\r\n\/*!\r\n Return the median. If data has even size, not the avg of the two numbers in the\r\n middel of the array is returned, but the upper one.\r\n\r\n This is an improved version from\r\n http:\/\/stackoverflow.com\/questions\/638030\/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list\/638713#638713\r\n\r\n This algorithm need in practice 50 iterations. Like a binary search around the true median.\r\n *\/\r\nqreal experimenalMedian(const QVector &data) {\r\n if(data.isEmpty())\r\n return 0.0;\r\n\r\n QPair minmax = qMinMax(data);\r\n int medianIdx = qFloor(data.size()\/2.0);\r\n qreal medianValue = (minmax.first + minmax.second)\/2.0;\r\n\r\n while(minmax.first < minmax.second &&\r\n !fuzzyCompare(minmax.first, minmax.second)) {\r\n medianValue = (minmax.first + minmax.second)\/2.0;\r\n int K = 0;\r\n for(int i=0; i < data.size(); i++) {\r\n if(data.at(i) <= medianValue) {\r\n K++;\r\n }\r\n }\r\n K > medianIdx ? minmax.second = medianValue : minmax.first = medianValue;\r\n }\r\n return medianValue;\r\n}\r\n\r\n<\/code>\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Es gibt viele M\u00f6glichkeiten den Median zu berechnen. Eine w\u00e4re die Daten zu sortieren und dann das mittlere Element zu w\u00e4hlen. Dazu muss man aber eine Kopie der Daten speichern, was ung\u00fcnstig ist, wenn der Arbeitsspeicher schon fast voll ist. Jaaa, heutzutage hat jeder Unmengen an Arbeitsspeicher. Es gibt aber Menschen die haben \"NUR\" 2GB […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[17,12],"class_list":["post-1908","post","type-post","status-publish","format-standard","hentry","category-allgemein","tag-cpp","tag-qt"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/1908","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1908"}],"version-history":[{"count":6,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/1908\/revisions"}],"predecessor-version":[{"id":1913,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/1908\/revisions\/1913"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1908"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}