为什么std::nth_element对于N < 33的输入向量返回排序后的向量？

Question

为什么std::nth_element对于N < 33的输入向量返回排序后的向量？

9

我正在使用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个元素的向量，向量会完全排序。从33个元素开始，它就不再被排序（正如预期）。

不确定这是否重要，但该函数位于通过Matlab使用“Microsoft Windows SDK 7.1（C ++）”编译的“(Matlab-)mex c ++代码”中。

编辑：

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

- stack_horst

4

该函数进行部分排序以返回您请求的值。它需要进行多少个部分排序取决于其实现方式。 - Jonathan Potter

不是与墨西哥相关的，但是很有趣的问题。 - chappjc

你图形左侧的峰看起来很像随机向量中最长连续子序列长度的直方图。这可能对应于小部分随机选取的百分位值非常接近向量结尾的情况，导致最长子序列在从未被nth_vector访问过的向量部分中。但这只是猜测。 - rici

@rici：主意不错，但我已经检查过了，这并不是情况。对于向量最终以这些非常短的排序序列结束的运行，相应的百分位数也均匀地分布在0和100之间。 - stack_horst

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

这将因标准库实现而异(并可能基于其他因素而异)，但通常情况下：

std::nth_element允许根据需要重新排列输入容器，只要第n个元素位于位置n，并且在位置n处对容器进行了分区。
对于小容器，通常比快速选择更快的方法是使用完整的插入排序，尽管这种方法不具有可扩展性。

由于标准库作者通常会选择最快的解决方案，因此大多数nth_element实现（以及sort实现）对于小输入（或递归底部的小段）都使用定制算法，这些算法可能比必要的更积极地对容器进行排序。对于标量值的向量，插入排序非常快，因为它最大程度地利用了缓存。通过流扩展，可以通过进行并行比较来进一步加速。

顺便说一句，您可以通过仅计算阈值迭代器一次来节省少量计算，这可能更易读：

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