Я не нашел эту конкретную тему нигде ...

Я вызываю алгоритм nth_element () около 400 000 раз в секунду для разных данных в std :: vector из 23 целых чисел, более точных значений «unsigned short».

Я хочу повысить скорость вычислений, и этот конкретный вызов требует значительной части процессорного времени. Теперь, как и в случае с std :: sort (), я заметил, что функция nth_element видна в профилировщике даже при самом высоком уровне оптимизации и режиме NDEBUG (компилятор Linux Clang), поэтому сравнение встроено, но не сам вызов функции. Что ж, более точный пример: виден не nth_element (), а std :: __ introselect ().

Поскольку размер данных невелик, я экспериментировал с использованием функции квадратичной сортировки PIKSORT, которая часто выполняется быстрее, чем вызов std :: sort, когда размер данных меньше 20 элементов, возможно потому, что функция будет встроенной.

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;
    }
}

Однако это было медленнее, чем использование nth_element в этом случае.

Кроме того, использование статистического метода не подходит,Что-то быстрее, чем std :: nth_element

Наконец, поскольку значения находятся в диапазоне от 0 до около 20000, метод гистограммы не выглядит подходящим.

Мой вопрос: кто-нибудь знает простое решение этого? Я думаю, что я, вероятно, не единственный, кому приходится часто вызывать std :: sort или nth_element.