Warum gibt std :: nth_element sortierte Vektoren für Eingabevektoren mit N <33 Elementen zurück?

Question

ich nth_element bin mit einem (in etwa korrekt) Wert für eine Perzentil eines Vektors zu erhalten, etwa so:

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end()); 

    return vectorIn[(percent*vectorIn.size())/100]; 
} 

bemerkte ich, dass für Vectorin Längen von bis zu 32 Elementen, wird der Vektor vollständig sortiert. Ausgehend von 33 Elementen wird es (wie erwartet) nie sortiert.

Nicht sicher, ob das wichtig ist, aber die Funktion ist in einem "(Matlab-) mex C++ - Code", der über Matlab mit dem "Microsoft Windows SDK 7.1 (C++)" kompiliert wird.

EDIT:

auch folgende Histogramms der Längen der längsten sortierten Blöcke in 1E5-Vektoren an die Funktion übergeben (siehe Vektoren enthalten 1E4 zufällige Elemente und ein zufälliges Perzentil wurde berechnet). Beachten Sie die Spitze bei sehr kleinen Werten.

Answer 1

Dies wird von Standard-Bibliothek Implementierung Standard-Bibliothek Implementierung variiert (und auf anderen Faktoren variieren kann), aber im Allgemeinen:

• std :: nth_element wird die neu zu ordnen erlaubt Eingabebehälter, so wie er es für richtig hält, vorausgesetzt, dass das n-te_element in der Position n ist und der Container an der Position n partitioniert ist.

• Bei kleinen Containern ist es normalerweise schneller, eine vollständige Einfügesortierung durchzuführen als eine Schnellauswahl, auch wenn diese nicht skalierbar ist.

Seit Standardbibliothek Autoren für die schnellste Lösung in der Regel entscheiden werden, die meisten nth_element Implementierungen (und was das betrifft, sortieren Implementierungen) verwenden angepasste Algorithmen für kleine Eingänge (oder für kleine Segmente am unteren Rand der Rekursion) , die den Behälter aggressiver sortieren können, als es notwendig erscheint. Für Vektoren von Skalarwerten ist die Einfügesortierung extrem schnell, da sie den größten Vorteil des Caches hat. Mit Streaming-Erweiterungen ist es möglich, es noch schneller zu machen, indem Sie parallele Vergleiche durchführen.

By the way, können Sie nur durch Berechnung der Schwelle Iterator einmal eine winzige Menge der Berechnung speichern, die besser lesbar sein könnte:

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    auto nth = vectorIn.begin() + (percent*vectorIn.size())/100; 
    std::nth_element(vectorIn.begin(), nth, vectorIn.end()); 
    return *nth; 
}