Perzentil berechnen
-
Servus,
ich bin auf der Jagd nach einer Methode um das x-te Perzentil zu berechnen. Erst dachte ich, da gibt es bestimmt schon eine einzige überlegene Lösung, aber ich fand diverse Ansätze, einige basteln selbst, einige sortieren die gesamte Liste vorab, einige schaffen es mit weniger. Ein alter Thread dazu ist hier: http://www.c-plusplus.net/forum/199232
Wie würdet ihr das machen ?
Danke vorab.
-
Wie ich schon in dem dort angegebenen Thread gesagt habe, würde ich die Verwendung von nth_element() vorschlagen, wenn du nur das n-größte Element deiner Sammlung benötigst. Das dürfte auf jeden Fall schneller sein als wenn du die Liste komplett sortierst (nach meinem Buch lineare Laufzeit).
Wenn du von den selben Daten mehrere Elemente benötigst, solltest du über's Sortieren nachdenken.(ab wann letzteres günstiger ist, solltest du mal nachmessen)
-
Ich habe später noch einen Vorteil, wenn die Liste sortiert vorliegt, daher ist das mal mein Lösungsvorschlag:
double percentile( ) { // Code-Snippet aus Medianberechnung angepasst von tsql.de/php/median_berechnen_funktion // Eingabe // TODO als Parameter angeben lassen vector<double> items; items.push_back( 0.6 ); items.push_back( 0.7 ); items.push_back( 0.2 ); items.push_back( 0.5 ); items.push_back( 0.1 ); items.push_back( 0.8 ); items.push_back( 0.3 ); items.push_back( 0.4 ); items.push_back( 0.9 ); items.push_back( 1.0 ); // mit diesem ist die Eingabe ungerade // Variablen int size = items.size(); int perc = 99; // TODO als Parameter reinholen double percfraq = perc * 0.01; //cout << "Percfrag = " << percfraq << endl; double rval = 0.0; if ( size == 0 ) { return rval; } // Ausbruch bei leerem Vektor // Debug-Liste //cout << " Ausgabe der Liste:\n"; //vector<double>::const_iterator iter1 = items.begin(); //int c1 = 0; //while (iter1 != items.end() ) //{ // cout << " Lauf ... Item ("; // cout << c1 << "): "; // cout << *iter1 << ";\n"; // ++iter1; // c1++; //} // Sortiervorgang sort( items.begin(), items.end() ); // Debug-Liste //cout << " Ausgabe der sortierten Liste:\n"; //vector<double>::const_iterator iter2 = items.begin(); //int c2 = 0; //while (iter2 != items.end() ) //{ // cout << " Lauf ... Item ("; // cout << c2 << "): "; // cout << *iter2 << ";\n"; // ++iter2; // c2++; //} if ( size % 2 == 0 ) { rval = ( items.at( size * percfraq - 1 ) + items.at( size * percfraq ) ) * 0.5 ; // Fall 'gerade Anzahl an Elementen' -> das arithmetische Mittel der beiden relevanten Elemente gemessen am Perzentilprozentwert } else { rval = items.at( size * percfraq ); // Fall ungerade Anzahl an Elementen -> das Element was zum Perzentilprozentwert passt } return rval; }
-
Ja, wenn du sie später noch sortiert brauchst, dann solltest du es auch sortieren. Allerdings solltest die Unterscheidung in gerade/ungerade bei der letzten if-Abfrage nochmal überdenken - bei einem allgemeinen Quantil solltest du dort eher abfragen, ob
size*percfraqeine ganze Zahl ist.