Почему std :: nth_element возвращает отсортированные векторы для входных векторов с N <33 элементами?

Question

Я использую nth_element, чтобы получить (примерно правильное) значение для процентиля вектора, например, так:

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

Я заметил, что vectorIn длиной до 32 элементов, вектор получает полностью отсортирован. Начиная с 33 элементов он никогда не сортируется (как и ожидалось).

Не уверен, что это имеет значение, но функция находится в «(Matlab-) mex C++ code», который скомпилирован через Matlab с помощью «Microsoft Windows SDK 7.1 (C++)».

РЕДАКТИРОВАТЬ:

см также следующую гистограмму длин самых длинных отсортированных блоков в 1e5 векторов, переданных функции (векторы содержали 1E4 случайных элементов и случайного процентиля рассчитывали). Обратите внимание на пик при очень малых значениях.

Answer 1

Это будет отличаться от стандартной реализации библиотеки к стандартной реализации библиотеки (и может варьироваться в зависимости от других факторов), но в общих чертах:

• станд :: nth_element разрешено переставить контейнер ввода, если он сочтет нужным, при условии, что nth_element находится в позиции n, а контейнер разделен в позиции n.

• Для небольших контейнеров, как правило, быстрее выполнять полную сортировку вставки, чем с помощью быстрого выбора, хотя это не масштабируется.

Поскольку стандартные авторы библиотеки, как правило, выбирают для самого быстрого решения, большинство nth_element реализации (и, в этом отношении, сортировать реализации) использовать индивидуальные алгоритмы для небольших входов (или для небольших сегментов в нижней части рекурсии) , который может сортировать контейнер более агрессивно, чем кажется необходимым. Для векторов скалярных значений сортировка вставки выполняется очень быстро, так как она использует максимальное преимущество кеша. Благодаря потоковым расширениям можно ускорить его еще больше, выполнив параллельные сравнения.

Кстати, вы можете сэкономить небольшое количество вычислений лишь вычисление порогового значения итератора один раз, что может быть более удобными для чтения:

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