Ich habe dieses spezielle Thema nirgends gefunden ...

Ich rufe den Algorithmus nth_element () ungefähr 400.000 Mal pro Sekunde für verschiedene Daten in einem std :: -Vektor mit 23 ganzen Zahlen auf, genauer gesagt mit "vorzeichenlosen kurzen" Werten.

Ich möchte die Rechengeschwindigkeit verbessern, und dieser spezielle Aufruf benötigt einen erheblichen Teil der CPU-Zeit. Jetzt habe ich wie bei std :: sort () festgestellt, dass die Funktion nth_element auch bei höchster Optimierungsstufe und NDEBUG-Modus (Linux-Clang-Compiler) im Profiler sichtbar ist, sodass der Vergleich inline ist, aber nicht der Funktionsaufruf selbst. Naja, mehr preise: nicht nth_element () sondern std :: __ introselect () ist sichtbar.

Da die Datenmenge klein ist, habe ich mit einer quadratischen Sortierfunktion PIKSORT experimentiert, die häufig schneller ist als der Aufruf von std :: sort, wenn die Datenmenge weniger als 20 Elemente beträgt, wahrscheinlich, weil die Funktion inline ist.

template <class CONTAINER>
inline void piksort(CONTAINER& arr)  // indeed this is "insertion sort"
{
    typename CONTAINER::value_type a;

    const int n = (int)arr.size();
    for (int j = 1; j<n; ++j) {
        a = arr[j];
        int i = j;
        while (i > 0 && a < arr[i - 1]) {
            arr[i] = arr[i - 1];
            i--;
        }
        arr[i] = a;
    }
}

In diesem Fall war dies jedoch langsamer als die Verwendung von nth_element.

Auch eine statistische Methode ist nicht angebracht,Etwas schneller als std :: nth_element

Finally, da die Werte im Bereich von 0 bis ungefähr 20000 liegen, sieht eine Histogrammmethode nicht angemessen aus.

Meine Frage: kennt jemand eine einfache Lösung dafür? Ich glaube, ich bin wahrscheinlich nicht der einzige, der sehr häufig std :: sort oder nth_element aufrufen muss.