为什么 std::nth_element return 对 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];
}

我注意到对于最多 32 个元素的 vectorIn 长度，向量得到完全排序。从 33 个元素开始，它永远不会排序（如预期的那样）。

不确定这是否重要，但该函数位于使用 "Microsoft Windows SDK 7.1 (C++)".

通过 Matlab 编译的“(Matlab-)mex c++ 代码”中

编辑：

另请参阅以下传递给函数的 1e5 个向量中最长排序块的长度直方图（向量包含 1e4 个随机元素，并计算了一个随机百分位数）。请注意非常小的峰值。

Answer 1

这将因标准库实现而异（并且可能因其他因素而异），但一般而言：

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

为什么 std::nth_element return 对 N < 33 元素的输入向量进行排序？

Why does std::nth_element return sorted vectors for input vectors with N < 33 elements?

c++

sorting

algorithm

mex

nth-element