为什么std :: nth_element返回N <33个元素的输入向量的排序向量？

Question

我std::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 ++代码"中,通过Matlab使用"Microsoft Windows SDK 7.1(C++)"编译.

编辑:

还参见传递给函数的1e5向量中最长排序块的长度的以下直方图(包含1e4个随机元素和随机百分位数的向量).注意非常小的峰值.

Answer 1

这将从标准库实现到标准库实现(并且可能根据其他因素而有所不同),但一般而言:

• 如果nth_element位于位置n,并且容器在位置n处分区,则允许std :: nth_element在其认为合适时重新排列输入容器.

• 对于小容器,执行完全插入排序通常比快速选择更快,即使这不可扩展.

由于标准库作者通常会选择最快的解决方案,因此大多数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;
}