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 个元素的 vectorIn 长度，向量会完全排序。从 33 个元素开始，它永远不会排序（如预期的那样）。

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

编辑：

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

longes 排序块的长度直方图

4

1 回答 1

6

这会因标准库实现而异（可能会因其他因素而异），但总的来说：

  • 允许 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;
}
于 2015-02-16T19:27:49.797 回答