C/C++ Forum :: Median mit streaming daten

rapso Moderator 15:49:13 09.02.2010 Titel:

Shade Of Mine schrieb:

Hallo Leute.

Ich will den Median einer quasi endlosen Zahlenreihe berechnen. Quasi endlos, da sie schon irgendwann aufhört, ich sie aber nicht speichern kann.

bei sowas macht man wohl oefter ein histogram, du teilst also den wertebereich in buckets auf und approximierst darin dann den median.

__Stefan__ Mitglied 18:22:31 09.02.2010 Titel:

Ich hoffe, das verdeutlicht das Prinzip:

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	#include <iostream> #include <queue> #include <vector> class Average { public: Average(std::size_t median_size): m_median_size(median_size), m_deque(median_size, 0), m_count(0), m_sum(0) { } void Insert(double x) { // Laenge der deque bleibt konstant! m_deque.pop_front(); m_deque.push_back(x); // Inhalt der deque sortieren std::vector<double> tmp(m_deque.begin(), m_deque.end()); std::sort(tmp.begin(), tmp.end()); // Median dazu addieren m_sum += tmp[m_median_size / 2]; ++m_count; } double GetAverage() const { return m_sum / m_count; } private: std::size_t m_median_size; std::deque<double> m_deque; std::size_t m_count; double m_sum; }; int main() { Average a(15); for(int i = 0; i < 1000; ++i) { a.Insert(std::rand()); } std::cout << a.GetAverage(); return 0; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	#include <iostream> #include <queue> #include <vector> class Average { public: Average(std::size_t median_size): m_median_size(median_size), m_deque(median_size, 0), m_count(0), m_sum(0) { } void Insert(double x) { // Laenge der deque bleibt konstant! m_deque.pop_front(); m_deque.push_back(x); // Inhalt der deque sortieren std::vector<double> tmp(m_deque.begin(), m_deque.end()); std::sort(tmp.begin(), tmp.end()); // Median dazu addieren m_sum += tmp[m_median_size / 2]; ++m_count; } double GetAverage() const { return m_sum / m_count; } private: std::size_t m_median_size; std::deque<double> m_deque; std::size_t m_count; double m_sum; }; int main() { Average a(15); for(int i = 0; i < 1000; ++i) { a.Insert(std::rand()); } std::cout << a.GetAverage(); return 0; }

C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	#include <iostream> #include <queue> #include <vector> class Average { public: Average(std::size_t median_size): m_median_size(median_size), m_deque(median_size, 0), m_count(0), m_sum(0) { } void Insert(double x) { // Laenge der deque bleibt konstant! m_deque.pop_front(); m_deque.push_back(x); // Inhalt der deque sortieren std::vector<double> tmp(m_deque.begin(), m_deque.end()); std::sort(tmp.begin(), tmp.end()); // Median dazu addieren m_sum += tmp[m_median_size / 2]; ++m_count; } double GetAverage() const { return m_sum / m_count; } private: std::size_t m_median_size; std::deque<double> m_deque; std::size_t m_count; double m_sum; }; int main() { Average a(15); for(int i = 0; i < 1000; ++i) { a.Insert(std::rand()); } std::cout << a.GetAverage(); return 0; }

Shade Of Mine Moderator 20:11:00 09.02.2010 Titel:

__Stefan__ schrieb:

Ich hoffe, das verdeutlicht das Prinzip:

Genial. Auf die Idee den Durchschnitt aller Median Werte zu nehmen bin ich nicht gekommen. Aber macht vollkommen Sinn. Danke.